הצגת המקור של הדף "פונקציית גיבוב מתגלגלת"

'''פונקציית גיבוב מתגלגלת''' (ב[[אנגלית]]: '''Rolling hash''') היא [[פונקציית גיבוב]] אשר מופעלת על חלקים שונים של מידע כלשהו, בכדי להשוות מול תוצאות גיבוב של בקשות חיפוש. השימוש העיקרי בה הוא האצת חיפושים<ref>{{קישור כללי|כתובת=http://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf|כותרת=Rolling Hash (Rabin-Karp Algorithm)|אתר=mit.edu|תאריך=February 18, 2011}}</ref><ref>{{קישור כללי|כתובת=http://www.cs.ucf.edu/~dmarino/ucf/cop3503/lectures/RollingHash.pdf|כותרת=String Matching via a Rolling Hash Function|אתר=cs.ucf.edu}}</ref>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== ראו גם ==
* [[פונקציית גיבוב קריפטוגרפית]]
* [[MD5|md5]]
* [[Secure Hash Algorithm|SHA]]

== קישורים חיצוניים ==
* [https://www.geeksforgeeks.org/string-hashing-using-polynomial-rolling-hash-function/ דוגמה לקוד אשר משתמש באלגוריתם]
* [https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/ תיאור נוסף ואימפלנטציה בקוד]

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:פונקציות גיבוב]]