פילטר בלום
מתוך ויקיפדיה, האנציקלופדיה החופשית
פילטר בלום (Bloom filter) הוא מבנה נתונים חסכוני במקום בזיכרון מחשב המאפשר לדעת, בהסתברות גבוהה, האם נתון נמצא בקבוצת נתונים מסוימת. הוא הומצא בידי ברוטון ה. בלום.
בדרך כלל משמש הפילטר ככלי עזר לגישה למבנה נתונים אחר, ומאפשר לדעת באופן מיידי האם יש טעם לחפש את הנתונים באותו מבנה נתונים אחר.
ייתכן מצב שבו הפילטר יכזיב, ויצביע על נתון שאינו נמצא כאילו הוא נמצא, אך ההיפך לא ייתכן. תשובה שלילית לגבי הימצאותו של נתון היא נכונה בוודאות.
[עריכה] תיאור האלגוריתם
ישנו מערך של K ביטים, שכל אחד מהם יכול להצביע על 1 או על 0. ערכם ההתחלתי הוא 0.
ישנן m פונקציות ערבול (hash) שונות. טווח הפונקציות הוא k-1..0.
כל אימת שמכניסים נתון, מזינים את פונקציות הערבול בערכו (המכונה בדרך כלל:המפתח שלו). מקבלים כתוצאה m מספרים של ביטים במערך, מספר כתוצאה של כל פונקציה, ואותם "מדליקים" (כלומר קובעים את ערכם על 1).
אחר כך כאשר בודקים האם נתון נמצא, מפעילים את פונקציות הערבול על המפתח של הנתון. אם כל הביטים המתקבלים מהפונקציות דלוקים, יש סבירות גבוהה שהנתון נמצא (אם כי ייתכן שהביטים הודלקו בשל קיומם של נתונים אחרים). אם לא כל הביטים דלוקים, ניתן לומר בוודאות גמורה כי הנתון אינו נמצא (אחרת כבר בהכנסתו היו מודלקים הביטים המתקבלים עבורו בערבול).
[עריכה] ניתוח הסתברותי
נניח שפונקציות הערבול הן בעלות התפלגות אחידה. הסבירות שביט מסוים לא יודלק בידי פונקציית ערבול הוא 1/k.
הסבירות שהוא לא יודלק בידי אף אחת מפונקציות הערבול היא:
.
הסיכוי שביט יישאר בערך אפס אחרי הכנסת n אלמנטים היא:
;
ועל כן הסבירות שהוא יקבל ערך 1 היא:
.
מה הסבירות שתתקבל תשובה חיובית עבור אלמנט שאינו מצוי בקבוצת הנתונים ?
דבר זה יקרה אם כל m הביטים שפונקציות הערבול נותנות עבורו הודלקו.
.
ברור שככל שמספר הביטים במערך גדל, כך קטן הסיכוי לתשובות חיוביות שגויות. ברור גם שהגדלת מספר האלמנטים המוכנסים מגדילה את הסיכוי לשגיאות.
למספר פונקציות הערבול יש שתי השפעות סותרות:מצד אחד, מפעילים יותר פונקציות ולכן צריך שיודלקו יותר ביטים כדי שיניחו שאלמנט מצוי בקבוצת הנתונים. מנגד, בכל פעם שמכניסים נתון, יותר ביטים מודלקים, וממילא גדל הסיכוי שתיווצר בעתיד "התנגשות" שתגרום לתשובה חיובית עבור נתונים שאינם נמצאים.
ניתן לחשב שהמספר האופטימלי של פונקציות ערבול עבור k (מספר ביטים) ו-n (מספר אלמנטים) הוא
,
והסבירות לטעות בשאילתה תהיה:
.
אם נניח שמקצים 32 ביטים לכל אלמנט (k=32*n) ומשתמשים ב-13 פונקציות ערבול, הסיכוי לתשובה חיובית בשאילתה עבור נתון שאינו בקבוצה קטן ממיליונית.
[עריכה] מחיקה
אין אפשרות למחיקת נתון שהוכנס ל-פילטר בלום, והפתרון עלול להיות בנייה מחדש של כל הפילטר.
"כיבוי" פשוט של הביטים שפונקציות הערבול כורכות יחד עם האלמנט היא בלתי אפשרית, שכן ביטים אלו עלולים להצביע גם על נתונים אחרים, שכיבוי הביטים ישלול מהמשתמש את המידע על קיומם.
עם זאת, הועלו רעיונות חדשים ולפיהם ייעשה שימוש במונה, שיימנה כמה פעמים הודלק כל ביט. אז ניתן יהיה להפחית את המונה של כל הביטים הקשורים באלמנט מסוים במקרה של מחיקת האלמנט. ברור שלשם כך יש להקריב מקום נוסף בזיכרון.

