Effiziente Set-Mitgliedschaft mit Bloom Filter

Der Bloom-Filter ist eine Datenstruktur, die dazu dient, zu testen, ob ein Element Mitglied einer Menge ist. Es wird in verschiedenen Anwendungen wie Rechtschreibprüfung, Datenbankindizierung und Netzwerkroutern verwendet, die eine schnelle und speichereffiziente Methode zum Testen der Satzmitgliedschaft erfordern. Bloom-Filter sind probabilistische Datenstrukturen, was bedeutet, dass sie möglicherweise falsch-positive, aber niemals falsch-negative Ergebnisse erzeugen.

Bevor wir Bloom Filter erklären, wollen wir zunächst das Hashing verstehen. Hashing ist eine Technik zum Reduzieren einer großen Datenmenge in einen kleineren Hash-Wert fester Größe, wobei die Wahrscheinlichkeit gering ist, dass zwei Datenwerte denselben Hash-Wert erzeugen (Kollision).

Implementierung

Bloom-Filter werden als Bit-Array aus N Bits implementiert, die zu Beginn alle auf 0 gesetzt sind. Das Bit-Array stellt die Menge dar und jedes Element wird K-mal mit verschiedenen Hash-Funktionen gehasht. Die resultierenden K-Hash-Werte werden verwendet, um die entsprechenden Bits im Bit-Array auf 1 zu setzen.

Um die Zugehörigkeit zu prüfen, wird das Element erneut K-mal gehasht und die resultierenden Bits im Bit-Array überprüft. Wenn alle K Bits auf 1 gesetzt sind, wird das Element als Mitglied der Menge betrachtet, obwohl es möglich ist, dass das Element nicht tatsächlich in die Menge eingefügt wurde, was zu einem falschen Positiv führt.

Die Wahrscheinlichkeit eines falsch positiven Ergebnisses wird durch die Größe des Bit-Arrays N und die Anzahl der Hash-Funktionen K bestimmt.

Anwendungsfall

Angenommen, wir müssen ein Benutzerregistrierungssystem entwerfen, das es Benutzern ermöglicht, sich mit einem eindeutigen Benutzernamen und Passwort zu registrieren. Um zu überprüfen, ob ein ausgewählter Benutzername verfügbar ist, können wir die gesamte Datenbank durchsuchen und nach einer Übereinstimmung suchen. Dies ist jedoch eine langsame und speicherintensive Methode. Eine bessere Lösung ist die Verwendung eines Bloom-Filters.

Der Bloom-Filter wird mit einem großen Bit-Array und einer Reihe von Hash-Funktionen initialisiert. Das Bit-Array wird zunächst ausschließlich auf Nullen gesetzt und die Hash-Funktionen werden so ausgewählt, dass die Eingabewerte gleichmäßig über das Bit-Array verteilt werden.

Wenn ein Benutzer versucht, sich zu registrieren, wird der gewählte Benutzername durch die Hash-Funktionen geleitet, die eine Reihe von Indizes im Bit-Array generieren. Das System prüft dann den Wert der Bits an diesen Indizes. Wenn alle Bits auf eins gesetzt sind, geht das System davon aus, dass der Benutzername bereits verwendet wird, und lehnt die Registrierung ab. Wenn eines der Bits auf Null gesetzt ist, kann das System bestätigen, dass der Benutzername nicht verwendet wird, und fährt mit der Registrierung fort.

Nachdem die Registrierung abgeschlossen ist, setzt das System die Bits an den von den Hash-Funktionen generierten Indizes auf eins und zeigt damit an, dass der Benutzername jetzt verwendet wird.

Dies ist ein einfaches Beispiel dafür, wie ein Bloom-Filter verwendet werden kann, um effizient nach festgelegten Mitgliedschaften in einem Benutzernamen-Registrierungssystem zu suchen. Auch wenn die Wahrscheinlichkeit eines falsch positiven Ergebnisses gering ist, kann die Verwendung einer sekundären Prüfung diese Einschränkung effektiv mildern und die Genauigkeit der Ergebnisse sicherstellen.

