אלגוריתם KMP

אלגוריתם KMP הוא אלגוריתם בתחום מדעי המחשב להתאמת תבניות הפועל בזמן ליניארי במקרה הגרוע. האלגוריתם התגלה בשנת 1970 על ידי דונלד קנות' ווואן פראת', ובאופן בלתי תלוי על ידי ג'יימס מוריס. השלושה פרסמו יחדיו את האלגוריתם בכתב העת SIAM בשנת 1977.

מטרתו של האלגוריתם היא למצוא מופעים של מחרוזת P (תבנית, pattern) בתוך מחרוזת T (טקסט), כאשר $|T|=n,|P|=m$. בעוד האלגוריתם הנאיבי לביצוע פעולה זו פועל בזמן $\mathrm {O} (mn)$ בזמן הגרוע, אלגוריתם KMP עובד בזמן $\mathrm {O} (n)$ בזמן גרוע.

תיאור האלגוריתם

נניח $T=t_{0}t_{1}...t_{n-1}$ וגם $P=p_{0}p_{1}...p_{m-1}$

האלגוריתם הנאיבי להתאמת מחרוזות, יחפש עבור כל מיקום בטקסט האם הוא התחלה של המחרוזת. אלגוריתם זה עובד בזמן $\mathrm {O} (mn)$. אלגוריתם KMP משתמש בטרנזיטיביות של התאמת מחרוזות על מנת לחסוך השוואות מיותרות. בכל פעם שהאלגוריתם יתקל בנקודת חוסר התאמה בטקסט, הוא יחזור להתאים את הרישא הארוכה ביותר של התבנית המתאימה לסיפא הארוכה ביותר של הטקסט בנקודה בו נתקלנו בחוסר התאמה.

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

הסבר ויזואלי

כאשר ניתקל בתבנית ABCABCD ובטקסט ABCABCABCABCABCABCD, נקודת אי ההתאמה הראשונה תהיה באינדקס 6.

ניתן לשים לב, שהאלגוריתם הנאיבי יתחיל לחפש מהאינדקס הבא (1), למרות שניתן לדלג מידית לאינדקס 3. KMP יודע לדלג לאינדקס 3, מכיוון שלאחר שהתאמנו את A באינדקס 0, B באינדקס 1 ו-C באינדקס 2, ברור שלא נוכל להתאים את A באינדקסים 1 או 2.

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

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

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

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

פסאודו קוד

חיפוש

קלט - T, P אורך תבנית - m, אורך טקסט - n

1. בנה טבלת סיפות A עבור התבנית P
2. $0\to i$
3. $0\to j$
4. כל עוד $i<n$ בצע:
   1. כל עוד $T[i]=P[j]$ וגם $j<m,i<n$ בצע:
      1. $i+1\to i$
      2. $j+1\to j$
   2. אם j=m, דווח על התאמה באינדקס i-j
   3. אם i=n, סיים
   4. $i-min(0,A[j])\to i$
   5. $max(A[j],0)\to j$

בניית טבלה

קלט - T באורך n

