פונקציית גיבוב מתגלגלת

פונקציית גיבוב מתגלגלת (באנגלית: Rolling hash) היא פונקציית גיבוב אשר מופעלת על חלקים שונים של מידע כלשהו, בכדי להשוות מול תוצאות גיבוב של בקשות חיפוש. השימוש העיקרי בה הוא האצת חיפושים^[1]^[2].

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

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

תיאור התהליך

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

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

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

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

דוגמה לתהליך

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

ראשית, נקבל את תוצאת הגיבוב של "דהו", נניח לדוגמה בלבד שפוקנציית הגיבוב היא חיבור ערכי הגימטריה, כלומר במקרה הגיבוב של "דהו" יהיה: 4(ד) + 5(ה)+ 6(ו) = 15.

שנית, נעבור "בחלון מתלגל" על המידע ונחשב את ערכי הגיבוב בכל פעם עד שנמצא התאמה, כאשר נשים לב שאורך ה"חלון" הוא כאורך החיפוש שרצינו (שלושה תווים):

אבגדהוזחטיכלמנסעפצקרשת => 1(א) + 2(ב) + 3(ג) = 6.

אבגדהוזחטיכלמנסעפצקרשת => 2(ב) + 3(ג) + 4(ד) = 9.

אבגדהוזחטיכלמנסעפצקרשת => 3(ג) + 4(ד) +5(ה) = 12.

אבגדהוזחטיכלמנסעפצקרשת => (ד) + 5(ה)+ 6(ו) = 15.

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

אם לא התאים, נמשיך בחיפוש עד סוף המידע.

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

חסרונות

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

במילים אחרות, אם נניח $O(m)$ (או $O(1)$ ) כסיבוכיות ההשוואה של פיסות המידע לאחר ההתאמה בגיבוב, כאשר m שואף ל n (הרבה התאמות מול הגיבוב), נקבל $O(n)$ .