Beispiel

Lassen Sie uns eine Beispielimplementierung eines Bloom-Filters in einem System zur Registrierung von Benutzernamen testen.

Wir betrachten einen Bloom-Filter mit einem Bit-Array der Länge 10 und drei Hash-Funktionen.
Zunächst sind alle Bits des Bit-Arrays auf 0 gesetzt.

Bit Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

h1("Rohit") = 8
h2("Rohit") = 2
h3("Rohit") = 7

Nachdem die Registrierung abgeschlossen ist, setzt das System die Bits an den von den Hash-Funktionen generierten Indizes auf eins.

Bit Array: [0, 0, 1, 0, 0, 0, 0, 1, 1, 0]

h1("Mohit") = 2
h2("Mohit") = 8
h3("Mohit") = 5

Nachdem die Registrierung abgeschlossen ist, setzt das System die Bits an den von den Hash-Funktionen generierten Indizes auf eins.

Bit Array: [0, 0, 1, 0, 0, 1, 0, 1, 1, 0]

h1("Rahul") = 2
h2("Rahul") = 5
h3("Rahul") = 7

Dies ist ein Beispiel für falsch positive Ergebnisse, die bei der Verwendung von Bloom-Filtern auftreten können. Um dies zu umgehen, führt das System eine sekundäre Prüfung anhand der Datenbank durch, um die Verfügbarkeit des Benutzernamens zu bestätigen.

Vor-und Nachteile

Einer der Hauptvorteile des Bloom-Filters ist seine Platzeffizienz. Im Vergleich zu anderen Datenstrukturen wie Hash-Tabellen oder binären Suchbäumen benötigt es deutlich weniger Speicher zum Speichern der Mengenelemente. Ein weiterer Vorteil ist der zeitkonstante Betrieb. Die zeitliche Komplexität des Mitgliedschaftstests beträgt O(K), unabhängig davon, ob K die Anzahl der Hash-Funktionen ist, unabhängig von der Anzahl der Elemente in der Menge.

Aufgrund der probabilistischen Natur des Bloom-Filters eignet er sich jedoch nicht für Anwendungen, bei denen falsch positive Ergebnisse nicht akzeptabel sind. In solchen Fällen sollten alternative Datenstrukturen wie Hash-Tabellen oder binäre Suchbäume verwendet werden.

Die Falsch-Positiv-Rate eines Bloom-Filters kann durch Erhöhen der Größe des Bit-Arrays oder der Anzahl der Hash-Funktionen reduziert werden. Allerdings erhöht die Vergrößerung des Bit-Arrays auch den Speicherbedarf des Filters. Andererseits erhöht die Erhöhung der Anzahl der Hash-Funktionen die zeitliche Komplexität des Mitgliedschaftstests. Bei der Verwendung von Bloom-Filtern ist es wichtig, den optimalen Kompromiss zwischen räumlicher und zeitlicher Komplexität zu finden.

Allgemeine Verwendungen

Bloom-Filter werden aufgrund ihrer Effizienz und ihres probabilistischen Charakters in einer Vielzahl anspruchsvoller Designanwendungen eingesetzt. Einige der häufigsten Anwendungsfälle sind:
Web-Suchmaschinen : Bloom-Filter können verwendet werden, um URLs von Seiten zu speichern, die bereits gecrawlt wurden, und verhindern so, dass Suchmaschinen bereits besuchte Seiten erneut crawlen.
Datenbankindizierung : Verwenden Sie Bloom-Filter, um zu prüfen, ob eine Datenbank einen bestimmten Datensatz enthält, sodass kein vollständiger Tabellenscan erforderlich ist.
Netzwerkrouting : Filtern von Netzwerkpaketen durch Überprüfen, ob ihre Zieladressen zu einer Reihe autorisierter Adressen gehören.
Rechtschreibprüfung : Überprüfen, ob ein Wort in einem großen Wörterbuch vorhanden ist.