A Bloom-szűrő hatékony valószínűségi alapú adatszerkezet, melyet Burton Howard Bloom írt le 1970-ben, annak ellenőrzésére használják, hogy egy elem egy halmaz eleme-e. Hamis pozitívok előfordulhatnak, de hamis negatívok nem – tehát egy kérés vagy „a halmazban lehet”, vagy „egyértelműen nincs a halmazban” eredményt ad. Hozzáadhatók elemek a halmazhoz, de el nem vehetők (de ez számláló Bloom-szűrővel megoldható). Az elemszámmal nő a hamis pozitív eredmény valószínűsége.
Ez az elemek leképezését jelenti -ra, majd vizsgálatát annak vizsgálatával, hogy , mindezt több h hasítófüggvénnyel vizsgálva.
Bloom a technikát olyan esetekre javasolta, ha a forrásadat nagy memóriát igényelne „hagyományos” hibamentes hasítási technikákkal. Példaként írt egy szavas szótár szótagolási algoritmusáról, ahol a szavak 90%-a egyszerű szabályt követ, de a maradék 10% költséges tárhelyhozzáférést igényel bizonyos szótagolási minták megszerzéséhez. Elegendő magmemóriával egy hibátlan hasítófüggvény használható minden felesleges hozzáférés megszüntetéséhez, de korlátozott memória esetén Bloom technikája kisebb területet igényel, de a legtöbb felesleges hozzáférést megszünteti. Például egy ideális hasításhoz szükséges terület 15%-ával megegyező hasítási terület a hozzáférések 85%-át megszünteti.
Általánosabban: kevesebb mint 10 bit szükséges 1%-os hamispozitív-valószínűséghez elemszámtól és mérettől függetlenül.
Az algoritmus leírása bélyegkép|360px|Bloom-szűrő, melynek elemei . A színes nyilak az elemekhez rendelt helyeket mutatják a bittömbben. A w elem nem része az halmaznak, mivel egy 0-t tartalmazó helyhez is rendeli a hasítófüggvény. Az ábrán .
Az üres Bloom-szűrő 0 bitből álló sor. Ezenkívül szükséges különböző hasítófüggvény, melyek egyes elemeket a tömbbeli helyek valamelyikéhez rendelnek egy elemet, uniform véletlenszerű eloszlást létrehozva. Általában k kis, az hibaaránytól függő konstans, míg m k-val és a hozzáadandó elemek számával arányos.
Egy elem hozzáadásához a k hasítófüggvény argumentumaként adandó meg, így k helyet kapva. E helyek bitjei 1-re állítandók.
Egy elem lekérdezéséhez (vagyis annak ellenőrzéséhez, hogy a halmaz eleme-e) megadandó a k hasítófüggvény argumentumaként, így k helyet kapva. Ha bármely helyen a bit 0, az elem nem eleme a halmaznak, ha az volna, beillesztésekor minden bit 1 lenne. Ha mindegyik 1, vagy a halmaz eleme az elem, vagy más elemek hozzáadásakor változtak 1-re a bitek, hamis pozitívot adva. Egyszerű Bloom-szűrőben nincs különbség a két eset közt, de összetettebb módszerek megoldják ezt.
A k eltérő függvény tervezése nehézkes lehet nagy k-ra. Egy jó, széles kimenetű hasítófüggvényhez gyenge korrelációnak kell lennie (ha egyáltalán van) a különböző bitmezők közt, így több „különböző” hasítófüggvény hozható létre a kimenet több bitmezőre való szeletelésével. Egy másik mód k eltérő bemeneti érték (például ) bevitele egy bemenetű hasítófüggvényhez, vagy ezen értékek kulcshoz adása. Nagy m vagy k esetén a függvények függetlensége a hamispozitív-arány csekély növekedésével enyhíthető.; . (Különösen mutatja meg a k index levezetését javított dupla, illetve tripla hasítással, melyek a dupla hasítás egyszerű véletlenszám-generáló változatai, melyek bemenete a két vagy három hasítási érték.)
Egy elem eltávolítása egyszerű Bloom-szűrőből lehetetlen, mivel nem deríthető ki, hogy a k hozzárendelt bit melyike állítandó 0-ra. Bár a k bit bármelyikének 0-ra állítása elég az elem eltávolításához, ez más elemeket is eltávolít, melyeknek e bitre van leképezésük. Mivel az egyszerű algoritmus nem ad lehetőséget annak meghatározására, hogy más elemek is vannak-e, melyek megváltoztatják az elemhez eltávolítható biteket, bármely bit eltávolítása hamis negatívot okozhat.
Egy elem egyszeri eltávolítása egy Bloom-szűrőből szimulálható másik Bloom-szűrővel, mely az eltávolított elemeket tartalmazza. Azonban a második szűrő hamis pozitívjai az összetett szűrőben nem kívánt hamis negatívok lesznek. Ekkor egy korábban törölt elem visszaadása nem lehetséges, mivel a „törölt” szűrőből kellene törölni.
Gyakran bár minden kulcs elérhető, de felsorolásuk költséges (például sok olvasási műveletet igényel). Ha a hamispozitív-arány túl magas, a szűrő újból létrehozható, de ez általában ritka. Hely- és időelőnyök bélyegkép|360px|Bloom-szűrő kulcsértékes tároló válaszidejének gyorsítására. Az értékek hosszú elérési idejű meghajtón vannak, a Bloom-szűrős döntések sokkal gyorsabbak. Pozitív jelzés esetén a hamis pozitívok kiszűréséért néhány hozzáférés történik. A válaszidő jobb Bloom-szűrővel, mint anélkül.
A hamis pozitívok kockázata ellenére a Bloom-szűrők jelentős helyelőnnyel rendelkezik más halmazjelölő adatszerkezetekhez képest, amilyenek az önkiegyensúlyozó bináris keresőfák, a trie-k, a hasítótáblák, a tömbök és a bejegyzések kapcsolt listái. Ezek legtöbbjéhez szükséges maguknak az elemeknek a tárolása, mely kevés bittől (kis egészek) tetszőleges számú bitet igénybevehetnek, például sztringek esetén (a trie-k kivételek, mivel azonos prefixumú elemek közt megoszthatnak tárhelyet). Azonban a Bloom-szűrők nem tárolják magukat az adatokat, és önálló megoldás kell a tényleges tárhelyhez. A kapcsolt szerkezeteknek a mutatókhoz lineáris helytöbblet kell. Egy 1%-os hibaarányú, k optimális értékű Bloom-szűrőhöz ezzel szemben elemenként mintegy 9,6 bit kell elemmérettől függetlenül. Ennek oka részben a tömbökhöz hasonló tömörség, részben a valószínűség-alapú természete. Az 1%-os hamispozitív-arány elemenként mintegy 4,8 bittel tizedére csökkenthető.
Azonban ha a lehetséges értékek száma kicsi, és nagy részük a halmaz eleme lehet, a Bloom-szűrőnél a determinisztikus bittömb jobb lehet, mely csak 1 bitet igényel lehetséges elemenként. A hasítótáblák hely- és időelőnnyel is rendelkeznek, ha az ütközéseket figyelmen kívül hagyják, és csak azt tárolják, hogy az egyes helyek tartalmaznak-e elemet, ez esetben gyakorlatilag Bloom-szűrők lettek, ahol .
A Bloom-szűrők érdekessége, hogy egy elem hozzáadásához vagy egy elem halmazba tartozásának ellenőrzéséhez szükséges idő konstans (), az elemszámtól független. Nincs más ilyen konstans adatszerkezet, de a ritka hasítótáblák átlagos elérési ideje kisebb lehet egyes Bloom-szűrőkénél. Hardverben azonban a Bloom-szűrő jobb, mivel a k keresés egymástól független és párhuzamossá tehető.
Helyhatékonysága megértéséhez fontos az általános Bloom-szűrő összehasonlítása a speciális esettel. Ha , a hamis pozitívok arányának alacsonyan tartásához kevés bitnek kell 1-nek lennie, így a tömbnek nagynak kell lennie, hosszú 0-sorokkal. A tömb méretéhez viszonyított információtartalma alacsony. Az általános Bloom-szűrő ( sokkal több 1 bitet enged alacsony hamispozitív-arány mellett. Megfelelő k és m esetén a bitek körülbelül fele 1 lesz,, pp. 21–22 melyek nagyjából véletlenszerűek lesznek, minimalizálva a redundanciát és maximalizálva az információtartalmat.
Hamispozitív-arány bélyegkép|360px|A hamispozitív-arány az elemszám és az m szűrőméret függvényében, optimális hasítófüggvény feltételezésével.
Ha egy hasítófüggvény minden tömbbeli helyet azonos valószínűséggel választ ki, és m bites a tömb, annak valószínűsége, hogy egy bitet elem beillesztésekor nem változtat 1-re egy hasítófüggvény, .
Ha k a hasítófüggvények száma, és egyikük közt sincs korreláció, annak valószínűsége, hogy egy bitet egy hasítófüggvény se állít 1-re:
Felhasználva az -gyel kapcsolatos azonosságot: , így nagy m esetén
n elem esetén a 0 bit valószínűsége:
tehát az 1 bité:
Egy, a halmazban nem lévő elem ellenőrzésekor a hasítófüggvénnyel számítótt k pozíció a fenti valószínűséggel 1. Annak valószínűsége hogy mindegyik 1, így az algoritmus hibásan állítja, hogy az elem a halmazban van, gyakran szerepel így:
Ez nem feltétlenül igaz, mert feltételezi az egyes bitek állapotának valószínűségének függetlenségét. Azonban feltéve, hogy ez közelítőleg igaz, a hamis pozitívok valószínűsége csökken m növekedésével, és nő n-ével (az elemszáméval).
A hamis pozitív tényleges valószínűsége függetlenség feltételezése nélkül:
ahol a kapcsos zárójelek másodfajú Stirling-számokat jelölnek.
Egy ugyane közelítést adó elemzést adott meg Mitzenmacher és Upfal., pp. 109–111, 308. Miután mind az n elem bekerült a szűrőbe, legyen q az m bitből a 0-k aránya (tehát a 0 bitek száma qm). Ekkor egy halmazon kívüli elem ellenőrzésekor a k hasítófüggvény bármelyike által adott pozíció esetén annak valószínűsége, hogy a talált bit 1, . Így annak valószínűsége, hogy mind a k hasítófüggvény által talált bit 1, . Továbbá q várt értéke annak valószínűsége, hogy egy adott helyt érintetlenül hagyott mind a k hasítófüggvény mind az n elemre, mely: . Bebizonyítható a függetlenség feltételezése nélkül, hogy a q a várt értékhez nagy valószínűséggel nagyon közel van. Az Azuma–Hoeffding-egyenlőtlenségből bebizonyították, hogy:, p. 308.
Innen kijelenthető, hogy a pontos hamispozitív-valószínűség:
Optimális hasítófüggvényszám A hasítófüggvények száma, k, pozitív egész kell, hogy legyen. Ettől eltekintve adott m és n esetén a legkevesebb hamis pozitívot adó k
A szükséges bitszám, m adott n (elemszám), a kívánt hamispozitív-valószínűség, ε és optimális k esetén k fenti valószínűségbe helyettesítésével adható meg:
vagyis:
Innen:
Tehát az optimális bitszám:
ahol a megfelelő k hasítófüggvényszám eltekintve attól, hogy egésznek kell lennie:
Tehát adott ε hamispozitív-valószínűség esetén a Bloom-szűrő hossza, m arányos a szűrt elemek számával, n-nel, a szükséges hasítófüggvények száma csak ε-tól függ.
Az képlet 3 okból közelít. Először: az -et -ként közelíti, mely jó aszimptotikus közelítés (egyre jobban közeledik, ahogy m →∞). Másodszor, feltételezi, hogy az, hogy a tesztelt bit 1, független attól, hogy bármely más bit 1. Végül feltételezi, hogy egész.
Goel és Gupta azonban közelítések és feltételezések nélküli felső határt adtak, és bemutatták, hogy egy véges, m bites, n elemes és k hasítófüggvényes Bloom-szűrő hamispozitív-valószínűsége () legfeljebb
Ez azt jelenti, hogy a közelítő képlet legfeljebb fél elemmel többet és legfeljebb 1-gyel kevesebb bitet jelent.
Egy Bloom-szűrő elemszámának közelítése
szerint egy Bloom-szűrő elemszáma az alábbi képlettel közelíthető:
ahol a szűrő elemszámának becslése, m a szűrő hossza, k a hasítófüggvények száma, X az 1 bitek száma.
Halmazok uniója és metszete
A Bloom-szűrők halmazok kompakt megadására alkalmas. Gyakran használják két halmaz uniójának vagy metszetének elemszámának becslésére. kimutatta, hogy két m hosszú Bloom-szűrő esetén elemszámuk közelítőleg és
Uniójuk mérete közelítőleg ahol azon bitek száma, mely legalább az egyik szűrőben 1. Metszetük mérete közelítőleg a három képletet együtt használva.
Jellemzők Szemben egy hagyományos hasítótáblával, mely nyílt címzést használ ütközésfeloldáshoz, egy fix méretű Bloom-szűrő tetszőleges mennyiségű elemű halmazt jelölhet, azonban a hamispozitív-arány addig növekszik, míg a szűrőben minden bit 1 nem lesz, ahol már minden lekérdezés pozitív eredményt ad. Nyílt címzésű hasítással sosincs hamis pozitív, de a teljesítmény csökken, míg el nem éri a lineáris keresését. Azonos méretű és hasítófüggvény-halmazú Bloom-szűrők uniója és metszete bitenkénti „vagy” és „és” műveletekkel kapható meg. Az unióművelet veszteségmentes abban az értelemben, hogy az eredmény ugyanaz, mint a két halmaz uniójából képzett Bloom-szűrő. A metszetművelet eredményének hamispozitív-aránya nem nagyobb egyik kiinduló szűrőénél sem, de a két halmaz metszetéből készített szűrőénél nagyobb lehet. Bizonyos hasítókódok tekinthetők bevágott kártyák Bloom-szűrőiként. Ilyen például a Zatocoding, melyet Calvin Mooers hozott létre 1947-ben, ahol a kategóriahalmazt bevágások jelölik a kártyán, minden kategóriának véletlenszerű 4 bevágásos mintával.
Példák