Bloomov filter
Bloomov filter je dátová štruktúra, ktorá umožňuje počítačom zistiť, či sa daný prvok vyskytuje v množine. Bloomove filtre na to používajú hashovacie funkcie. Pre každý pridaný prvok sa vypočíta hash hodnota. Keď sa pridá nový prvok, jeho hash hodnota sa porovná s hodnotou ostatných prvkov v množine. Bloomov filter je pravdepodobnostná dátová štruktúra. Je možné získať falošne pozitívny výsledok, ale nie falošne negatívny. Inými slovami, dotaz vráti buď "pravdepodobne v množine", alebo "určite nie je v množine". Prvky možno do množiny pridávať, ale nie odstraňovať. S každým pridaným prvkom rastie pravdepodobnosť získania falošne pozitívneho výsledku.
Edward Bloom navrhol Bloomov filter v roku 1970. V článku Bloom predpokladá, že existuje algoritmus na oddeľovanie slov na konci riadku. Podľa príkladu má väčšina slov jednoduché vzory pre spojovníky. Ale približne 10 % slov si vyžaduje časovo náročné vyhľadávanie na získanie správneho pravidla. V jeho prípade išlo o spojovník približne 500 000 slov. Videl, že použitie "normálnych" bezchybných techník hashovania, ukladajúcich vzory spojovníkov, by si vyžadovalo veľa pamäte. Zistil, že použitím jeho techniky by mohol eliminovať väčšinu vyhľadávaní. Napríklad oblasť hashovania, ktorá má len 15 % veľkosti potrebnej pri ideálnom bezchybnom hashovaní, stále eliminuje 85 % prístupov na disk.
Všeobecnejšie povedané, na 1 % pravdepodobnosť falošne pozitívneho výsledku je potrebných menej ako 10 bitov na prvok, nezávisle od veľkosti alebo počtu prvkov v súbore.
Otázky a odpovede
Otázka: Čo je to Bloomov filter?
Odpoveď: Bloomov filter je dátová štruktúra, ktorá umožňuje počítačom zistiť, či sa daný prvok vyskytuje v množine. Používa na to hashovacie funkcie tak, že vypočíta hashovaciu hodnotu každého pridaného prvku a porovná ju s ostatnými prvkami v množine.
Otázka: Aký typ dátovej štruktúry je Bloomov filter?
Odpoveď: Bloomov filter je pravdepodobnostná dátová štruktúra, čo znamená, že existuje možnosť získania falošne pozitívnych výsledkov, ale nie falošne negatívnych.
Otázka: Kto navrhol Bloomov filter?
Odpoveď: Edward Bloom navrhol Bloomov filter v roku 1970.
Otázka: Aký bol Edwardov príklad použitia jeho techniky?
Odpoveď: Edwardovým príkladom bolo spojenie približne 500 000 slov; zistil, že pomocou svojej techniky mohol eliminovať väčšinu vyhľadávaní a znížiť počet prístupov na disk o 15 %.
Otázka: Koľko bitov na prvok je potrebných pre 1 % pravdepodobnosť falošne pozitívneho výsledku?
Odpoveď: Na 1 % pravdepodobnosť falošnej pozitivity je potrebných menej ako 10 bitov na prvok, nezávisle od veľkosti alebo počtu prvkov v množine.
Otázka: Je možné odstrániť prvky z blokového filtra po ich pridaní?
Odpoveď: Nie, prvky možno do množiny iba pridať, ale nie odstrániť.
Otázka: Zvyšuje alebo znižuje pridávanie ďalších prvkov pravdepodobnosť získania falošne pozitívneho výsledku?
Odpoveď: Pridanie väčšieho počtu prvkov zvyšuje pravdepodobnosť získania falošne pozitívneho výsledku.
