Bloomov filter
Bloomov filter je podatkovna struktura, ki računalniku omogoča, da preveri, ali se določen element pojavlja v množici. Bloomovi filtri za to uporabljajo hash funkcije. Za vsak dodan element se izračuna vrednost hasha. Ko se doda nov element, se njegova vrednost hash primerja z vrednostmi drugih elementov v množici. Bloomov filter je verjetnostna podatkovna struktura. Mogoče je dobiti lažno pozitivno, ne pa tudi lažno negativno vrednost. Z drugimi besedami, poizvedba vrne bodisi "morda je v množici" bodisi "zagotovo ni v množici". Elemente je mogoče dodati v množico, ne pa tudi odstraniti. Z vsakim dodanim elementom se verjetnost lažno pozitivnega rezultata poveča.
Edward Bloom je leta 1970 predlagal Bloomov filter. V članku Bloom domneva, da obstaja algoritem za prečrkovanje besed na koncu vrstice. V skladu s primerom ima večina besed preproste vzorce členkovanja. Vendar je za približno 10 % besed potrebno dolgotrajno iskanje, da se pridobi pravilno pravilo. V njegovem primeru je bilo treba podčrtati približno 500 000 besed. Opazil je, da bi uporaba "običajnih" brezhibnih tehnik hashanja, ki shranjujejo vzorce prečrkovanja, zahtevala veliko pomnilnika. Ugotovil je, da lahko s svojo tehniko odpravi večino iskanj. Na primer, območje hashiranja, ki je le 15 % velikosti, ki jo potrebuje idealno hashiranje brez napak, še vedno odpravi 85 % dostopov do diska.
Na splošno je za 1-odstotno verjetnost lažno pozitivnih rezultatov potrebnih manj kot 10 bitov na element, ne glede na velikost ali število elementov v nizu.
Vprašanja in odgovori
V: Kaj je Bloomov filter?
O: Bloomov filter je podatkovna struktura, ki računalnikom omogoča, da preverijo, ali se določen element pojavlja v množici. Za to uporablja hash funkcije, tako da izračuna hash vrednost vsakega dodanega elementa in jo primerja z drugimi elementi v množici.
V: Katera vrsta podatkovne strukture je Bloomov filter?
O: Bloomov filter je verjetnostna podatkovna struktura, kar pomeni, da obstaja možnost lažnih pozitivnih rezultatov, ne pa tudi lažnih negativnih.
V: Kdo je predlagal Bloomov filter?
O: Edward Bloom je leta 1970 predlagal Bloomov filter.
V: Kakšen je bil Edwardov primer uporabe njegove tehnike?
O: Edward je kot primer navedel prečrkovanje približno 500 000 besed; ugotovil je, da lahko s svojo tehniko odpravi večino iskanj in zmanjša število dostopov do diska za 15 %.
V: Koliko bitov na element je potrebnih za 1-odstotno verjetnost lažno pozitivnih rezultatov?
O: Za 1-odstotno verjetnost lažne pozitivnosti je potrebnih manj kot 10 bitov na element, ne glede na velikost ali število elementov v množici.
V: Ali je mogoče odstraniti elemente iz cvetočega filtra, ko so bili dodani?
O: Ne, elemente je mogoče samo dodati v množico, ne pa jih odstraniti.
V: Ali dodajanje več elementov poveča ali zmanjša verjetnost lažno pozitivnega rezultata?
O: Dodajanje več elementov poveča verjetnost, da bo rezultat lažno pozitiven.
