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

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

יהי Σ האלפבית (קבוצה סופית). פורמלית, גם התבנית וגם טקסט החיפוש הם וקטורים של אלמנטים מעל Σ .Σ יכולה להיות האלף-בית האנושי הרגיל (למשל, האותיות A עד Z באלפבית הלטיני). יישומים אחרים עשויים להשתמש באלפבית בינארי $(\Sigma =\{0,1\})$ או אלפבית של DNA $(\Sigma =\{A,C,G,T\})$ בביואינפורמטיקה.

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

סיווג בסיסי

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

אלגוריתמים לתבנית בודדת

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

אלגוריתם	זמן עיבוד מקדים	זמן התאמה
אלגוריתם חיפוש מחרוזות נאיבי	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

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

אלגוריתמים למספר קבוע של תבניות

• אלגוריתם אהו-קוראסיק (הרחבה של KMP)
• Commentz-וולטר אלגוריתם (הרחבה של בויאר-מור)
• Set-BOM (הרחבה של BOM)
• אלגוריתם רבין-קארפ

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

סיווגים אחרים

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

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

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

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

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

השיטה הנאיבית

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

חיפוש מבוסס אוטומט סופי דטרמיניסטי

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

שיטות אחרות

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

שיטות אינדקס

אלגוריתמים מהירים יותר מבוססים על עיבוד מקדים של הטקסט. לאחר בניית אינדקס לתתי-המחרוזות, למשל עץ סיפות או מערך סיפות, ניתן למצוא במהירות מופעים של התבנית. כדוגמה, ניתן לבנות עץ סיפות ב- $\Theta (n)$ זמן, ולמצוא את כל z המופעים של התבנית ב- $O(m)$ תחת ההנחה כי גודל האלפבית קבוע, וכל הצמתים הפנימיים של העץ יודעים אילו עלים נמצאים בתת-העץ שלהם. האחרון ניתן לביצוע על ידי הפעלת אלגוריתם DFS מהשורש של העץ.

ווריאציות נוספות

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

ראו גם

• עימוד רצפים
• התאמת תבניות דחוסות

לקריאה נוספת

• ר. ס בויאר וג'יי. אס. מור, אלגוריתם חיפוש מחרוזות מהיר, Carom. ACM 20, (10), 262-272(1977).
• צ'ארלס א. ליזרסון, תומאס ה. קורמן, רונלד ריבסט, קליפורד שטיין. מבוא לאלגוריתמים, מהדורה שלישית. MIT Press ו-McGraw-Hill, 2009. ISBN 0-262-03293-7. פרק 32: התאמת מחרוזות, עמ'. 985-1013.

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתמים לחיפוש מחרוזות בוויקישיתוף

• רשימה ענקית (מתוחזקת) של קישורים בנושא התאמת תבניות עדכון אחרון:12/27/2008 20:18:38
• StringSearch – אלגוריתמים לחיפוש מחרוזות בעלי ביצועים גבוהים ב-Java – מימושים של אלגוריתמים רבים לחיפוש מחרוזות ב-Java, (בויאר-מור, BNDN, בויאר-מור-הורספול, בויאר-מור-הורספול-רייטה, Shift-Or)
• StringsAndChars – מימושים מימוש של אלגוריתמים רבים לחיפוש מחרוזות (עבור תבנית אחת או יותר) ב-Java
• אלגוריתמים להתאמת מחרוזות מדויקת — אנימציה ב-Java, תיאור מפורט ומימוש C של אלגוריתמים רבים.
• (PDF) שיפורים להתאמת מחרוזות מקורבת על תבנית אחת או יותר
• Kalign2: התאמה מרובה בעלת ביצועים גבוהים של רצפים של חלבון ונוקלאוטיד, מאפשר תוספות חיצוניות
• מימוש C של עץ סיפות מבוסס חיפוש מחרוזות