עץ סיפות

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

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

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

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

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

היסטוריה

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

שימושים

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

בהינתן עץ סיפות עבור מחרוזת $S$ באורך $n$ מספר פעולות ניתנות לביצוע יעיל:

• חיפוש מחרוזות ב-$S$:
  • מציאת תת-מחרוזת $P$ ב-$S$ באורך $m$ בזמן $O(m)$
  • מציאת המופעים הראשונים של התבניות $P_{1},\dots ,P_{q}$ שאורכן $m$ בזמן $O(m)$
  • מציאת $z$ מופעים של התבניות $P_{1},\dots ,P_{q}$ שאורכן $m$ בזמן $O(m+z)$
  • מציאת תת-מחרוזת של S אף אם מספר טעויות מותרות
  • מציאת התאמות לביטויים רגולריים
• תכונות של מחרוזת:
  • מציאת תת-המחרוזת המשותפת הארוכה ביותר של המחרוזות $S_{i}$ ו-$S_{j}$ בזמן $\Theta (n_{i}+n_{j})$
  • דחיסה של זיו ולמפל (בפרט LZ77) ב-$\Theta (n)$
  • מציאת תת-מחרוזת חוזרת הארוכה ביותר ב-$\Theta (n)$

מבני נתונים דומים

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

לקריאה נוספת

• Weiner, P. (1973), "Linear pattern matching algorithms" (PDF), 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1–11, doi:10.1109/SWAT.1973.13, אורכב מ-המקור (PDF) ב-2016-03-03, נבדק ב-2018-05-25
• McCreight, Edward M. (1976), "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM, 23 (2): 262–272, doi:10.1145/321941.321946
• Michael Rodeh, Vaughan Pratt and Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM 28 (1), 1981, 16 - 24.
• Ukkonen, E. (1995), "On-line construction of suffix trees" (PDF), Algorithmica, 14 (3): 249–260, doi:10.1007/BF01206331
• Baeza-Yates, Ricardo A.; Gonnet, Gaston H. (1996), "Fast text searching for regular expressions or automaton searching on tries", Journal of the ACM, 43 (6): 915–936, doi:10.1145/235809.235810
• Farach, Martin (1997), "Optimal Suffix Tree Construction with Large Alphabets" (PDF), 38th IEEE Symposium on Foundations of Computer Science (FOCS '97), pp. 137–143
• Gusfield, Dan (1999), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, ISBN 0-521-58519-8

קישורים חיצוניים

מדיה וקבצים בנושא עץ סיפות בוויקישיתוף

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