הבדלים בין גרסאות בדף "פונקציית גיבוב"

נוספו 135 בתים ,  לפני שנתיים
אין תקציר עריכה
מ (בוט החלפות: לעיתים)
ב[[תקשורת ספרתית]] וב[[מדעי המחשב]], '''פונקציית גִּבּוּב''' (ב[[אנגלית]]: '''Hash function'''; לעיתים '''פונקציית ערבול''', '''פונקציית תמצות''' ואף '''פונקציית טחינה''') היא פונקציה שממירה [[קלט]] חופשי באורך משתנה ל[[פלט]] באורך קבוע, בדרך כלל קצר בהרבה. אין זה רצוי, אך עם זאת בלתי נמנע שפונקציית גיבוב תתן לעיתים פלט זהה לקלטים שונים, ולכן פונקציות גיבוב נמדדות בהסתברות להפקת [[פלט]] זהה. לפונקציות גיבוב יש שימושים בבעיות אלגוריתמיות רבות, ובהן [[מיון (מדעי המחשב)|מיון]] וחיפוש בטקסטים ארוכים [[קריפטוגרפיה|ובהצפנה]].
 
== שימושים ==
=== טבלת גיבוב ===
{{הפניה לערך מורחב|טבלת גיבוב}}
פונקציית גיבוב היא מרכיב חשוב בבניית [[טבלת גיבוב]]. הפונקציה משמשת [[אינדקס (מחשב)|אינדקס]] (מפתח) לאיברי [[טבלת גיבוב|טבלת הגיבוב]] והיא "המנוע" הקובע את מהירות הגישה בשליפה ואחסון איברים בטבלה. בהקשר זה, לפונקציית גיבוב ישנם שני תפקידים:
 
א. הפיכת המפתח, שבו משתמשים כדי לאחסן איברים בטבלאות גיבוב, לערך מספרי. לדוגמה, כשהמפתח הוא [[מחרוזת (מדעי המחשב)|מחרוזת]], יש להשתמש בפונקציית גיבוב שממירה מחרוזת למספר.
 
ב. הכנסת הערך המספרי לתחום האינדקסים של הטבלה. לדוגמה, אם הערך המספרי של המפתח הוא 100 והטבלה היא בת 20 מקומות, יש להמיר את הערך 100 למספר בין 0 ל-19.
פונקציות גיבוב ויישומן לצורך איחזור מידע, נחקרו לראשונה על ידי [[ארנולד דמי]] (A.I. Dumey) ב-1956. במדובר באופן כללי בשיטות [[היוריסטיקה|היוריסטיות]] שנותנות פתרון לבעיה שנקראת 'בעיית המילון', שהיא הבעיה הבסיסית שפונקציית גיבוב אמורה לפתור. בהינתן המרחב <math>U</math> של כל אלמנטים האפשריים - מתוכם צריך לאחסן <math>N</math> אלמנטים, המטרה היא למצוא פונקציה שממפה אלמנטים מהמרחב <math>U</math> ל[[מערך (מבנה נתונים)|מערך]] כניסות בזיכרון <math>A[1..N]</math> כך ששלוש הפונקציות הבסיסיות: <math>\text{INSERT}(x,k)</math>, <math>\text{DELETE}(k)</math> ו-<math>\text{LOOKUP}(k)</math> דהיינו הוספה, מחיקה או חיפוש ערכים, צריכות להתבצע און-ליין במהירות האפשרית ובמינימום זיכרון אפשרי. <math>k</math> הוא המפתח לערך ו-<math>x</math> הוא המידע המשויך אליו.
 
