Bloomi filter: kindel „ei” või tõenäoline „jah”

Iga sõna märgib m bitiga reas k bitti. Sõna otsimisel kontrollitakse selle k bitti: juba üks 0 tõestab, et sõna pole lisatud; kui kõik on 1, on sõna filtris tõenäoliselt olemas. Lisa sõnu sammhaaval ja proovi siis otsida enda valitud sõna.

Näidisarvutus — Bloomi filter: kindel „ei” või tõenäoline „jah”

Väärtusega 1 bitid	20 / 64 (31,3%)
Bitte sõna kohta	8,00
Parim k standardhinnangu järgi	5,55
Valepositiivsete osakaalu standardhinnang	3,06%
Hinnang tegeliku täitumuse järgi	3,05%
Mõõdetud 10 000 lisamata sõne põhjal	335 / 10 000 (3,35%)
Lisatud sõnad vastusega „kindlasti mitte”	0 / 8

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Bloomi filter vastab küsimusele, kas element kuulub hulka. Selleks kasutab ta m bitist koosnevat rida ja k räsifunktsiooni. Elemendi lisamisel seatakse need k bitti, millele selle räsid osutavad. Otsing kontrollib samu k bitti: kui mõne väärtus on 0, siis element kindlasti ei kuulu hulka; kui kõik on 1, kuulub see hulka tõenäoliselt. Vale vastus „tõenäoliselt jah” on valepositiivne tulemus. Kui lisatud on n elementi, on valepositiivsete tulemuste osakaalu standardhinnang (1 − e^−kn/m)^k. See on Bloomi 1970. aasta valemi eksponentsiaalne lähendus, mille vähim väärtus saavutatakse, kui k = (m/n) ln 2.

Mida iga sümbol tähendab

m: bittide arv filtris
k: räsifunktsioonide arv ehk bittide arv, mida iga sõna seab ja iga otsing kontrollib
n: lisatud sõnade arv
X: väärtusega 1 bittide arv pärast kõigi n sõna lisamist

Eeldab: Sõna k asukohta saadakse kahest räsist topelträsimise teel: asukoht i on (h₁ + i·h₂) mod m. Siin on h₁ sõna FNV-1a räsi, h₂ täiendavalt segatud ja paarituks muudetud djb2 räsi ning m arvu 2 aste. Seetõttu on sõna k asukohta alati erinevad. Standardhinnang käsitleb kõiki kn asukohta sõltumatute juhuvalikutena. Topelträsimise ja väikese m tõttu erineb see eeldus tegeliku filtri tööst. Valepositiivsete osakaalu mõõdetakse 10 000 sõne hulgas vahemikus 0 kuni 9999. Tulemus on täpne nende sõnede jaoks, kuid ei kehti täpse osakaaluna kõigi võimalike sõnade kohta.

16 räsifunktsiooni annavad halvema tulemuse kui 1 🖖

Vajuta nuppu Viis räsifunktsiooni ja vaata tulemuste all olevat tabelit. Kui filtris on 128 bitti ja 16 sõna, laseb 1 räsifunktsioon läbi 12,82% lisamata sõnedest. 5 korral on osakaal 2,50%, veeru väikseim; 16 korral aga 32,01%, rohkem kui 1 korral. Iga lisanduv funktsioon paneb otsingu kontrollima veel üht bitti, mis aitab tulemust täpsustada. Samal ajal seab iga lisamine veel ühe biti, mis suurendab valepositiivsete tulemuste võimalust. Kui k kasvab 1-st 5-ni, väheneb osakaal igal sammul. Edasi hakkab see kasvama, väikese langusega k = 15 juures. Bloom leidis pöördepunkti 1970. aastal: see saabub siis, kui ligikaudu poolte bittide väärtus on 1. 5 räsifunktsiooni korral on siin 128 bitist selliseid 60. Standardhinnangu järgi on parim k väärtus (m/n) ln 2 = 8 × 0,693 = 5,55.

Väärtusega 1 bittide loendamine annab standardhinnangust täpsema tulemuse 🖖

Vajuta nuppu 16 räsifunktsiooni. Standardhinnang on 9,76%, kuid filter laseb läbi 32,01%. Hinnangu järgi peaks väärtusega 1 olema 128 × (1 − e⁻²) = 110,7 bitti. Need 16 sõna seavad aga 119 bitti. Kui tõsta tegelikult seatud bittide osakaal astmesse 16, saame (119/128)¹⁶ = 31,15%, mis on mõõdetud tulemusele lähedal. Nii suure k korral mõjutavad mõned lisanduvad väärtusega 1 bitid tulemust tugevasti, sest kõik 16 kontrollitavat bitti peavad olema väärtusega 1. Lehel on 6 051 seadistust, mille puhul tekib vähemalt üks valepositiivne tulemus. Neist 5 356 puhul annab tegelik täitumus täpsema hinnangu, kui täpsuse mõõduks võtta hinnangu ja mõõdetud osakaalu suhe. Filter saab oma väärtusega 1 bitid ise kokku lugeda ja seega oma valepositiivsete osakaalu valemist täpsemalt hinnata. Ka need 16 loomanimetust on sattunud ebasoodsalt: 150 muu 16 sõnast koosneva hulga puhul on sama suure filtri keskmine osakaal 14,4%, endiselt hinnangust kõrgem.

Ühe sõna kustutamisel kaob ka teine 🖖

