עץ סיפות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש
עץ סיפות עבור המחרוזת BANANA מרופדת עם $. מצביעי הסיפה מקווקווים.

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

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

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

שימושים[עריכת קוד מקור | עריכה]

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

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

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

מבני נתונים דומים[עריכת קוד מקור | עריכה]

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

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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


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