Bloomův filtr - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

2022-08-14T14:51:07Z

Nahrazení textu „</math>“ textem „\)</big>“

← Starší verze		Verze z 14. 8. 2022, 14:51
Řádka 53:		Řádka 53:

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

	'''Dotaz''' na nějaký prvek ''x'' (tj. otázka, zda prvek ''x'' patří do množiny anebo nepatří) funguje		'''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:		podle následujícího algoritmu:
-	# Vypočítejme hodnotu každé z ''k'' hašovacích funkcí (označme tyto hašovací funkce <big>\(h_1 \ldots h_k</~~math~~>) pro argument ''x'' (stejně jako při vkládání).	+	# Vypočítejme hodnotu každé z ''k'' hašovacích funkcí (označme tyto hašovací funkce <big>$h_1 \ldots h_k$</big>) pro argument ''x'' (stejně jako při vkládání).
-	# Takto dostaneme hodnoty <big>\(h_1(x), h_2(x), \ldots h_k(x)</~~math~~>, teda nejvíc ''k'' různých hodnot	+	# Takto dostaneme hodnoty <big>$h_1(x), h_2(x), \ldots h_k(x)$</big>, teda nejvíc ''k'' různých hodnot
	(stejně jako při vkládání).		(stejně jako při vkládání).
-	# Podíváme se na hodnoty pole na pozicích <big>\(h_1(x), h_2(x), \ldots h_k(x)</~~math~~>. Pokud je aspoň jedna z	+	# Podíváme se na hodnoty pole na pozicích <big>$h_1(x), h_2(x), \ldots h_k(x)$</big>. Pokud je aspoň jedna z
	nich 0, víme s určitostí říct, že prvek ''x'' se v množině nenachází, protože jinak by byly všechny tyto		nich 0, víme 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		hodnoty při jeho vložení nastaveny na 1. Pokud jsou všechny tyto hodnoty 1, potom sice s určitostí nelze

Sysop: Nahrazení textu „ $“ textem „$ \(“

2022-08-14T14:48:12Z

Nahrazení textu „<math>“ textem „<big>\(“

← Starší verze		Verze z 14. 8. 2022, 14:48
Řádka 53:		Řádka 53:

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

	'''Dotaz''' na nějaký prvek ''x'' (tj. otázka, zda prvek ''x'' patří do množiny anebo nepatří) funguje		'''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:		podle následujícího algoritmu:
-	# Vypočítejme hodnotu každé z ''k'' hašovacích funkcí (označme tyto hašovací funkce <~~math~~>h_1 \ldots h_k</math>) pro argument ''x'' (stejně jako při vkládání).	+	# Vypočítejme hodnotu každé z ''k'' hašovacích funkcí (označme tyto hašovací funkce <big>\(h_1 \ldots h_k</math>) pro argument ''x'' (stejně jako při vkládání).
-	# Takto dostaneme hodnoty <~~math~~>h_1(x), h_2(x), \ldots h_k(x)</math>, teda nejvíc ''k'' různých hodnot	+	# Takto dostaneme hodnoty <big>\(h_1(x), h_2(x), \ldots h_k(x)</math>, teda nejvíc ''k'' různých hodnot
	(stejně jako při vkládání).		(stejně jako při vkládání).
-	# Podíváme se na hodnoty pole na pozicích <~~math~~>h_1(x), h_2(x), \ldots h_k(x)</math>. Pokud je aspoň jedna z	+	# Podíváme se na hodnoty pole na pozicích <big>\(h_1(x), h_2(x), \ldots h_k(x)</math>. Pokud je aspoň jedna z
	nich 0, víme s určitostí říct, že prvek ''x'' se v množině nenachází, protože jinak by byly všechny tyto		nich 0, víme 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		hodnoty při jeho vložení nastaveny na 1. Pokud jsou všechny tyto hodnoty 1, potom sice s určitostí nelze

Sysop: /* Popis algoritmu */ Typo

2014-08-06T09:06:29Z

Popis algoritmu: Typo

← Starší verze		Verze z 6. 8. 2014, 09:06
Řádka 36:		Řádka 36:

	== Popis algoritmu ==		== Popis algoritmu ==
