Bloomův filtr

Bloomův filtr, pojmenovaný podle Burtona Howarda Blooma, který ho objevil v roce 1970, je prostorově efektivní pravděpodobnostní datová struktura, která se používá na ověřování příslušnosti prvků do množiny. Protože je tato struktura pravděpodobnostní, mohou při tomto ověřování nastat chyby. Při této chybě se o prvku, který ve skutečnosti do dané množiny nepatří, dozvíme, že tam patří, ale nikdy ne naopak. To znamená, že při odpovědi, že daný prvek do množiny nepatří, se dá na Bloomův filtr spolehnout na 100%. Pravděpodobnost chyby roste s větším počtem prvků v dané množině (při pevné velikosti reprezentace).

Bloomův filtr se používá v různých aplikacích. Například, databázový systém Big Table od společnosti Google používá Bloomův filtr na redukování vyhledávání na disku. +more Před tím, než vůbec zpracuje požadavek, ověří si pomocí Bloomova filtru, zda daný řádek anebo sloupec databáze existuje (tj. zda patří do množiny reprezentované Bloomovým filtrem). Kvůli charakteru možných chyb při použití Bloomova filtru se nikdy nemůže stát, že by "přehlédnul" existující záznam. Tím se výrazně zvyšuje výkon databázového systému (při neexistujících záznamech nemusí pokaždé číst z disku) při zachování stoprocentní spolehlivosti. Bloomovy filtry používá také proxy server Squid pro tzv. cache digests a archivační systém Venti na detekování předtím vloženého obsahu.

Popis algoritmu

+more_Barevné_šipky_ukazují_na_pozice_v_bitové_poli,_kde_jsou_na základě_hašovací_funkce|hašovacích_funkcí_přiřazeny_všechny_prvky_množiny. _Množina_{x,_y, z}_neobsahuje_prvek_w,_protože_existuje_taková_hašovací_funkce,_které_hodnota_je_pro_vstup_w rovná_0. _V_tomto_příklade_je_m=18_(velikost_pole)_a_k=3_(počet_hašovacích_funkcí). _Barva_šipek určuje_vstup_hašovací_funkce_(teda_prvek_univerzum'>univerza), pro každou barvu jsou 3 šipky odpovídající třem hašovacím funkcím (k = 3). .

Prázdný Bloomův filtr (odpovídající prázdné množině) je bitové pole délky m bitů, přičemž všechny hodnoty pole jsou nastaveny na 0.

Na práci s Bloomovým filtrem je potřebné mít definovaných k různých hašovacích funkcí, přičemž každá z nich (při zachování požadavku rovnoměrného hašování) přiřadí každému prvku univerza (množina všech prvků, o kterých potenciálně můžeme chtít zjišťovat jejich příslušnost do množiny) jednu z m pozic pole.

Vložení prvku x do reprezentované množiny funguje podle následujícího algoritmu: # Vypočítejme hodnotu každé z k hašovacích funkcí (označme tyto hašovací funkce h_1 \ldots h_k) pro argument x. # Takto dostaneme hodnoty h_1(x), h_2(x), \ldots h_k(x), teda nejvíc k různých hodnot. +more # Nastavme hodnoty pole na pozicích h_1(x), h_2(x), \ldots h_k(x) na 1.

Dotaz na nějaký prvek x (tj. otázka, zda prvek x patří do množiny anebo nepatří) funguje podle následujícího algoritmu: # Vypočítejme hodnotu každé z k hašovacích funkcí (označme tyto hašovací funkce h_1 \ldots h_k) pro argument x (stejně jako při vkládání). +more # Takto dostaneme hodnoty h_1(x), h_2(x), \ldots h_k(x), teda nejvíc k různých hodnot (stejně jako při vkládání). # Podíváme se na hodnoty pole na pozicích h_1(x), h_2(x), \ldots h_k(x). Pokud je aspoň jedna z nich 0, můžeme s určitostí říct, že prvek x se v množině nenachází, protože jinak by byly všechny tyto hodnoty při jeho vložení nastaveny na 1. Pokud jsou všechny tyto hodnoty 1, potom sice s určitostí nelze říct nic, ale aspoň pro menší počet prvků v množině je relativně vysoká pravděpodobnost, že prvek x se v množině nachází. Proto je výstupem algoritmu zjištění, že prvek se v množině nachází, je potřeba ale počítat s možností chyby.

Protože při dotazech na prvky mohou vznikat chyby, Bloomovy filtry se v praxi používají obzvlášť tehdy, když chyba tohoto druhu nemůže způsobit problém. Teda například v této modelové situaci: máme nějakou proceduru, která na základě nějakého vstupu vykoná nějakou proceduru (typicky nějaké časově náročné výpočty). +more Výpočet ale může proběhnout úspěšně jen v případě, pokud byl vstup ještě před tímto požadavkem uživatelem vložen do nějaké databáze informací (teda např. k rodnému číslu, které budeme považovat za vstup, musíme mít v databázi jméno, příjmení,. ). V takovém případě lze říct, že vstup bude patřit do množiny, pokud o něm v dané databázi existuje záznam, v opačném případě do ní nebude patřit. V případě, že dokážeme ještě před spuštěním výpočtu určit, že vstup do této množiny nepatří, umíme ušetřit náklady na vykonání tohoto výpočtu. Na to lze použít Bloomův filtr. Pokud nastane chyba, neznamená to velký problém, protože fakt, že vstup do množiny nepatří, dokážeme zjistit i po vykonání výpočtu (pouze to bude stát nějaký výpočtový čas). V mnoha případech však chyba nenastane, a co je podstatné, nikdy nenastane v případě, že vstup skutečně do množiny patří. Bloomův filtr tedy, jak napovídá jeho název, dokáže odfiltrovat poměrně velké množství vstupů, pro které bychom výpočet spouštěli marně.

Omezení Bloomových filtrů

Asi nejpodstatnějším omezením Bloomových filtrů je, že z pochopitelných důvodů nepodporují odebírání prvků z množiny. Pokud bychom se totiž pokusili všech k hodnot daných vzpomínanými hašovacími funkcemi pro prvek x nastavit na 0, mohlo by se stát, že bychom nedopatřením odebrali také jiný prvek - libovolný prvek y, který je prvkem množiny a současně hodnota aspoň jedné hašovací funkce má pro vstup y stejnou hodnotu jako některá z těchto k hodnot. +more Tím by se ale porušila základní vlastnost Bloomových filtrů, že pokud prvek patří do množiny, výsledkem dotazu je vždy kladná odpověď.

Reference

Externí odkazy

[url=http://portal. acm. +moreorg/citation. cfm. id=362692&dl=ACM&coll=portal]Originální článek[/url] * [url=http://en. literateprograms. org/Bloom_filter_(C)]Implementace Bloomova filtru[/url] v jazyce C * [url=https://web. archive. org/web/20111001233540/http://wwwse. inf. tu-dresden. de/xsiena/bloom_filter]Implementace Bloomova filtru[/url] v jazyce Java * [url=https://web. archive. org/web/20090131053735/http://www. eecs. harvard. edu/~kirsch/pubs/bbbf/esa06. pdf]Less Hashing, Same Performance: Building a Better Bloom Filter[/url] - článek o optimalizaci Bloomových filtrů.

Kategorie:Hašování Kategorie:Vyhledávací algoritmy Kategorie:Datové struktury