תאורטית אפשר להקצות שטח זיכרון כגודל המרחב <math>U</math> ואז כל אלמנט יהיה ממופה לעצמו לפי סדר רץ כלשהו (כל אלמנט יכול להיות [[אינדקס (מחשב)|אינדקס]] של עצמו). אולם במקרה זה צריכת הזיכרון תהיה בזבזנית כי אם <math>N</math> קטן משמעותית מ-<math>U</math> שטח הזיכרון לא ינוצל במלואו. מלבד זאת ייתכן שיהיה בלתי מעשי להקצות כמות כזו של זיכרון אם המרחב גדול. הפתרון של דמי פשוט, מגדירים פונקציה <math>h</math> שהיא פונקציה [[מספר אקראי|ראנדומלית]] 'כאוטית', 'משוגעת':
:<math>h : U\rightarrow \{1,...,N\}</math>,
שתמפה את הערכים באקראי, כך שכל כניסה <math>i</math> במערך <math>A[1..N]</math> תכיל [[רשימה מקושרת]] (מכאן השם), של מפתחות <math>k</math> (אם במקרה קיימים שניים או יותר באותה כניסה) כך שמתקיים <math>h(k)=i</math>. לכל מפתח מצמידים את המידע המשויך אליו. לצורך הפונקציה הראנדומלית הציע דמי פונקציה פשוטה כמו <math>h(x)=x\text{ modulo }p</math> כאשר <math>p</math> [[מספר ראשוני|ראשוני]]. בממוצע הפונקציה פועלת כמצופה והערכים מתפזרים היטב על פני המערך. הסיכוי שיימצאו מספר גדול של מפתחות בכניסה אחת במקרה הממוצע, נמוך. אפשר לראות שמציאת ערך בטבלה היא בערך ב[[סיבוכיות]] של <math>O(1)</math>.
===פונקציית גיבוב אוניברסלית===
{{ערך מורחב|פונקציית גיבוב אוניברסלית}}
ב-1975 פרסמו [[לורנס קרטר]] ו[[מרק ווגמן]] מאמר{{הערה|[http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/universalclasses.pdf Universal Classes of Hash Functions]}} רב השפעה שחוקר את פונקציות הגיבוב מהיבט תאורטי. הם הטביעו לראשונה את המושג [[פונקציית גיבוב אוניברסלית]] (Universal Hash Function) והראו שלוש מחלקות אפשריות של פונקציות כאלו וכן הוכיחו שפונקציה העונה להגדרהל[[הגדרה]] זו, קרובה למינימום התאורטי האפשרי, כלומר עם מינימום התנגשויות ללא תלות באופי הקלט וכן ניתנת לחישוב באופן יעיל.
 
תהי <math>\mathcal{H}</math> מחלקה של פונקציות מהצורה <math>h : U\rightarrow A[1..N]</math> כאשר <math>h</math> שנבחרה באקראי מתוך המרחב <math>\mathcal{H}</math> הממפה ערכים מ-<math>U</math> ל-<math>A</math> כאשר <math>|U|>|A|</math>. אומרים ש-<math>h</math> אוניברסלית אם עבור כל <math>x,y\in U</math> כאשר <math>x\ne y</math> מתקיים:
כלומר ההסתברות שתהיה התנגשות (שהפונקציה <math>h</math> תמפה שני ערכים לאותה כניסה) נמוכה או שווה ל-<math>1/N</math> וכן אומרים שהפונקציה <math>h</math> 'כמעט אוניברסלית' אם היא מקיימת <math>\textstyle \Pr[h(x)=h(y)]\le \frac{2}{N}</math>.
 
לדוגמה אם נתונה קבוצה <math>A=\{0,1,...,a-1\}</math> עם <math>a</math> אלמנטים והקבוצה <math>B=\{0,1,...,b-1\}</math> עם <math>b</math> אלמנטים ונתון מספר ראשוני <math>p\ge a</math> והפונקציה <math>g</math> שממפה אלמנטים מ-<math>Z_p</math> לקבוצה <math>B</math> (מסיבות של יעילות רצוי ש-<math>g</math> תהיה השארית מחילוק ב-<math>b</math>. אם <math>b=2^k</math> אין צורך לבצע חילוק בפועל אלא נוטלים את <math>k</math> הסיביות הפחות משמעותיות של האלמנט ומתעלמים מהיתר). נתונים שני [[אלמנטים]] <math>m</math> ו-<math>n</math> מתוך <math>Z_p</math> כאשר <math>m\ne0</math>. אז הפונקציה
:<math>h_{m,n}(x)=((mx+n)\text{ mod }p)\text{ mod }b</math>
היא פונקציית גיבוב אוניברסלית.
 
=== בדיקת שגיאות ===
בהעברת [[מידע]] ברשת, יבדוק הצד המקבל את שלמות המידע תוך השוואת פלט פונקציית הגיבוב עם הצד השולח. אם הפלט לא שווה, ישלח המקטע הפגום מחדש.
בדומה לכך, בהעתקת קבצים ייבדק המקטע המועתק כדי להבטיח את שלמות ההעתקה. פונקציות דומות משמשות גם לאיתור [[וירוס מחשב|וירוסים]] בקבצים ששותפו באינטרנט וגם כדי לוודא שגורם שלישי לא שינה את המידע בדרך (ראו גם [[התקפת אדם בתווך]]).
 
9

עריכות