עץ סיפות

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

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

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

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

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

בהינתן עץ סיפות עבור מחרוזת  באורך  מספר פעולות ניתנות לביצוע יעיל:
 חיפוש מחרוזות ב-:
 מציאת תת-מחרוזת  ב- באורך  בזמן 
 מציאת המופעים הראשונים של התבניות  שאורכן  בזמן 
 מציאת  מופעים של התבניות  שאורכן  בזמן 
 מציאת תת-מחרוזת של S אף אם מספר טעויות מותרות
 מציאת התאמות לביטויים רגולריים
 תכונות של מחרוזת:
 מציאת תת-המחרוזת המשותפת הארוכה ביותר של המחרוזות  ו- בזמן 
 דחיסה של זיו ולמפל (בפרט LZ77) ב-
 מציאת תת-מחרוזת חוזרת הארוכה ביותר ב-

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

 לקריאה נוספת 

Michael Rodeh, Vaughan Pratt and Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM 28 (1), 1981, 16 - 24.

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

סיפות, עץ