Bloomův filtr
Bloomův filtr je datová struktura, která umožňuje počítačům zjistit, zda se daný prvek vyskytuje v množině. Bloomovy filtry k tomu používají hashovací funkce. Pro každý přidaný prvek se vypočítá hodnota hash. Když je přidán nový prvek, jeho hodnota hash se porovná s hodnotami ostatních prvků v množině. Bloomův filtr je pravděpodobnostní datová struktura. Je možné získat falešně pozitivní výsledek, ale ne falešně negativní. Jinými slovy, dotaz vrátí buď "pravděpodobně v množině", nebo "určitě není v množině". Prvky lze do množiny přidávat, ale ne odebírat. S každým přidaným prvkem roste pravděpodobnost získání falešně pozitivního výsledku.
Edward Bloom navrhl Bloomův filtr v roce 1970. V článku Bloom předpokládá, že existuje algoritmus pro spojování slov na konci řádku. Podle příkladu má většina slov jednoduché vzory pro spojování. Ale asi 10 % slov vyžaduje časově náročné vyhledávání pro získání správného pravidla. Jeho případ se týkal spojování asi 500 000 slov. Viděl, že při použití "normálních" bezchybných hashovacích technik, ukládajících vzory spojovníků, by bylo potřeba hodně paměti. Zjistil, že pomocí své techniky může většinu vyhledávání eliminovat. Například oblast hashování o velikosti pouze 15 % velikosti potřebné pro ideální bezchybné hashování stále eliminuje 85 % přístupů na disk.
Obecněji řečeno, pro 1% pravděpodobnost falešné pozitivity je zapotřebí méně než 10 bitů na prvek, nezávisle na velikosti nebo počtu prvků v souboru.
Otázky a odpovědi
Otázka: Co je to Bloomův filtr?
A: Bloomův filtr je datová struktura, která umožňuje počítačům zjistit, zda se daný prvek vyskytuje v množině. Používá k tomu hashovací funkce, které vypočítávají hashovací hodnotu každého přidaného prvku a porovnávají ji s ostatními prvky v množině.
Otázka: Jaký typ datové struktury je Bloomův filtr?
Odpověď: Bloomův filtr je pravděpodobnostní datová struktura, což znamená, že existuje možnost získání falešně pozitivních výsledků, ale ne falešně negativních.
Otázka: Kdo navrhl Bloomův filtr?
Odpověď: Bloomův filtr navrhl Edward Bloom v roce 1970.
Otázka: Jaký byl Edwardův příklad použití jeho techniky?
Odpověď: Edwardův příklad se týkal spojování asi 500 000 slov; zjistil, že pomocí své techniky může eliminovat většinu vyhledávání a snížit počet přístupů na disk o 15 %.
Otázka: Kolik bitů na prvek je potřeba pro 1% pravděpodobnost falešné pozitivity?
Odpověď: Pro 1% pravděpodobnost falešné pozitivity je zapotřebí méně než 10 bitů na prvek, nezávisle na velikosti nebo počtu prvků v množině.
Otázka: Je možné odstranit prvky z bloom filtru, jakmile byly přidány?
Odpověď: Ne, prvky lze do množiny pouze přidat, ale ne odebrat.
Otázka: Zvyšuje nebo snižuje přidání více prvků pravděpodobnost získání falešně pozitivního výsledku?
Odpověď: Přidání více prvků zvyšuje pravděpodobnost získání falešně pozitivního výsledku.
