imported>Mary Joanna: /* Anwendungen */ +sdhash => Fuzzy Hashing

2025-09-29T20:13:14Z

Anwendungen: +sdhash => Fuzzy Hashing

Neue Seite

Ein '''Bloom-Filter''' (benannt nach [[Burton Howard Bloom]]) ist eine [[Probabilistische Aussage|probabilistische]] [[Datenstruktur]], mit deren Hilfe sehr schnell festgestellt werden kann, welche Daten in einem [[Datenstrom]] schon einmal vorgekommen sind und welche erstmals auftreten. Hierzu wird mit einer geeigneten Zahl von [[Hash-Funktion]]en ein „Fingerabdruck“ des gelesenen [[Datensatz]]es in einer einzeiligen [[Hashtabelle]] hinterlassen.

1970 von [[Burton H. Bloom]] zur Rechtschreibkontrolle und zur [[Worttrennung]] am Zeilenende entwickelt, werden Bloomfilter heute oft bei der [[Datenbanksystem|Datenbankverwaltung]] und für das [[Routing]] in [[Netzwerk]]en eingesetzt. Im Gegensatz zu vergleichbaren [[Algorithmus|Algorithmen]] brauchen Bloom-Filter nur sehr wenig [[Speicherplatz]]. Für die Anwendbarkeit sind aber auch die folgenden Eigenheiten von entscheidender Bedeutung: Schlüsselwerte, die einmal in der Hashtabelle erfasst wurden, verbleiben dort. Weiterhin sind [[falsch positiv]]e Ergebnisse möglich, d. h., was der Filter akzeptiert, war mit hoher Wahrscheinlichkeit in den Schlüsselwerten enthalten; hingegen war definitiv nicht enthalten, was er abweist.

== Funktionsprinzip ==
[[Datei:Bloom filter.svg|mini|360px|Ein Beispiel eines Bloomfilters für die Menge {''x'', ''y'', ''z''}. Die farbigen Pfeile geben die Position im Bit-Array des Bloomfilters an. Das Element ''w'' ist nicht in der Menge {''x'', ''y'', ''z''} enthalten, da es Positionen umfasst, deren Wert 0 ist. In diesem Bild sind m=18 und k=3.]]
Ein Bloomfilter besteht aus einem ''m''-stelligen Bit-Array (welches zu Beginn mit Nullen gefüllt ist) und aus ''k'' unterschiedlichen Hashfunktionen mit einem Wertebereich von 0 bis ''m''-1. Hierbei ist vor allem wichtig, dass die von den Hashfunktionen gelieferten Werte [[Gleichverteilung|gleichverteilt]] sind, [[Kryptographische Hashfunktion|kryptografische Eigenschaften]] sind nicht gefordert. Aus diesem Grund werden häufig einfache und sehr schnelle Hashverfahren (z. B. [[MurmurHash]] oder [[FNV (Informatik)|FNV]]) eingesetzt.

Anfangs wird dem Bloomfilter sein [[Vokabular]] zugewiesen. Hierzu werden für jedes zu speichernde Wort mittels der ''k'' Hashfunktionen ''k'' Hashwerte ermittelt. Jeder der ermittelten Hashwerte entspricht einer Position im Bit-Array. Jede dieser Positionen wird nun auf 1 gesetzt, wobei es unerheblich ist, ob sich an dieser Position vorher eine 1 oder eine 0 befand.

Soll nun überprüft werden, ob ein beliebiger Wert im Vokabular enthalten ist, werden wiederum dessen ''k'' Hashwerte ermittelt. Enthält eine der ''k'' Stellen des Bit-Arrays des Filters eine 0, wo der Hash des zu prüfenden Wertes eine 1 hat, so ist sicher, dass der Wert nicht im Filter enthalten ist. Steht an jeder der ''k'' Stellen eine 1 im Filter, wo auch der zu prüfende Wert eine 1 hat, ist es sehr wahrscheinlich, dass der Wert im Filter gespeichert wurde. Ein Bloomfilter kann allerdings nie mit absoluter Gewissheit sagen, dass ein bestimmter Wert wirklich gespeichert ist, da bedingt durch [[Kollisionssicherheit|Kollisionen]] ein gewisses Risiko besteht, Werte irrtümlich als zugehörig einzuordnen ([[False positive|Falsch-positive Klassifikation]]). Dieses Risiko kann jedoch durch geeignete Wahl von ''k'', ''m'', und Kapazität des Filters (also der Höchstzahl zu speichernder Werte) vermindert werden.

Da eine bestimmte Position im Bit-Array durch das Hinzufügen von unterschiedlichen Werten auf 1 gesetzt worden sein kann, ist es bei herkömmlichen Bloomfiltern nicht möglich, einmal hinzugefügte Werte nachträglich zu löschen. Abhilfe schaffen hier so genannte [[Counting Bloomfilter|Zählende Bloomfilter]].

