Szerkesztő:Mugli/Bloom filter

A Bloom filter egy helytakarékos valószínűségi modellen alapuló adatszerkezet, amelyet Burton Howard Bloom talált fel 1970-ben. Ezen adatszerkezet használható arra, hogy eldöntsük egy halmaz tartalmaz-e egy adott elemet. Fals pozitív eredmények lehetségesek, de Fals negatívak nem. Elemek hozzáadhatóak a halmazhoz, de kivenni nem lehet belőle. Máshogy megfogalmazva a lekérdezés eredménye lehet: "valószínűleg benne van a halmazban" vagy "biztosan nincs a halmazban". Hozzá lehet adni elemeket a halmazhoz, de törölni nem lehet belőle. Minél több elem van a halmazban, annál nagyobb a valószínűsége a fals pozitív eredménynek a tartalmazásvizsgálat során.

Bloom eredetileg olyan alkalmazásra javasolta ezen adatszerkezetet, ahol a bemeneti adatmennyiség tárolása túl sok helyet foglalt volna a "szokványos", azaz hiba-mentes hasítás alkalmazásával. Ő eredetileg az elválasztás szótárat adta meg, amely akkoriban 500.000 szót tartalmazott. Amelyek szavak közül 90%-ra a nem rendhagyó elválasztási szabályok vonatkoznak. Azonban a fennmaradó 10%-ra el kell tárolni a rendhagyó elválasztási alakot.

Megfigyelések azt mutatják, hogy általános esetben elég kevesebb, mint 10 bit eltárolása ahhoz, hogy 1%-nál kisebb hibaarányt érjünk el.

Algoritmus leírása

Példa egy Bloom filterre, amely a {x, y, z} halmazt reprezentálja. A színes nyilak mutatják meg azokat a pozíciókat a bit-tömbben, amelyre az egyes halmaz elemek leképeződnek a hash függvény által. A w elem nem található a {x, y, z} halmazban, mert egy olyan bit-tömb-be képeződik le amely 0-t is tartalmaz. Ehhez az számhoz, m = 18 és k = 3 értékek.

Egy üres Bloom szűrő egy m hosszú bit tömb, ami csupa 0-t tartalmaz.Szükséges még k különböző hash függvény, amelyek mindegyike leképezi a hash függvényt néhány elem pozícióra m tömb pozíciók, így egy egyenletes véletlenszerű eloszlás. Jellemzően, k kicsi állandó, amely a kívánt ε hibás hibaaránytól függ, míg m arányos k és a hozzáadandó elemek számával.