-	[[Soubor:Bloom filter.png\|right\|~~240px~~\|thumb\|Příklad Bloomova filtru reprezentujícího	+	[[Soubor:Bloom filter.png\|right\|400px\|thumb\|Příklad Bloomova filtru reprezentujícího
	[[množina\|množinu]] {''x'', ''y'', ''z''}. Barevné šipky ukazují na pozice v bitové poli, kde jsou na		[[množina\|množinu]] {''x'', ''y'', ''z''}. 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ákladě [[hašovací funkce\|hašovacích funkcí]] přiřazeny všechny prvky množiny. Množina {''x'', ''y'',

Sysop: + Masivní vylepšení

2014-08-06T09:02:00Z

+ Masivní vylepšení

← Starší verze		Verze z 6. 8. 2014, 09:02
Řádka 1:		Řádka 1:
-	{{~~Wikipedia~~-cs\|Bloomův filtr~~\|700}}~~	+	'''Bloomův filtr''', pojmenovaný podle [[Burton Howard Bloom\|Burtona Howarda Blooma]], který ho objevil v
		+	roce [[1970]],<ref>{{cite web\|author=[[Donald Knuth]]\|title=[[The Art of Computer Programming]], Errata for
		+	Volume 3 (2nd ed.)\|url=http://www-cs-faculty.stanford.edu/~knuth/err3.textxt}}</ref> je prostorově
		+	efektivní pravděpodobnostní [[datová struktura]], která se používá na ověřování příslušnosti
		+	[[prvek\|prvků]] do [[množina\|množiny]]. Protože je tato struktura pravděpodobnostní, můžou 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. 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.<ref>{{Citace sborníku
		+	\| meno = Fay\| priezvisko = Chang
		+	\| meno2 = Jeffrey\| priezvisko2 = Dean
		+	\| meno3 = Sanjay \| priezvisko3 = Ghemawat
		+	\| meno4 = Wilson \| priezvisko4 = Hsieh
		+	\| meno5 = Deborah \| priezvisko5 = Wallach
		+	\| meno6 = Mike \| priezvisko6 = Burrows
		+	\| meno7 = Tushar \| priezvisko7 = Chandra
		+	\| meno8 = Andrew \| priezvisko8 = Fikes
		+	\| meno9 = Robert \| priezvisko9 = Gruber
		+	\| Příspěvek = Bigtable: A Distributed Storage System for Structured Data
		+	\| Titul = Seventh Symposium on Operating System Design and Implementation
		+	\| Rok = 2006 \| URL = http://labs.google.com/papers/bigtable.html}}.</ref> Bloomovy filtry používá
		+	také [[proxy server]] [[Squid]] pro tzv. ''cache digests'' <ref name="Wessels172">{{cite book\| last=Wessels
		+	\| first=Duane \| year=2004 \| month=January \| chapter=10.7 Cache Digests \| title=Squid: The Definitive Guide
		+	\| edition=1st \| publisher=O'Reilly Media \| isbn=0596001622 \| page=172 \| quote=Cache Digests are based on a
		+	technique first published by Pei Cao, called Summary Cache. The fundamental idea is to use a Bloom filter
		+	to represent the cache contents.}}</ref> a archivační systém [[Venti]] na detekování předtím vloženého
		+	obsahu.<ref>http://plan9.bell-labs.com/magic/man2html/8/venti</ref>
		+
		+	== Popis algoritmu ==
		+	[[Soubor:Bloom filter.png\|right\|240px\|thumb\|Příklad Bloomova filtru reprezentujícího
		+	[[množina\|množinu]] {''x'', ''y'', ''z''}. 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žina\|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í funkce\|hašovacích
		+	funkcí]], přičemž každá z nich (při zachování požadavku [[rovnoměrné hašování\|rovnoměrného hašování]])
		+	přiřadí každému prvku [[univerzum\|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 <math>h_1 \ldots h_k</math>) pro argument ''x''.
		+	# Takto dostaneme hodnoty <math>h_1(x), h_2(x), \ldots h_k(x)</math>, teda nejvíc ''k'' různých hodnot.
		+	# Nastavme hodnoty pole na pozicích <math>h_1(x), h_2(x), \ldots h_k(x)</math> 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 <math>h_1 \ldots h_k</math>) pro argument ''x'' (stejně jako při vkládání).
		+	# Takto dostaneme hodnoty <math>h_1(x), h_2(x), \ldots h_k(x)</math>, 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 <math>h_1(x), h_2(x), \ldots h_k(x)</math>. Pokud je aspoň jedna z
		+	nich 0, víme 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 můžou 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é [[výpočtová složitost\|časově náročné]] výpočty). 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é číslo\|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 víme 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ří, víme 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žina\|množiny]]. Pokud bychom se totiž pokusili všech ''k'' hodnot daných vzpomínanými [[hašovací funkce\|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. 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 ==
		+	<references />
		+	== Externí odkazy ==
		+	* [http://portal.acm.org/citation.cfm?id=362692&dl=ACM&coll=portal Originální článek (anglicky)]
		+	* [http://en.literateprograms.org/Bloom_filter_(C) Implementace Bloomova filtru] v jazyce [[C (programovací jazyk)\|C]] (anglicky)
		+	* [http://wwwse.inf.tu-dresden.de/xsiena/bloom_filter Implementace Bloomova filtru] v jazyce [[Java (programovací jazyk)\|Java]] (anglicky)
		+	* [http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf Less Hashing, Same Performance: Building a Better Bloom Filter – článek o optimalizaci Bloomových filtrů (anglicky)]
		+
		+
		+	{{Commonscat}}{{Článek z Wikipedie}}
	[[Kategorie:Hašování]]		[[Kategorie:Hašování]]
	[[Kategorie:Vyhledávací algoritmy]]		[[Kategorie:Vyhledávací algoritmy]]
	[[Kategorie:Datové struktury]]		[[Kategorie:Datové struktury]]

Sysop: 1 revizi

2013-11-30T16:23:29Z

1 revizi

← Starší verze

Verze z 30. 11. 2013, 16:23

Sysop: + Výrazné vylepšení

2012-10-22T01:08:00Z

+ Výrazné vylepšení

Nová stránka

{{Wikipedia-cs|Bloomův filtr|700}}

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