Hashfunktionen mit konstanter Bildmenge und variabler Quellmenge sind im Allgemeinen nicht [[Bijektivität|bijektiv]], weshalb es mit klassischen Bloomfiltern unmöglich ist, die enthaltenen Werte zurückzugewinnen. Es kann nur mit einer gewissen (ggf. hohen) Wahrscheinlichkeit ermittelt werden, ob ein vorgegebenes Wort enthalten ist oder nicht. Dies ist bei vielen Anwendungsgebieten ein großer Nachteil, da z. B. auch die Suche mit Platzhaltern unmöglich wird.

Bloomfilter können von Nutzen sein, wenn sensible Daten gespeichert werden sollen. Beispielsweise kann das Verfahren dazu verwendet werden, um bei einer Fahndung sicher auszuschließen, dass eine gerade überprüfte Person gesucht wird, ohne dabei Personendaten im Klartext vorhalten zu müssen.

== Beispiel ==
Angenommen, der Filter hat eine Länge von 10 Bit (''m=10'') und besitzt 3 Hashfunktionen (''k=3''). Das Vokabular bestehe aus den Wörtern „der“, „die“ und „das“.

Zunächst ist der Filter leer:
0 0 0 0 0 0 0 0 0 0

Nun werden die Wörter nacheinander zum Filter hinzugefügt. Dazu werden für jedes der Wörter die Ergebnisse der 3 Hashfunktionen ermittelt.
; „der“:Angenommen, die Hashfunktionen liefern für das Wort „der“ die Werte 8, 2 und 4. Es werden also die Positionen 8, 2 und 4 im Array auf 1 gesetzt. Das Array sieht jetzt wie folgt aus:

0 '''1''' 0 '''1''' 0 0 0 '''1''' 0 0

; „die“:Angenommen, die Hashfunktionen liefern für das Wort „die“ die Werte 7, 4 und 1. Es werden also die Positionen 7, 4 und 1 im Array auf 1 gesetzt. Das Array sieht jetzt wie folgt aus:

'''1''' 1 0 '''1''' 0 0 '''1''' 1 0 0

; „das“:Angenommen, die Hashfunktionen liefern für das Wort „das“ die Werte 9, 2 und 8. Es werden die Positionen 9, 2 und 8 im Array auf 1 gesetzt, womit das Array wie folgt aussieht:

1 '''1''' 0 1 0 0 1 '''1''' '''1''' 0
Es soll nun die Existenz verschiedener Wörter im Filter überprüft werden.
; „wer“: Für das Wort „wer“ wird angenommen, dass sich bei der Berechnung der Hashfunktionen die Werte 10, 1 und 3 ergeben. Die Positionen 10 und 3 im Array enthalten eine 0, somit ist das Wort nicht im Filter enthalten, was korrekt ist.
; „das“: Da die Hashfunktion für gleiche Eingaben das gleiche Ergebnis liefert, ergeben sich für das Wort „das“ die gleichen Werte wie zuvor beim Einfügen, nämlich 9, 2 und 8. Alle diese Positionen sind im Array auf 1 gesetzt, das Wort könnte also im Filter gespeichert sein, was auch der Fall ist.
; „sie“: Für das Wort „sie“ wird angenommen, dass sich bei der Berechnung der Hashfunktionen die Werte 9, 1, 4 ergeben. Da alle diese Positionen im Array auf 1 gesetzt sind, könnte das Wort im Filter gespeichert sein. Da das Wort „sie“ aber oben nicht dem Filter hinzugefügt wurde, handelt es sich um ein falsch positives Ergebnis.

Es sollte bedacht werden, dass dies ein bewusst konstruiertes Extrembeispiel darstellt, welches noch keine Schlüsse auf die Qualität des Verfahrens zulässt.

