הצגת המקור של הדף "עץ סיפות"

[[קובץ:Suffix tree BANANA.svg|ממוזער|200px|שמאל|עץ סיפות עבור המחרוזת <code>BANANA</code> מרופדת עם <code>$</code>. מצביעי הסיפה מקווקווים.]]
ב[[מדעי המחשב]], '''עץ סֵיפוֹת''' (Suffix Tree) הוא [[מבנה נתונים]] מסוג [[Trie]] דחוס, המכיל את כל הסיפות (סיומות) האפשריות של מחרוזת נתונה ומאפשר חיפוש וגישה מהירים לסיפות הללו, באמצעותו ניתן לאמת את קיומה של תת-מחרוזת כלשהי ביעילות.
שמו ניתן לו מצורת הרבים של המילה '''סֵיפָא''' - סיומת, ב[[ארמית]].

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

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

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

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

בהינתן עץ סיפות עבור מחרוזת <math>S</math> באורך <math>n</math> מספר פעולות ניתנות לביצוע יעיל:
* חיפוש מחרוזות ב-<math>S</math>:
** מציאת תת-מחרוזת <math>P</math> ב-<math>S</math> באורך <math>m</math> בזמן <math>O(m)</math>
** מציאת המופעים הראשונים של התבניות <math>P_1,\dots,P_q</math> שאורכן <math>m</math> בזמן <math>O(m)</math>
** מציאת <math>z</math> מופעים של התבניות <math>P_1,\dots,P_q</math> שאורכן <math>m</math> בזמן <math>O(m + z)</math>
** מציאת תת-מחרוזת של S אף אם מספר טעויות מותרות
** מציאת התאמות ל[[ביטוי רגולרי|ביטויים רגולריים]]
* תכונות של מחרוזת:
** מציאת תת-המחרוזת המשותפת הארוכה ביותר של המחרוזות <math>S_i</math> ו-<math>S_j</math> בזמן <math>\Theta(n_i + n_j)</math>
** דחיסה של [[אלגוריתם למפל-זיו|זיו ולמפל]] (בפרט LZ77) ב-<math>\Theta(n)</math>
** מציאת תת-מחרוזת חוזרת הארוכה ביותר ב-<math>\Theta(n)</math>

== מבני נתונים דומים ==
מבנה נתונים אחר שמאפשר חיפושים דומים, אך כנראה יעיל יותר מעשית, הוא {{קישור שפה|אנגלית|Suffix array|מערך סיפות}} (הייצוג כמערך קומפקטי יותר ויעיל, אולם בעל אותה [[סיבוכיות]] אסימפטוטית).

== לקריאה נוספת ==

<div style="direction: ltr;">
*{{citation|last=Weiner|first=P.|title=[[Symposium on Foundations of Computer Science|14th Annual IEEE Symposium on Switching and Automata Theory]]|year=1973|pages=1–11|contribution=Linear pattern matching algorithms|doi=10.1109/SWAT.1973.13|contribution-url=http://airelles.i3s.unice.fr/files/Weiner.pdf|accessdate=2018-05-25|archive-date=2016-03-03|archive-url=https://web.archive.org/web/20160303211939/http://airelles.i3s.unice.fr/files/Weiner.pdf|url-status=dead}}
*{{citation|last=McCreight|first=Edward M.|title=A Space-Economical Suffix Tree Construction Algorithm|date=1976|journal=[[Journal of the ACM]]|volume=23|issue=2|pages=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.
*{{citation|last=Ukkonen|first=E.|title=On-line construction of suffix trees|url=http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf|year=1995|journal=[[Algorithmica]]|volume=14|issue=3|pages=249–260|doi=10.1007/BF01206331}}
*{{citation|title=Fast text searching for regular expressions or automaton searching on tries|year=1996|last1=Baeza-Yates|last2=Gonnet|first1=Ricardo A.|first2=Gaston H.|journal=[[Journal of the ACM]]|volume=43|issue=6|pages=915–936|doi=10.1145/235809.235810}}
*{{citation|last=Farach|first=Martin|title=[[Symposium on Foundations of Computer Science|38th IEEE Symposium on Foundations of Computer Science (FOCS '97)]]|year=1997|pages=137–143|contribution=Optimal Suffix Tree Construction with Large Alphabets|contribution-url=http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf}}
*{{citation|last=Gusfield|first=Dan|title=Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology|year=1999|publisher=Cambridge University Press|isbn=0-521-58519-8}}
</div>

==קישורים חיצוניים ==
{{ויקישיתוף בשורה}}

{{מבני נתונים}}
{{קצרמר|מדעי המחשב}}
[[קטגוריה:עצי חיפוש|סיפות, עץ]]