Interaktive Mathe- und Wissenschafts-Lektionen

← Informatik

Bloom-Filter: Sicher nicht oder wahrscheinlich ja

Jedes Wort setzt k Bits in einer Folge von m Bits. Bei einer Abfrage prüfst du die k Bits des Wortes: Eine einzige 0 beweist, dass es nie eingefügt wurde. Stehen alle auf 1, ist es nur wahrscheinlich enthalten. Füge die Wörter Schritt für Schritt ein und gib dann ein eigenes Wort ein.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Bloom-Filter: Sicher nicht oder wahrscheinlich ja

Ein Bloom-Filter prüft mit einer Folge von m Bits und k Hashfunktionen, ob ein Element zu einer Menge gehört. Beim Einfügen werden die k Bits gesetzt, auf deren Positionen die Hashwerte des Elements verweisen. Eine Abfrage prüft dieselben k Bits: Ist eines davon 0, gehört das Element sicher nicht zur Menge. Stehen alle auf 1, gehört es wahrscheinlich dazu. Eine falsche Antwort „wahrscheinlich ja“ heißt falsch positives Ergebnis. Nach dem Einfügen von n Elementen lautet die Standardnäherung für die Falsch-Positiv-Rate (1 − e−kn/m)k. Sie ist eine exponentielle Näherung von Blooms ursprünglicher Formel aus dem Jahr 1970 und nimmt bei k = (m/n) ln 2 ihr Minimum an.

Was die einzelnen Symbole bedeuten

m
die Anzahl der Bits im Filter
k
die Anzahl der Hashfunktionen und damit der Bits, die jedes Wort setzt und jede Abfrage prüft
n
die Anzahl der eingefügten Wörter
X
die Anzahl der auf 1 gesetzten Bits, nachdem alle n Wörter eingefügt wurden
Setzt voraus
Die k Positionen eines Wortes werden durch Doppelhashing aus zwei Hashwerten berechnet: Position i ist (h₁ + i·h₂) mod m. Dabei ist h₁ der FNV-1a-Hashwert des Wortes und h₂ ein zusätzlich durchmischter djb2-Hashwert, der ungerade gemacht wird. Da m eine Zweierpotenz ist, sind die k Positionen eines Wortes stets verschieden. Die Standardnäherung behandelt jede der kn Positionen als unabhängige zufällige Wahl. Durch Doppelhashing und ein kleines m weicht der tatsächliche Filter von dieser Annahme ab. Gemessen wird die Falsch-Positiv-Rate an den 10.000 Zeichenfolgen 0 bis 9999. Für diese Zeichenfolgen ist sie exakt, für die Gesamtheit aller möglichen Wörter gilt das nicht.

Sechzehn Hashfunktionen sind schlechter als eine 🖖

Klick auf Fünf Hashfunktionen und schau dir die Tabelle unter den Ergebnissen an. Bei 128 Bits und 16 Wörtern lässt 1 Hashfunktion 12,82 % der nie eingefügten Zeichenfolgen durch. Mit 5 sind es 2,50 %, der niedrigste Wert in der Spalte. Mit 16 steigt die Rate auf 32,01 % und liegt damit höher als mit 1. Jede zusätzliche Funktion prüft bei der Abfrage ein weiteres Bit. Das hilft. Sie setzt aber auch bei jedem Einfügen ein weiteres Bit und erhöht damit die Belegung. Von 1 bis 5 sinkt die Rate mit jedem Schritt, danach steigt sie bis auf einen kleinen Rückgang bei 15. Bloom erkannte 1970, wo der Wendepunkt liegt: Etwa die Hälfte der Bits steht dann auf 1. Bei 5 Hashfunktionen sind es hier 60 von 128. Die Standardnäherung liefert als bestes k den Wert (m/n) ln 2 = 8 × 0,693 = 5,55.

Die Anzahl der 1-Bits liefert die bessere Näherung 🖖

Klick auf Sechzehn Hashfunktionen. Die Standardnäherung ergibt 9,76 %, doch der Filter lässt 32,01 % durch. Die Näherung geht von 128 × (1 − e−2) = 110,7 gesetzten Bits aus. Diese 16 Wörter setzen tatsächlich 119. Erhebst du den tatsächlichen Anteil gesetzter Bits in die Potenz 16, also (119/128)16, erhältst du 31,15 %. Das liegt nahe am gemessenen Wert. Bei einem so großen k fallen schon wenige zusätzliche Bits mit dem Wert 1 stark ins Gewicht, denn alle 16 geprüften Bits müssen auf 1 stehen. Unter allen Einstellungen dieser Seite, bei denen falsch positive Ergebnisse auftreten, liegt die Näherung aus den tatsächlich gesetzten Bits in 5.356 von 6.051 Fällen näher an der gemessenen Rate. Als Maß dient dabei das Verhältnis von Näherung und Messwert. Ein Filter kann seine eigenen 1-Bits zählen und so seine Rate besser abschätzen als mit der Standardformel. Diese sechzehn Tiere bilden allerdings auch eine ungünstige Auswahl: Bei 150 anderen Gruppen mit jeweils 16 Wörtern erreicht ein Filter dieser Größe im Mittel 14,4 %, immer noch mehr als die Näherung vorhersagt.