== Varianten ==
In der wissenschaftlichen Literatur wurden zahlreiche Varianten und Erweiterungen von Bloomfiltern vorgeschlagen. Einen guten Überblick bietet der Artikel ''Network applications of bloom filters: A survey''<ref>{{Literatur |Autor=Andrei Broder, Michael Mitzenmacher |Titel=Network applications of bloom filters: A survey |Sammelwerk=Internet Mathematics |Datum=2002 |Seiten=636-646 |Online=https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.98 |Abruf=2013-05-21}}</ref> von Broder und Mitzenmacher. Zu diesen Erweiterungen zählen beispielsweise ''[[Counting Bloomfilter]]''<ref>{{Literatur |Autor=Michael Mitzenmacher |Titel=Compressed bloom filters |Sammelwerk=IEEE/ACM Transactions on Networking |Datum=2002 |Seiten=604-612 |DOI=10.1109/TNET.2002.803864}}</ref>, die auf Kosten eines höheren Platzbedarfs das Entfernen von Elementen erlauben. Andere Bloomfilter-Varianten versuchen die Vorteile des Bloomfilters auf [[Datenstrom|Stream]]-Daten zu erweitern (z. B. ''Stable Bloomfilter''<ref>{{Literatur |Autor=Fan Deng, Davood Rafiei |Titel=Approximately detecting duplicates for streaming data using stable bloom filters |Sammelwerk=Proceedings of the 2006 ACM SIGMOD international conference on Management of data |Datum=2006 |Seiten=25-36 |DOI=10.1145/1142473.1142477}}</ref>), während weitere Varianten Optionen für probabilistische Multiplizitätsabschätzungen von eingefügten Elementen bieten (z. B. ''Bloomier Filter''<ref>{{Literatur |Autor=[[Bernard Chazelle]], Joe Kilian, Ronitt Rubinfeld, Ayellet Tal |Titel=The Bloomier filter: an efficient data structure for static support lookup tables |Sammelwerk=Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms |Datum=2004 |Seiten=30-39 |Online=http://dl.acm.org/citation.cfm?id=982797 |Abruf=2013-05-21}}</ref>).

Im Bereich der Datenbanken werden auch ''Buffered Bloom Filter'' verwendet, um insbesondere bei Solid State Discs ([[Solid-State-Drive|SSD]]) häufig zugegriffene Speicherstellen ermitteln zu können<ref>{{Literatur |Autor=Mustafa Canim, George A. Mihaila, Bishwaranjan Bhattacharjee |Titel=Buffered Bloom Filters on Solid State Storage |Sammelwerk=First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS) |Datum=2010 |Online=https://www.vldb.org/archives/website/2010/proceedings/files/vldb_2010_workshop/ADMS_2010/adms10-canim.pdf |Abruf=2019-04-23}}</ref>.

== Anwendungen ==

* Der [[Proxyserver]] [[Squid]] verwendet Bloomfilter zum Abgleichen von [[Cache]]-Einträgen.<ref>{{Internetquelle |url=https://wiki.squid-cache.org/SquidFaq/CacheDigests#What_is_the_theory_behind_Cache_Digests.3F |titel=SquidFaq/CacheDigests |abruf=2013-05-21}}</ref>
* Die [[NoSQL|NoSQL-Datenbanken]] [[Bigtable]], [[Apache HBase]] und [[Apache Cassandra]] verwenden Bloomfilter zur Vermeidung von teuren Festplattenzugriffen bei Abfragen auf nicht-existierende Schlüsselwerte.
* Der [[Webbrowser]] [[Google Chrome]] pflegt einen Bloomfilter mit den Signaturen gefährlicher Webseiten und überprüft bei Eingabe einer URL, ob diese in diesem Filter enthalten ist.<ref>{{Internetquelle |autor=Alex Yakunin |url=http://blog.alexyakunin.com/2010/03/nice-bloom-filter-application.html |titel=Nice Bloom filter application |archiv-url=https://web.archive.org/web/20101027012345/http://blog.alexyakunin.com/2010/03/nice-bloom-filter-application.html |archiv-datum=2010-10-27 |abruf=2013-05-21 |kommentar=über die Anwendung von Bloomfiltern für Safe Browsing in Google Chrome |offline=1}}</ref>
* Die [[Kryptowährung]] [[Bitcoin]] nutzt Bloomfilter zur Verifikation von Transaktionen in lightweight Clients (SPV)
* Das [[Fuzzy Hashing|Fuzzy-Hashing]]-Tool ''sdhash'' basiert auf Bloomfiltern.

== Literatur ==
* {{Literatur
|Autor=Burton H. Bloom
|Titel=Space/Time Trade-offs in Hash Coding with Allowable Errors
|Sammelwerk=Communications of the ACM
|Band=13
|Nummer=7
|Datum=1970-07
|ISSN=0001-0782
|Seiten=422–426
|Online=https://crystal.uta.edu/~mcguigan/cse6350/papers/Bloom.pdf
|Format=PDF
|KBytes=}}
* {{Literatur
|Autor=Michael Mitzenmacher, Eli Upfal
|Titel=Probability and Computing: Randomized Algorithms and Probabilistic Analysis
|Verlag=Cambridge University Press
|Datum=2005
|ISBN=0-521-83540-2
|Online={{Google Buch |BuchID=0bAYl6d7hvkC |SeitenID=PR13}}}}

== Einzelnachweise ==
<references />

== Weblinks ==
* [https://github.com/DivineTraube/Orestes-Bloomfilter Orestes Bloomfilter] – Open-Source Java-Implementierung von Bloomfiltern und Counting Bloomfiltern mit umfangreichen Verteilungs-, Persisitierungs- und Hashingoptionen.
* [https://libhashish.sourceforge.net/ Libhashish] – Bloomfilter-Bibliothek für C und C++
* [https://matthias.vallentin.net/blog/2011/06/a-garden-variety-of-bloom-filters/ A Garden Variety of Bloom filters] – Umfassende, englischsprachliche Erklärung verschiedener Bloomfilter-Varianten
* [https://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html Tabelle mit False-Positive Rates für verschiedene Konfigurationen]

[[Kategorie:Datenstruktur]]
[[Kategorie:Hash]]

Bloomfilter - Versionsgeschichte

imported>Mary Joanna: /* Anwendungen */ +sdhash => Fuzzy Hashing