אהו-קוראסיק
אלגוריתם Aho-Corasick הוא אלגוריתם לחיפוש מחרוזות שהומצא על ידי אלפרד אהו ומרגרט קוראסיק[1]. זהו אלגוריתם להתאמת מילון, המאתר פריטים מתוך סט סופי של מחרוזות ("מילון") בתוך טקסט הקלט. האלגוריתם מתאים את כל המחרוזות בו זמנית. הסיבוכיות של האלגוריתם ליניארית באורך של המחרוזות בתוספת אורך הטקסט לחיפוש ומספר ההתאמות בפלט. היות שמוצאים את כל ההתאמות, ייתכן מספר ריבועי של התאמות אם כל תת-מחרוזת מתאימה (למשל מילון = a, aa, aaa, aaaa ומחרוזת קלט aaaa).
באופן לא פורמלי, האלגוריתם בונה אוטומט סופי המזכיר trie עם מעברים נוספים בין צמתים פנימיים שונים. מעברים נוספים אלו מאפשרים מעבר מהיר בין התאמת מחרוזת שנכשלה (למשל, חיפוש אחר cat ב-trie שאינו מכיל cat, אבל מכיל את המילה cart, וכך נכשל בצומת שהרישא שלו היא ca), לענפים אחרים של ה-trie שלהם רישא משותפת (למשל, במקרה הקודם, ענף של המילה attribute עשויה להיות המעבר לרוחב הטוב ביותר). דבר זה מאפשר לאוטומט מעבר בין התאמות של מחרוזות מבלי לחזור על עקבותיו.
כאשר מילון המחרוזות ידוע מראש (לדוגמה, מסד נתונים של וירוסי מחשב), בניית האוטומט יכולה להתבצע פעם אחת off-line והאוטומט נשמר לשימוש מאוחר יותר. במקרה זה, זמן הריצה ליניארי באורך הקלט בתוספת מספר ההתאמות.
אלגוריתם Aho–Corasick להתאמת מחרוזות היווה את הבסיס המקורי של הפקודה fgrep ב-Unix.
דוגמה
בדוגמה זו, נעסוק במילון המכיל את המילים הבאות: {a,ab,bab,bc,bca,c,caa}.
הגרף להלן הוא מבנה הנתונים הנבנה על ידי Aho–Corasick מהמילון הנתון, כאשר כל שורה בטבלה מייצגת צומת ב-trie, ועמודה מייצגת את הרצף (הייחודי) של התווים מהשורש לצומת.
למבנה הנתונים יש צומת אחד עבור כל קידומת של כל מחרוזת במילון. אז אם (bca) נמצא במילון, אז יהיו צמתים ל-(bca), (bc), (b), ו-(). נסמן צומת שנמצא במילון בכחול, ואת יתר הצמתים באפור.
ניצור קשת "בן" מכוונת בצבע שחור מכל צומת לצומת ששמו מתקבל על ידי שרשור תו אחד. לכן תהיה קשת שחורה מ-(bc) ל-(bca).
ניצור קשת "סיפא" מכוונת בצבע כחול מכל צומת לצומת שהוא הסיפא ממש הארוכה ביותר האפשרית שלו בגרף. עבור צומת (caa) לדוגמה, (aa) (a) ו- () הן סיפא ממש. הארוכה ביותר מהן שנמצאת בגרף היא (a). לכן תהיה קשת כחולה מ- (caa) ל-(a). ניתן לחשב את כל הקשתות הכחולות בזמן ליניארי באופן רקורסיבי על ידי מעבר על הקשתות הכחולות של האב, עד שמגיעים לצומת שלו בן שמתאים לאות של צומת המטרה.
ניצור קשת "סיפא של מילון" בצבע ירוק מכל צומת לצומת הבא במילון שניתן להגיע אליו על ידי מעבר על קשתות כחולות. לדוגמה, יש קשת ירוקה מ- (bca) ל-(a) כי (a) הוא הצומת הראשון במילון (כלומר צומת כחול) שניתן להגיע אליו על ידי מעבר על קשתות כחולות ל-(ca) ומשם ל-(a). ניתן לחשב קשתות ירוקות בזמן ליניארי באופן רקורסיבי על ידי מעבר על קשתות כחולות עד שמצא צומת כחול, ושמירת מידע זה (memoizing).
| מסלול | במילון | חיצי סיפא | חיצי סיפא של המילון |
|---|---|---|---|
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | – | () | |
| (ba) | – | (a) | (a) |
| (bab) | + | (ab) | (ab) |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | – | (a) | (a) |
| (caa) | + | (a) | (a) |
בכל שלב מתקדמים מהצומת הנוכחי על ידי מציאת בן מתאים, ואם אין כזה, על ידי מציאת בן של הסיפא, ואם זה לא עובד, על ידי מציאת בן של הסיפא של הסיפא, וכן הלאה, ומסיימים לבסוף בשורש אם אף צומת מתאים לא נמצא קודם לכן.
כאשר האלגוריתם מגיע לצומת, הוא מדפיס את כל ערכי המילון המסתיימים במיקום התו הנוכחי בטקסט הקלט. דבר זה מתבצע על ידי הדפסה של כל צומת שניתן להגיע אליו בעזרת "חיצי סיפא של מילון", כאשר מתחילים בצומת זה, וממשיכים עד שמגיעים לצומת שאין לו קשתות סיפא של מילון. בנוסף, הצומת עצמו מודפס, אם הוא ערך במילון.
ביצוע על מחרוזת הקלט abccab מניב את הצעדים הבאים:
| צומת | מחרוזת נותרת | מצב סופי: פלט | המעבר | פלט |
|---|---|---|---|---|
| () | abccab | מתחילים בשורש | ||
| (a) | bccab | 1:a | () לבן (a) | צומת נוכחי |
| (ab) | ccab | ab:2 | (a) לבן (ab) | צומת נוכחי |
| (bc) | cab | bc:3, c:3 | (ab) לסיפא (ב) לבן (bc) | צומת נוכחי, צומת הסיפא |
| (c) | ab | c:4 | (bc) לסיפא (c) לסיפא () לבן (c) | צומת נוכחי |
| (ca) | b | a:5 | (c) לבן (ca) | צומת הסיפא |
| (ab) | ab:6 | (ca) לסיפא (a) לבן (ab) | צומת נוכחי |
קישורים חיצוניים
- התאמת קבוצה ואלגוריתם Aho–Corasick, שקפי הרצאה מאת Pekka Kilpeläinen
- ערך Aho–Corasick במילון לאלגוריתמים ומבני נתונים של NIST
- Aho–Corasick בשימוש בקוד פתוח NCBI BLAST ל-DNA, וחיפוש רצף חלבונים
הערות שוליים
- ^ Aho, Alfred V.; Corasick, Margaret J. (ביוני 1975). "Efficient string matching: An aid to bibliographic search". Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. MR 0371172.
{{cite journal}}: (עזרה)
23779012אהו-קוראסיק