עץ סיפות
BANANA מרופדת עם $. מצביעי הסיפה מקווקווים.במדעי המחשב עץ סֵיפוֹת (Suffix Tree) הוא מבנה נתונים המאפשר חיפושים מהירים של תת-מחרוזת כלשהי של מחרוזת נתונה, ויישומים נוספים הקשורים למחרוזות. שמו ניתן לו מצורת הרבים של המילה סֵיפָא - סיומת, בארמית.
עץ הסיפות של מחרוזת S באורך n הוא עץ שמקיים:
- קימת התאמה 1-1 בין הסיפות של S והמסלולים מהשורש אל העלים.
- הקשתות מתאימות לתתי-מחרוזות לא ריקות.
- לכל הצמתים הפנימיים (פרט אולי לשורש) יש לפחות שני בנים.
כדי להבטיח קיום עץ כזה מוסיפים בסוף המחרוזת אות מיוחדת לסמן את סופה (ריפוד עם $.). הדבר מבטיח כי שום סיפא אינה רישה של סיפא אחרת. מספר העלים בעץ סיפא הוא n ומספר הצמתים הפנימיים הוא כל היותר n-1.
בהינתן עץ סיפות מספר פעולות ניתנות לביצוע יעיל: מציאת תת-מחרוזת של S, מציאת תת-מחרוזת של S אף אם מספר טעויות מותרות, מציאת התאמות לביטויים רגולריים. מבנה הנתונים מאפשר מימוש יעל של מספר אלגוריתמים, כמו מציאת תת-המחרוזת המשותפת הארוכה ביותר של שתי מחרוזות ושל אלגוריתם הדחיסה של זיו ולמפל (בפרט LZ77). מחרוזת עשויה לייצג גם מקטע של DNA, ועצי סיפות משמשים גם בתחום זה.
עצי סיפות הומצאו ב-1973 על ידי ווינר (Weiner) שאף הציע אלגוריתם לינארי לבניתם. שיפור נוסף הוצע על ידי מקרייט (McCreight) שהציע אלגוריתם לבנייתם שזקוק לזיכרון לינארי בלבד. בתחילת שנות ה-1990 מצא יוקונן שיטה פשוטה לבניית עץ סיפות שנתון בצורה מקוונת בסיבוכיות זמן ומקום תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפא.
מבנה נתונים אחר שמאפשר חיפושים דומים, אך כנראה יעיל יותר מעשית, הוא מערך סיפות (הייצוג כמערך קומפקטי יותר ויעיל, אולם בעל אותה סיבוכיות אסימפטוטית).
לקריאה נוספת
- P. Weiner, Linear pattern matching algorithm, 14th Annual IEEE Symposium on Switching and Automata Theory, 1973 1-11.
- Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM 23 (2), 1976, 262 - 272.
- Michael Rodeh, Vaughan Pratt and Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM 28 (1), 1981, 16 - 24.
- Dan Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
קישורים חיצוניים
- E. Ukkonen, On-line construction of suffix trees. Algorithmica 14(3): 249-260, 1995.
| מבני נתונים | ||
|---|---|---|
| מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
| גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • X-fast trie • טריי y מהיר• עץ WAVL | |
| הסתברותיים | מסנן בלום | |