Du löschst ein Wort, und ein anderes verschwindet 🖖

Klick auf owl löschen und geh Schritt für Schritt bis zum Ende. owl hat die Bits 37, 58 und 15 gesetzt. Das danach eingefügte Wort fox nutzt die Positionen 14, 15 und 16; Bit 15 stand schon auf 1. Wenn du die Bits von owl zurücksetzt, setzt du auch Bit 15 von fox zurück. Die Abfrage von fox ergibt daraufhin „sicher nicht“, obwohl das Wort im Filter enthalten ist. Das ist ein falsch negatives Ergebnis, genau der Fehler, den ein Bloom-Filter ausschließt. Ein Bit hält nur fest, dass irgendein Wort es gesetzt hat. Welches, bleibt unbekannt. Deshalb lässt sich kein einzelnes Bit bedenkenlos zurücksetzen. In diesem Filter mit 64 Bits würde das Löschen von 6 der 8 Wörter jeweils ein anderes Wort mit verschwinden lassen. Die übliche Lösung speichert an jeder Position einen kleinen Zähler statt eines einzelnen Bits. Beim Einfügen wird er um 1 erhöht, beim Löschen um 1 verringert. Dafür braucht der Filter mehr Speicher.

Aufgabe vollständig gelöst

  1. Wie klein konnte Blooms Filter für die Silbentrennung von 1970 sein? 4 Schritte

    Burton Bloom beschrieb 1970 ein Programm zur Silbentrennung für 500.000 Wörter. Ein paar einfache Regeln reichen für 450.000 davon; die übrigen 50.000 müssen in einem Wörterbuch auf der Festplatte nachgeschlagen werden. Sein Vorschlag: Ein Filter für diese 50.000 Wörter bleibt im Arbeitsspeicher. Dafür nimmt man in Kauf, dass 1 von 16 einfachen Wörtern einen unnötigen Festplattenzugriff auslöst. Wie viele Bits und Hashfunktionen braucht der Filter, und wie viele Festplattenzugriffe bleiben übrig? Stell anschließend auf dieser Seite dieselbe Anzahl an Bits pro Wort ein und miss die Rate.

    Öffne diese Aufgabe im Tool

    1. Beim besten k benötigt die Standardnäherung log₂(1/p) / ln 2 Bits pro Wort. Für p = 1/16 sind das 4 / 0,6931 = 5,77 Bits. Der Filter braucht also 50.000 × 5,77 = 288.539 Bits. Bloom selbst gab „weniger als 300.000 Bits“ an. Das beste k ist 5,77 × ln 2 = 4. Bei 4 Hashfunktionen steht im Erwartungswert die Hälfte der Bits auf 1.

    2. Für jedes der 50.000 schwierigen Wörter bleibt ein Festplattenzugriff nötig. Dazu kommt 1 von 16 einfachen Wörtern, also weitere 450.000 / 16 = 28.125 Zugriffe. Insgesamt sind das 78.125 Festplattenzugriffe bei 500.000 Wörtern oder 15,6 %. Bloom rundete auf 78.000. Gegenüber einem Festplattenzugriff für jedes Wort spart das 84 %.

    3. Die Länge eines Wortes geht in keine dieser Rechnungen ein. Der Filter benötigt 5,77 Bits pro Wort, ob es nun „cat“ oder „incomprehensibilities“ heißt. Für eine herkömmliche Hashtabelle veranschlagte Bloom dagegen im Mittel mindestens 19 Bits, um ein Wort darzustellen. Jede Halbierung von p kostet zusätzlich 1 / ln 2 = 1,44 Bits pro Wort. Für 1 von 64 wären es 6 / 0,6931 = 8,66.

    4. Auf dieser Seite kannst du höchstens 64 Wörter einfügen. Die Näherung hängt aber nur von m/n und k ab. Stell m = 256, n = 44 (5,82 Bits pro Wort) und k = 4 ein. Dann stehen 122 der 256 Bits auf 1, also 47,7 %. Von den 10.000 nie eingefügten Zeichenfolgen erhalten 535 die Antwort „wahrscheinlich ja“: 5,35 %, weniger als die 1/16 = 6,25 %, für die der Filter ausgelegt wurde. Die Standardnäherung ergibt für diesen Filter 6,11 %.

    Antwort

    288.539 Bits und 4 Hashfunktionen; es bleiben 78.125 Festplattenzugriffe bei 500.000 Wörtern. Für die 44 Wörter in 256 Bits misst diese Seite 5,35 %. Damit bleibt die Rate unter dem Zielwert. Das Ergebnis gilt für diesen einen Filter mit 44 Wörtern. Ob 50.000 Wörter in 288.539 Bits ähnlich nahe an 1/16 liegen, lässt sich hier nicht prüfen: Die Seite erlaubt höchstens 64 Wörter.

Lernpfad

Was eine Datenstruktur mit wenig Aufwand leistet

Quellen (1)

· Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.