Vajuta nuppu Kustuta owl ja liigu sammhaaval lõpuni. Sõna owl seadis bitid 37, 58 ja 15. Järgmisena lisatud fox kasutas bitte 14, 15 ja 16; biti 15 väärtus oli juba 1. Sõna owl bittide nullimine nullib ka fox jaoks vajaliku biti 15. Nüüd annab fox otsing vastuse „kindlasti mitte”, kuigi sõna on filtris. See on valenegatiivne tulemus, mille puudumist Bloomi filter just lubabki. Bitt näitab ainult seda, et mõni sõna on selle seadnud. Milline sõna, seda bitt ei ütle, mistõttu ei saa ühtki bitti ohutult nullida. Selles 64-bitises filtris põhjustaks 8 sõnast 6 kustutamine ka mõne teise sõna kadumise. Tavapärane lahendus hoiab iga biti asemel väikest loendurit: lisamisel suurendatakse seda 1 võrra ja kustutamisel vähendatakse 1 võrra. See nõuab rohkem mälu.

Kui väike võis olla Bloomi 1970. aasta poolitusfilter? 4 sammu
Burton Bloom tõi 1970. aastal näiteks 500 000 sõnaga poolitusprogrammi. Mõne lihtsa reegli abil saab poolitada neist 450 000; ülejäänud 50 000 tuleb otsida kettal olevast sõnastikust. Ta soovitas hoida nende 50 000 sõna filtrit põhimälus ja leppida sellega, et iga 16 lihtsa sõna kohta suunab 1 programmi asjatult kettale. Mitut bitti ja räsifunktsiooni filter vajab? Mitu kettalt lugemist jääb alles? Seejärel vali siin lehel sama bittide arv sõna kohta ja mõõda tulemust.

Ava see ülesanne tööriistas
1. Parima k korral vajab filter standardhinnangu järgi log₂(1/p) / ln 2 bitti sõna kohta. Kui p = 1/16, saame 4 / 0,6931 = 5,77 bitti. Filtri maht on seega 50 000 × 5,77 = 288 539 bitti; Bloom ise kirjutas „vähem kui 300 000 bitti”. Parim k on 5,77 × ln 2 = 4. 4 räsifunktsiooni korral on hinnangu järgi poolte bittide väärtus 1.
  
  $\frac{lo g _{2} 16}{ln 2} = \frac{4}{0.6931} = 5.77 bits per word, 50000 \times 5.77 = 288539 bits, k = 5.77 \times ln 2 = 4$
2. Kõik 50 000 keerulist sõna tuleb endiselt kettalt otsida. Lisaks läheb kettale iga 16 lihtsa sõna kohta 1, mis annab 450 000 / 16 = 28 125 lugemist juurde. Kokku on see 78 125 kettalt lugemist 500 000-st ehk 15,6%. Bloom ümardas tulemuse 78 000-ni: võrreldes iga sõna kettalt otsimisega jääb ära 84% lugemistest.
  
  $50000 + \frac{450 000}{16} = 78125 disk reads of 500000 (15.6%)$
3. Sõna pikkus neis arvutustes ei esine. Filter vajab sõna kohta 5,77 bitti, olgu sõnaks „cat” või „incomprehensibilities”. Tavaline räsitabel vajas Bloomi hinnangul iga sõna esitamiseks keskmiselt vähemalt 19 bitti. Iga p vähendamine poole võrra lisab sõna kohta 1 / ln 2 = 1,44 bitti. Tõenäosuse 1/64 korral oleks vaja 6 / 0,6931 = 8,66 bitti.
  
  $\frac{1}{l n 2} = 1.44 bits per halving of p, \frac{6}{0.6931} = 8.66 for p = \frac{1}{64}$
4. Sellel lehel saab kasutada kõige rohkem 64 sõna, kuid hinnang sõltub ainult suhtest m/n ja k väärtusest. Vali m = 256, n = 44 (5,82 bitti sõna kohta) ja k = 4. 256 bitist on 122 väärtusega 1 ehk 47,7%. Filtrisse lisamata 10 000 sõnest saab 535 vastuseks „tõenäoliselt jah”: 5,35%, vähem kui filtri kavandamisel sihiks võetud 1/16 = 6,25%. Selle filtri standardhinnang on 6,11%.
  
  $\frac{256}{44} = 5.82 : \frac{535}{10 000} = 5.35% < \frac{1}{16} = 6.25%$
Vastus

288 539 bitti ja 4 räsifunktsiooni; alles jääb 78 125 kettalt lugemist 500 000-st. Lehe 44 sõnaga 256-bitise filtri mõõdetud osakaal on 5,35%, mis jääb sihist allapoole. See tulemus käib ühe konkreetse 44 sõnaga filtri kohta. Kas 50 000 sõna 288 539 bitis annaks sama lähedase tulemuse väärtusele 1/16, ei saa siin kontrollida: lehel on piiriks 64 sõna.

$288539 bits, k = 4, 78125 disk reads$

Õpitee

Allikad (1)

The method itself, the turning point at half the bits set in the first insight, and the hyphenation example the worked problem recomputes: Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM 13(7), July 1970, pp. 422–426.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.

Bloomi filter: kindel „ei” või tõenäoline „jah”

Teooria — Bloomi filter: kindel „ei” või tõenäoline „jah”

Mida iga sümbol tähendab

16 räsifunktsiooni annavad halvema tulemuse kui 1 🖖

Väärtusega 1 bittide loendamine annab standardhinnangust täpsema tulemuse 🖖

Ühe sõna kustutamisel kaob ka teine 🖖

Ülesanne täielikult lahendatud

Mida andmestruktuur võimaldab odavalt teha