Bloomfilter
Ein Bloomfilter ist eine Datenstruktur, die es Computern ermöglicht zu sehen, ob ein bestimmtes Element in einer Menge vorkommt. Bloom-Filter verwenden dazu Hash-Funktionen. Für jedes Element, das hinzugefügt wird, wird ein Hash-Wert berechnet. Wenn ein neues Element hinzugefügt wird, wird sein Hash-Wert mit dem der anderen Elemente in der Menge verglichen. Ein Bloom-Filter ist eine probabilistische Datenstruktur. Es ist möglich, ein falsches Positiv zu erhalten, aber nicht ein falsches Negativ. Mit anderen Worten, eine Abfrage gibt entweder "möglicherweise im Satz" oder "definitiv nicht im Satz" zurück. Elemente können der Menge hinzugefügt, aber nicht entfernt werden. Für jedes hinzugefügte Element wächst die Wahrscheinlichkeit, ein falsches positives Ergebnis zu erhalten.
Edward Bloom schlug 1970 den Bloom-Filter vor. In dem Artikel nimmt Bloom an, dass es einen Algorithmus zur Silbentrennung von Wörtern am Ende einer Zeile gibt. Dem Beispiel zufolge haben die meisten Wörter einfache Silbentrennungsmuster. Aber bei etwa 10 % der Wörter sind zeitaufwändige Nachschlagen erforderlich, um die richtige Regel zu finden. Sein Fall war der der Silbentrennung von etwa 500.000 Wörtern. Er sah, dass die Verwendung der "normalen" fehlerfreien Hashing-Techniken, bei der die Trennungsmuster gespeichert werden, sehr viel Speicherplatz erfordern würde. Er stellte fest, dass er mit seiner Technik die meisten Suchvorgänge eliminieren konnte. Beispielsweise eliminiert ein Hash-Bereich, der nur 15 % der Größe hat, die ein idealer fehlerfreier Hash benötigt, immer noch 85 % der Plattenzugriffe.
Allgemeiner ausgedrückt sind weniger als 10 Bits pro Element für eine falsch-positive Wahrscheinlichkeit von 1% erforderlich, unabhängig von der Größe oder Anzahl der Elemente in der Menge.
Fragen und Antworten
F: Was ist ein Bloom-Filter?
A: Ein Bloom-Filter ist eine Datenstruktur, mit der Computer feststellen können, ob ein bestimmtes Element in einer Menge vorkommt. Er verwendet dazu Hash-Funktionen, indem er den Hash-Wert jedes hinzugefügten Elements berechnet und ihn mit den anderen Elementen in der Menge vergleicht.
F: Welche Art von Datenstruktur ist ein Bloom-Filter?
A: Ein Bloom-Filter ist eine probabilistische Datenstruktur, d.h. es besteht die Möglichkeit, dass er falsch-positive Ergebnisse liefert, aber keine falsch-negativen.
F: Wer hat den Bloom-Filter vorgeschlagen?
A: Edward Bloom schlug den Bloom-Filter im Jahr 1970 vor.
F: Was war Edwards Beispiel für die Anwendung seiner Technik?
A: Edwards Beispiel war die Silbentrennung von etwa 500.000 Wörtern. Er fand heraus, dass er mit seiner Technik die meisten Suchvorgänge eliminieren und die Festplattenzugriffe um 15% reduzieren konnte.
F: Wie viele Bits pro Element sind für eine Falsch-Positiv-Wahrscheinlichkeit von 1% erforderlich?
A: Weniger als 10 Bits pro Element sind für eine Wahrscheinlichkeit von 1% falsch positiv erforderlich, unabhängig von der Größe oder der Anzahl der Elemente in der Menge.
F: Ist es möglich, Elemente aus einem Bloomfilter zu entfernen, nachdem sie hinzugefügt wurden?
A: Nein, Elemente können der Menge nur hinzugefügt, aber nicht entfernt werden.
F: Erhöht oder verringert das Hinzufügen weiterer Elemente die Wahrscheinlichkeit eines falsch positiven Ergebnisses?
A: Wenn Sie mehr Elemente hinzufügen, erhöht sich die Wahrscheinlichkeit eines falsch positiven Ergebnisses.
