Bloom szűrő

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. február 10-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Bloom - szűrő egy Burton Bloom által 1970-ben feltalált valószínűségi adatstruktúra [ 1] , amely lehetővé teszi annak ellenőrzését, hogy egy elem egy halmazhoz tartozik-e . Ebben az esetben lehet hamis pozitív eredményt kapni (nincs elem a halmazban, de az adatstruktúra jelzi, hogy igen), de nem téves negatív .

A Bloom-szűrő tetszőleges , a felhasználó által előre beállított memóriát használhatja, és minél nagyobb, annál kisebb az esélye, hogy hamis pozitív legyen. A készlethez új elemek hozzáadásának művelete támogatott, de a meglévők törlése nem (kivéve, ha számlálókkal történő módosítást alkalmazunk).

Az adatstruktúra leírása

A Bloom szűrő egy m bites bittérkép . Kezdetben, amikor az adatstruktúra tárolja az üres halmazt , minden m bit nullára lesz állítva. A felhasználónak k független h 1 , …, h k hash függvényt kell definiálnia , amelyek mindegyike egy elemhalmazt képez le egy m hatványhalmazba . (Más szóval a hash függvény minden elemhez 1-től m-ig terjedő számot rendel.) Minden e elemnél a tömb h 1 ( e ), ..., h k ( e ) számú bitjei megegyeznek a a hash függvények értéke 1.

Annak ellenőrzéséhez, hogy az e elem a tárolt elemek halmazához tartozik-e, ellenőrizni kell a h 1 ( e ) , …, h k ( e ) bitek állapotát. Ha ezek közül legalább az egyik egyenlő nullával, akkor az elem nem tartozhat a halmazhoz (ellenkező esetben az összeadáskor ezek a bitek mindegyike beállna). Ha mindegyik egyenlő eggyel, akkor az adatstruktúra szerint e tartozhat a halmazhoz. Ebben az esetben két helyzet adódhat: vagy az elem valóban a halmazhoz tartozik, vagy ezek a bitek véletlenül lettek beállítva más elemek hozzáadásakor, ami ebben az adatszerkezetben a hamis pozitívumok forrása.

A hash függvények függetlensége biztosítja a h k ( e ) indexek minimális ismétlődési valószínűségét azáltal, hogy többször minimalizálja az 1-re beállított bitek számát. (És ez a hamis pozitív eredmények fő forrása.)

Hamis pozitív valószínűség

Legyen a bittömb mérete egyenlő m bittel és k hash függvényt adunk meg. Tegyük fel, hogy a hash függvények halmazát véletlenszerűen választjuk ki, és bármely x elemhez minden h i hash függvény hozzárendel egy helyet a bittérképen egyenlő valószínűséggel

\Pr(h_{i}(x)=p)={\frac {1}{m)),\quad p=1\ldots m,

és ezen felül az értékek együttesen független valószínűségi változók (a későbbi elemzés egyszerűsítése érdekében). $Szia)$

Ekkor annak a valószínűsége , hogy a következő elem beszúrása során egy egység nem lesz beírva valamelyik p -edik bitbe, egyenlő

\Pr(h_{1}(x)\neq p\cap \ldots \cap h_{k}(x)\neq p)=\Pr(h_{i}(x)\neq p)^{k}= \left(1-{\frac {1}{m}}\right)^{k}.

És annak a valószínűsége, hogy a p -edik bit nulla marad, miután n különböző x 1 , ..., x n elemet beszúrunk az eredetileg üres Bloom-szűrőbe, egyenlő

\Pr \left(\forall i\in \{1\dots k\},\ \forall j\in \{1\ldots n\},\ h_{i}(x_{j})\neq p\right)=\left(1-{\frac {1}{m}}\right)^{kn}\approx e^{-kn/m}

kellően nagy m -re tekintettel a második figyelemre méltó határértékre .

Hamis pozitív eredmény, ha olyan y elemnél , amely nem egyenlő a beillesztett elemek egyikével sem, minden k bit h i ( y ) számmal nem nulla lesz, és a Bloom szűrő hibásan azt válaszolja, hogy y benne van a halmazban. beillesztett elemek közül. Egy ilyen esemény valószínűsége megközelítőleg egyenlő

(1-e^{-kn/m})^{k}.

Nyilvánvaló, hogy ez a valószínűség csökken m növekedésével (a bittömb mérete), és növekszik, ha n (a beillesztett elemek száma) nő. Fix m és n esetén az optimális k szám (a hash függvények száma), amely minimalizálja

\textstyle k={\frac {m}{n}}\ln 2\approx 0{,}6931{\frac {m}{n}}.

Ebben az esetben a hamis pozitív eredmény valószínűsége egyenlő

2^{{-k}}\kb. {0{,}6185}^{{m/n}}.

Következésképpen vegye figyelembe, hogy ahhoz, hogy a Bloom szűrő támogassa az adott korlátos hamis pozitív valószínűséget, a bittérkép méretének lineárisan arányosnak kell lennie a beillesztett elemek számával.

Tulajdonságok

Ellentétben sok más adatstruktúrával (például hash táblákkal ), amelyek szintén sok elemet tárolnak, a Bloom-szűrő az összes lehetséges elem univerzális halmazát képes reprezentálni . Ebben az esetben a bitkép összes bitje egyenlő eggyel.
Két azonos méretű és azonos hash függvénykészlettel rendelkező Bloom szűrő egyesítése és metszéspontja bitenkénti VAGY és ÉS műveletekkel valósítható meg a bittérképeiken.

Alkalmazás

A hash táblákhoz képest a Bloom szűrő több nagyságrenddel kevesebb memóriát tud kezelni, feláldozva a determinizmust. Jellemzően a drágább hozzáférésű (például merevlemezen vagy hálózati adatbázison elhelyezkedő) adatstruktúrában a nem létező adatokra vonatkozó kérések számának csökkentésére, vagyis az arra irányuló kérések „szűrésére” szolgál.

Példák gyakorlati alkalmazásra:

A Squid proxy virágzási szűrőket használ a gyorsítótár-kivonatok beállításához .
A Google BigTable Bloom-szűrőket használ a merevlemez-találatok számának csökkentésére, amikor egy adatbázistáblában egy adott sor vagy oszlop meglétét ellenőrzi. [2]
Számítógépes programok helyesírás-ellenőrzéshez.

Lásd még

Bloom szűrő számlálással

Jegyzetek

↑ Bloom, Burton H. (1970), Tér/idő kompromisszumok a hash kódolásban megengedett hibákkal , Communications of the ACM 13. kötet (7): 422–426 , DOI 10.1145/362686.362692
↑ Bigtable: Elosztott tárolórendszer a strukturált adatokhoz . Letöltve: 2012. július 30. Az eredetiből archiválva : 2015. február 8.. (határozatlan)