מסנן בלום

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

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

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

תיאור האלגוריתם

דוגמה לפילטר בלום המייצג את הקבוצה {x, y, z}. החצים הצבעוניים מראים את המקומות במערך הביטים אליהם מופה כל אחד מאיברי הקבוצה. האיבר w אינו חלק מהקבוצה {x, y, z}, כי אחד המקומות אליו הוא ממופה במערך הביטים מכיל 0. באיור זה, m = 18 and k = 3.

ישנו מערך של k ביטים, שכל אחד מהם שווה ל-0 או ל-1. ערכם ההתחלתי הוא 0.

ישנן m פונקציות ערבול (hash functions) שונות. טווח הפונקציות הוא k-1..0.

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

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

ניתוח הסתברותי

נניח שפונקציות הערבול הן בעלות התפלגות אחידה. ההסתברות שביט מסוים לא יודלק בידי פונקציית ערבול היא $1-{\frac {1}{k}}$.

ההסתברות שביט מסוים לא יודלק בידי אף אחת מפונקציות הערבול היא:

$\left(1-{\frac {1}{k}}\right)^{m}$.

ההסתברות שביט יישאר בערך אפס אחרי הכנסת n איברים היא:

$\left(1-{\frac {1}{k}}\right)^{mn}$;

ועל כן ההסתברות שערכו של ביט מסוים יהיה 1 לאחר הכנסת n איברים היא:

$1-\left(1-{\frac {1}{k}}\right)^{mn}$.

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

$\left(1-\left(1-{\frac {1}{k}}\right)^{mn}\right)^{m}\approx \left(1-e^{-mn/k}\right)^{m}$.

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

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

ניתן לחשב שהמספר האופטימלי של פונקציות ערבול עבור k (מספר ביטים) ו-n (מספר איברים) הוא

${\frac {k}{n}}\ln 2$,

וההסתברות לטעות בשאילתה תהיה:

$\left({\frac {1}{2^{\ln 2}}}\right)^{k/n}$.

אם נניח שמקצים 32 ביטים לכל איבר (k=32*n) ומשתמשים ב-13 פונקציות ערבול, הסיכוי לתשובה חיובית בשאילתה עבור איבר שאינו בקבוצה קטן ממיליונית.

יתרונות וחסרונות

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

ניתוח יעילות

באופן נאיבי, אם אורך הקלט הוא l ויש להפעיל עליו m פעמים את אלגוריתם הערבול (שבדרך כלל לינארי באורך הקלט) הרי שעלות חיפוש איבר בקבוצה וההכנסה של איבר לקבוצה היא ml. עלות זו גבוהה מזו הדרושה למציאת איבר בעזרת חיפוש בטבלת גיבוב רגילה. ניתן להציע פונקציות ערבול שבהן ניתן להשתמש בתוצאת חישוב ערבול אחד כדי למצוא את תוצאת הערבולים האחרים, לדוגמה SHA-1 MD5 ודומיהן. בעזרת שיטות אלו ניתן להגיע לסיבוכיות m+l.

מחיקה

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

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

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