1. צור מערך A בגודל n עם אפסים
2. שים באיבר הראשון במערך -1
3. לכל $i=1...n$ בצע:
   1. $i-1\to i'$
   2. כל עוד $i'>0$ בצע
      1. אם $T[i-1]=T[A[i']]$ צא מהלולאה
      2. אחרת $A[i']\to i'$
   3. $A[i']+1\to A[i]$

הוכחת נכונות

אלגוריתם

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

תהא התאמה באינדקס k, כלומר $p_{0}=t_{k},p_{1}=t_{k+1}...p_{m-1}=t_{k+m-1}$.

על מנת שתימצא התאמה באינדקס k, צריך להתחיל את הלולאה הפנימית עם ערכי i ,j המקיימים $i-j=k$. נשים לב שההפרש בין i ל-j משתנה בשתי אפשרויות -

1. $min(A[j],0)\neq 0$
2. $max(A[j],0)\neq j$

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

במקרה השני, ההפרש גדל בדיוק ב-$j-A[j]$ וגם j לא שווה 0. נניח בשלילה שקיים אינדקס התאמה k המקיים $i-j<k<i-A[j]$, זאת אומרת ש$p_{0}=t_{k},p_{1}=t_{k+1}...p_{m-1}=t_{k+m-1}$. בנוסף, מכיוון שהאלגוריתם הגיע לאינדקס j, מתקיים $p_{0}=t_{i-j},p_{1}=t_{i-j+1}...,p_{j-1}=t_{i-1}$. לכן, מתקיים $p_{0}=p_{k-i+j},p_{1}=p_{k-i+j+1},...,p_{i-k-1}=p_{j-1}$, כלומר אורך הרישא הארוכה ביותר שמתאימה לסיפא הארוכה ביותר באינדקס j היא לכל הפחות $i-k$, ולפי הגדרת הטבלה $A[j]\geq i-k\to k\geq i-A[j]$ בסתירה להנחת השלילה.

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

טבלה

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

הערה - קל לראות $\forall iA[i]<i$. נניח שהאלגוריתם עובד עבור ערכים קטנים מ-i, נוכיח שהוא עובד עבור i -

מקרה ראשון - אם מתקיים $T[i-1]=T[A[i']]$ וגם $i'$ הוא אינדקס שהסיפא הארוכה ביותר הנגמרת אצלו המתאימה לרישא הארוכה ביותר זהה לסיפא באינדקס $i-1$. נוכיח שאכן $A[i]=A[i']+1$. הערה - לפי ההגדרה, $i-1$ מקיים את זה. קל לראות שמתקיים $A[i]\geq A[i']+1$. נניח שמתקיים $A[i]>A[i']+1$, זאת אומרת $A[i]\geq A[i']+2$. אבל אם נוריד את התו האחרון מהסיפא והתו האחרון מהרישא, אזי יש לנו התאמה באורך לכל הפחות $A[i]-1$ באינדקס $i'$, בסתירה להנחה שהאלגוריתם צודק עבור ערכים קטנים מ-i ובפרט $i'$.

מקרה שני - $i'=0$. במקרה זה, מכיוון שלפי הגדרה $\forall i>0A[i]\geq 0$ וגם $i'$ הוא חסם עליון לאורך הסיפא המקסימלית, אזי מתקיים בוודאות $A[i]=0$. ואכן, $A[i']+1=A[0]+1=(-1)+1=0$.

מקרה שלישי - אם מתקיים $T[i-1]\neq T[A[i']]$. במקרה זה, התו החדש שנוסף אינו המשך של הרישא הקודמת, ולכן נחפש רישא קצרה יותר. מכיוון שהרישא הקודמת שווה לסיפא הקודמת, אזי הסיפא הארוכה ביותר המתאימה לרישא הארוכה ביותר ברישא הקודמת, היא גם סיפא של הסיפא הקודמת. מההנחה שהאלגוריתם פועל עבור קלטים קטנים, מתקיים שאורך הסיפא החדשה המתקבלת הוא המקסימלי, ולכן כל $A[i']<k<i'$ לא יכול להיות אורך הסיפא שאינה כוללת את התו האחרון. כלומר - גם אם האלגוריתם לא ימצא בשלב זה את אורך הסיפא הוא יתחיל באיטרציה הבאה עם $i''<i'$, ולכן האלגוריתם תמיד יגיע בסופו של דבר למקרה הראשון או השני.

נוכיח שלא קיים $i''=A[i']<k<i'$ כך ש-k הוא האורך של הסיפא הארוכה ביותר הנגמרת ב-$i-1$ ומתאימה לרישא. אם זה אכן היה מתקיים, אז לפי הגדרה $p_{0}=p_{i-1-k},p_{1}=p_{i-k},...p_{k-1}=p_{i-2}$, אבל מכיוון ש-$i''$ הוא אורך הסיפא הארוכה ביותר המתאימה ל-$i'$, וגם לפי הטרנזיטיביות הסיפא הנגמרת ב-$i-1$ זהה לסיפא הנגמרת ב-$i'$, אז למעשה $p_{i-2}=p_{i'-1}=p_{k-1},p_{i-3}=p_{i'-2}=p_{k-2},...$, וזאת אומרת שאורך הסיפא המקסימלית הנגמרת ב-$i'$ היא לפחות k, בסתירה לכך שהנחנו שהאלגוריתם צודק עבור קלטים קטנים. זאת גם למעשה ההוכחה ש-$i'$הוא חסם עליון לאורך הסיפא, שהרי $A[i]=A[i']+1\leq i'-1+1=i'$ עבור $i'$ כלשהו.

הוכחת זמן ריצה

זמן הריצה הכולל של האלגוריתם הוא $\mathrm {O} (m+n)$, כאשר הזמן הדרוש לבניית טבלה של התבנית הוא $\mathrm {O} (m)$ וזמן החיפוש הדרוש הוא $\mathrm {O} (n)$. נוכיח:

אלגוריתם

כאשר אנחנו מבצעים את החיפוש עצמו, בכל איטרציה של כל אחת מהלולאות יש לפחות קידום אחד של i, כלומר לא קיימת איטרציה בה i לא קודם. בנוסף, כל איטרציה של הלולאות מפעילות $\mathrm {O} (1)$ פעולות, ולכן בסך הכל יש לכל היותר $\mathrm {O} (n)$ פעולות.

טבלה

נסמן מונה C1 הסופר כמה פעמים עודפות האלגוריתם ביקר בתא בודד, ומונה C2 הסופר כמה פעמים האלגוריתם ביקר פעם בודדת. מתקיים $C2\leq n+1$ מכיוון שיש n+1 תאים בטבלה. כפי שצוין קודם, מתקיים $A[i]\leq A[i-1]+1$, וגם $A[i]=A[i-1]+1$ אם ורק אם קיימת איטרציה אחת בדיוק (כלומר C2 מקודם). בנוסף, מתקיים $A[i]<i$ לפי הגדרת הרישא. לכן, ניתן לכתוב $A[i]\leq i-1$, כלומר במקרה הגרוע יש לולאה יורדת. נחבר את התנאים - על מנת שיתקיים $A[i]>a$ צריך שיתקיים $C2>a$ (לפי התנאי הראשון), ועל מנת שנוכל לקדם את C1, צריך שיתקיים $A[i]>0$. בסך הכל, על מנת לקדם את C1 יש לקדם את C2, ולכן מתקיים $C1\leq C2\leq n+1$, ומספר האיטרציות הכולל קטן מ-$2n+2$, או $\mathrm {O} (n)$, כנדרש.

דוגמה

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.

הרחבות

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.

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

• KMP visualization

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34244868אלגוריתם KMP