אלגוריתמים לחיפוש מחרוזות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

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

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

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

ניתן לסווג את האלגוריתמים השונים על ידי מספר התבניות בהן כל אחד משתמש.

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

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

נסמן ב-m את אורך התבנית, ב-n את אורך טקסט החיפוש, וב-; את גודל האלפבית.

אלגוריתם זמן עיבוד מקדים זמן התאמה[1]
אלגוריתם חיפוש מחרוזות נאיבי 0 (אין עיבוד מקדים) (Θ(nm
אלגוריתם רבין-קארפ לחיפוש מחרוזות (Θ(m ממוצע (Θ(n + m


במקרה הגרוע (Θ((n−m)m

חיפוש מבוסס אוטומט סופי (Θ(mk (Θ(n
אלגוריתם KMP (Θ(m (Θ(n
אלגוריתם בויאר-מור לחיפוש מחרוזות (Θ(m + k במקרה הטוב (Ω(n/m,


הגרוע (O(mn

אלגוריתם Bitap

(shift-or, shift-and, Baeza–Yates–Gonnet)

(Θ(m + k (O(mn
אלגוריתם תיאום מחרוזות דו-כיווני (Θ(m (O(n+m
(BNDM (Backward Non-Deterministic Dawg Matching (O(m (O(n
(BOM (Backward Oracle Matching (O(m (O(n

אלגוריתם בויאר-מור מהווה סטנדרט בספרות עבור אלגוריתמים מעשיים לחיפוש מחרוזות.[2]

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

באופן טבעי, לא ניתן למנות את התבניות באופן סופי במקרה זה. הן מיוצגות בדרך כלל על ידי דקדוק רגולרי או ביטוי רגולרי.

סיווגים אחרים[עריכת קוד מקור | עריכה]

ניתן לסווג באמצעות גישות אחרות. אחת הנפוצות ביותר משתמשת בזמן עיבוד מקדים כקריטריון עיקרי.

מחלקות של אלגוריתמים לחיפוש מחרוזות[3]
טקסט לא מעובד מראש טקסט מעובד מראש
תבניות לא מעובדות מראש אלגוריתמים בסיסיים שיטת האינדקס
תבניות מעובדות מראש בניית מנועי חיפוש שיטת החתימה

שיטה נוספת מסווגת את האלגוריתמים על פי אסטרטגית ההתאמה שלהם:[4]

  • להתאים את הרישא קודם (KMP, Shift, אהו-קוראסיק)
  • להתאים את הסיפא קודם (בויאר-מור ווריאציות שלו, קומנץ-וולטר)
  • להתאים את הגורם הטוב ביותר קודם (BNDM, BOM, set-BOM)
  • אסטרטגיה אחרת (נאיבי, רבין-קרפ)

השיטה הנאיבית[עריכת קוד מקור | עריכה]

אך לא יעילה כדי לחפש מחרוזת אחת בתוך השנייה, היא לבדוק בכל מקום בה היא יכולה להמצא, אחד אחד, לראות אם היא שם. תחילה בודקים אם יש העתק של התבנית שמתחיל בתו הראשון של המחרוזת; אם לא, בודקים אם יש העתק של התבנית המתחיל בתו השני של המחרוזת; אם לא, נחפש החל מהתו השלישי, וכן הלאה. בדרך כלל, נצטרך להסתכל רק תו אחד או שניים לכל מיקום שגוי כדי לגלות שהתבנית לא מופיעה בו, כך שבמקרה הממוצע, זה לוקח O(n + m) צעדים, שבו n הוא אורך המחרוזת. m הוא אורך התבנית; אבל במקרה הגרוע, כמו חיפוש של התבנית "aaaab" בתוך המחרוזת "aaaaaaaaab", לוקח .

חיפוש מבוסס אוטומט סופי דטרמיניסטי[עריכת קוד מקור | עריכה]

DFA search mommy.svg

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

שיטות אחרות[עריכת קוד מקור | עריכה]

KMP מחשב אוטומט סופי דטרמיניסטי המזהה קלטים עם התבנית לחיפוש כסיפא, בויאר–מור מתחיל לחפש מסוף המחרוזת, כך שבדרך כלל הוא יכול לקפוץ קדימה בכל צעד מספר תווים כאורך התבנית. באייסה–ייטס עוקב אחר j התווים האחרונים האם הם מהווים קידומת של התבנית, ולכן ניתן להתאים אותו לחיפוש עמום של מחרוזות. אלגוריתם bitap הוא יישום של הגישה של באייסה–ייטס.

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

אלגוריתמים מהירים יותר מבוססים על עיבוד מקדים של הטקסט. לאחר בניית אינדקס לתתי-המחרוזות, למשל עץ סיפות או מערך סיפות, ניתן למצוא במהירות מופעים של התבנית. כדוגמה, ניתן לבנות עץ סיפות ב- זמן, ולמצוא את כל z המופעים של התבנית ב- תחת ההנחה כי גודל האלפבית קבוע, וכל הצמתים הפנימיים של העץ יודעים אילו עלים נמצאים בתת-העץ שלהם. האחרון ניתן לביצוע על ידי הפעלת אלגוריתם DFS מהשורש של העץ.

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

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

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

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

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

  1. ^ זמנים אסימטוטיים מבוטאים על ידי הסימונים O, Ω, Θ.
  2. ^ Hume; Sunday (1991). "Fast String Searching". Software: Practice and Experience 21 (11): 1221–1248. doi:10.1002/spe.4380211105. 
  3. ^ Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/.
  4. ^ Gonzalo Navarro; Mathieu Raffinot (2008). "Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences". ISBN 0-521-03993-2.