אלגוריתם רבין-קארפ

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

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

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

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

סקירה כללית

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

מספר אלגוריתמים מתקדמים לחיפוש מחרוזת, כמו אלגוריתם Knuth–Morris–Pratt ואלגוריתם Boyer–Moore, משפרים את זמן הריצה במקרה הגרוע על ידי שימוש במידע נוסף שמתקבל מכל חוסר התאמה, כדי לדלג על מיקומים בטקסט שבוודאות לא יתאימו לדוגמה.

לעומתם, האלגוריתם של רבין–קארפ משיג את שיפור הביצועים שלו באמצעות פונקציית גיבוב, אשר מבצעת בדיקה מקורבת (approximate check) בכל מיקום. השוואה מדויקת מתבצעת רק אם תוצאת הגיבוב של תת-המחרוזת שווה לזו של הדוגמה.

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

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

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

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

האלגוריתם

function RabinKarp(string s[1..n], string pattern[1..m])
    hpattern := hash(pattern[1..m]);
    for i from 1 to n-m+1
        hs := hash(s[i..i+m-1])
        if hs = hpattern
            if s[i..i+m-1] = pattern[1..m]
                return i
    return not found

השורות 2, 4 ו־6 דורשות כל אחת זמן ריצה של O(m). עם זאת, שורה 2 מבוצעת רק פעם אחת, ושורה 6 מתבצעת רק אם ערכי הגיבוב תואמים – דבר שלא סביר שיקרה יותר מפעמים ספורות. שורה 5 מתבצעת O(n) פעמים, אך כל השוואה בה לוקחת זמן קבוע, ולכן ההשפעה שלה היא בסך הכול O(n). הבעיה היא בשורה 4.

חישוב נאיבי של ערך הגיבוב של תת-המחרוזת s[i+1..i+m] דורש O(m) זמן, כיוון שיש לבדוק כל תו בנפרד. מאחר שחישוב הגיבוב מתבצע בכל איטרציה של הלולאה, האלגוריתם עם חישוב גיבוב נאיבי דורש זמן כולל של O(mn) — אותה סיבוכיות כמו אלגוריתם חיפוש מחרוזת פשוט.

כדי להשיג מהירות, יש לחשב את הגיבוב בזמן קבוע. ה״טריק״ הוא שהמשתנה hs כבר מכיל את ערך הגיבוב של s[i..i+m-1]. אם ניתן להשתמש בערך הזה כדי לחשב את ערך הגיבוב הבא בזמן קבוע, אז חישוב ערכי הגיבוב העוקבים יהיה מהיר.

ניתן לנצל את הטריק הזה באמצעות גיבוב מתגלגל (rolling hash) — פונקציית גיבוב שמעוצבת במיוחד כדי לאפשר את הפעולה הזו.

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

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

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

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

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

מסמך על האלגוריתם - https://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf