עץ סיפות

עץ סיפות עבור המחרוזת BANANA מרופדת עם $. מצביעי הסיפה מקווקווים.

במדעי המחשב עץ סֵיפוֹת (Suffix Tree) הוא מבנה נתונים המאפשר חיפושים מהירים של תת-מחרוזות כלשהי של מחרוזת נתונה, ויישומים נוספים הקשורים למחרוזות. שמו ניתן לו מצורת הרבים של המילה סֵיפָא - סיומת, בארמית.

עץ הסיפות של מחרוזת S באורך n הוא עץ שמקיים:

• קימת התאמה 1-1 בין הסיפות של S והמסלולים מהשורש אל העלים.
• הקשתות מתאימות לתתי-מחרוזות לא ריקות.
• לכל הצמתים הפנימיים (פרט אולי לשורש) יש לפחות שני בנים.

כדי להבטיח קיום עץ כזה מוסיפים בסוף המחרוזת אות מיוחדת לסמן את סופה (ריפוד עם $.). הדבר מבטיח כי שום סיפא אינה רישה של סיפא אחרת. מספר העלים בעץ סיפא הוא n ומספר הצמתים הפנימיים הוא כל היותר n-1. בהינתן עץ סיפות מספר פעולות ניתנות לביצוע יעיל: מציאת תת-מחרוזת של S, מציאת תת-מחרוזת של S אף אם מספר טעויות מותרות, מציאת התאמות לביטויים רגולריים. מבנה הנתונים מאפשר מימוש יעל של מספר אלגוריתמים, כמו מציאת תת-המחרוזת המשותפת הארוכה ביותר של שתי מחרוזות ושל אלגוריתם הדחיסה של זיו ולמפל (בפרט LZ77). בהקשר זה חשוב לציין שמחרוזת עשויה לייצג גם מקטע של DNA, ועצי סיפות משמשים גם בתחום זה.

עצי סיפות הומצאו ב-1973 על ידי ווינר (Weiner) שאף הציע אלגוריתם לינארי לבניתם. שיפור נוסף הוצע על ידי מקרייט (McCreight) שהציע אלגוריתם לבנייתם שזקוק לזיכרון לינארי בלבד. בתחילת שנות ה-1990 מצא יוקונן שיטה פשוטה לבניית עץ סיפות שנתון בצורה מקוונת בסיבוכיות זמן ומקום $O\left(n\right)$ תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפא.

מבנה נתונים אחר שמאפשר חיפושים דומים, אך כנראה יותר יעיל במעשה, הינו מערך סיפות (הייצוג כמערך יותר קומפקטי ויעיל, אולם בעל אותה סיבוכיות אסימפטוטית).

לקריאה נוספת

• 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.

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.