עץ סיפות
ויקיפדיה האנציקלופדיה encyclopedia
במדעי המחשב, עץ סֵיפוֹת (Suffix Tree) הוא מבנה נתונים מסוג Trie דחוס, המכיל את כל הסיפות (סיומות) האפשריות של מחרוזת נתונה ומאפשר חיפוש וגישה מהירים לסיפות הללו, באמצעותו ניתן לאמת את קיומה של תת-מחרוזת כלשהי ביעילות. שמו ניתן לו מצורת הרבים של המילה סֵיפָא - סיומת, בארמית.
עץ הסיפות של מחרוזת S באורך n הוא עץ שמקיים:
- קיימת התאמה 1-1 בין הסיפות של S והמסלולים מהשורש אל העלים.
- הקשתות מתאימות לתתי-מחרוזות לא ריקות.
- לכל הצמתים הפנימיים (פרט אולי לשורש) יש לפחות שני בנים.
כדי להבטיח קיום עץ כזה מוסיפים בסוף המחרוזת אות מיוחדת לסמן את סופה (ריפוד עם $
). הדבר מבטיח כי שום סיפא אינה רישה של סיפא אחרת. מספר העלים בעץ סיפא הוא n ומספר הצמתים הפנימיים הוא כל היותר n-1.