עץ סיפות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
סקריפט החלפות (ליניארי) |
עריכה והרחבה קלה |
||
שורה 8:
* לכל הצמתים הפנימיים (פרט אולי לשורש) יש לפחות שני בנים.
כדי להבטיח קיום עץ כזה מוסיפים בסוף המחרוזת אות מיוחדת לסמן את סופה (ריפוד עם <code>$</code>
== היסטוריה ==
בהינתן עץ סיפות מספר פעולות ניתנות לביצוע יעיל: מציאת תת-מחרוזת של S, מציאת תת-מחרוזת של S אף אם מספר טעויות מותרות, מציאת התאמות ל[[ביטוי רגולרי|ביטויים רגולריים]]. מבנה הנתונים מאפשר מימוש יעל של מספר אלגוריתמים, כמו מציאת תת-המחרוזת המשותפת הארוכה ביותר של שתי מחרוזות ושל אלגוריתם הדחיסה של [[אלגוריתם למפל-זיו|זיו ולמפל]] (בפרט LZ77). מחרוזת עשויה לייצג גם מקטע של [[DNA]], ועצי סיפות משמשים גם בתחום זה.▼
עצי סיפות הומצאו ב-[[1973]] על ידי ווינר (Weiner) שאף הציע אלגוריתם ליניארי לבנייתם, שהוגדר על ידי [[דונלד קנות']] כ"אלגוריתם השנה של 1973". שיפור נוסף הוצע על ידי מקרייט (McCreight) ב-1976 שהציע אלגוריתם לבנייתם שזקוק לזיכרון ליניארי בלבד. בתחילת שנות ה-1990 מצא מדען המחשב הפיני [[אסקו יוקונן]] שיטה פשוטה לבניית עץ סיפות שנתון בצורה מקוונת בסיבוכיות זמן ומקום <math>O\left(n\right)</math> תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפא. רוב האלגוריתמים לעצי סיפות רצים בזמן לינארי עבור אלפבית בגודל מוגדר, כשבמקרה הגרוע ביותר זמן הריצה הוא <math>O(n\log n)</math>.
== שימושים ==
▲
בהינתן עץ סיפות עבור מחרוזת <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>
== מבני נתונים דומים ==
מבנה נתונים אחר שמאפשר חיפושים דומים, אך כנראה יעיל יותר מעשית, הוא {{Ill|אנגלית|Suffix array|מערך סיפות}} (הייצוג כמערך קומפקטי יותר ויעיל, אולם בעל אותה [[סיבוכיות]] אסימפטוטית).
שורה 20 ⟵ 35:
<div style="direction: ltr;">
*{{citation|last=Weiner|first=P.|title=[[Symposium
*{{citation|last=McCreight|first=Edward M.
*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}}
* Dan Gusfield, ''Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology'', Cambridge University Press, 1997.▼
*{{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}}
▲*
</div>
שורה 29 ⟵ 47:
{{ויקישיתוף בשורה}}
<div style="direction: ltr;">
</div>
| |||