Bloom Filter in Java mit Guave

Guten Tag an alle.

Wir haben einen neuen Kurs gestartet - "Algorithmen für Entwickler" , der für diejenigen gedacht ist, die ihre Kenntnisse über verschiedene Strukturen und Algorithmen für die Datenverarbeitung erweitern, algebraische Probleme und dynamische Programmierprobleme für verschiedene Sprachen lösen möchten. Deshalb teilen wir heute einen kleinen Hinweis über die Funktionsweise des Bloom-Filters in Java.

Einführung

In diesem Artikel werden wir uns die Struktur des Bloom-Filters aus der Guava-Bibliothek ansehen. Der Bloom-Filter ist eine probabilistische Datenstruktur mit effizienter Speichernutzung, mit der wir die Frage „Ist dieses Element in der Menge enthalten?“ Beantworten können.

Der Bloom-Filter enthält keine falschen Negative. Wenn er also false zurückgibt, können Sie zu 100% sicher sein, dass dieses Element nicht in der Menge enthalten ist.

Der Bloom-Filter kann jedoch falsch positive Ergebnisse zurückgeben. Wenn also true zurückgegeben wird, ist die Wahrscheinlichkeit hoch, dass sich das Element tatsächlich in der Menge befindet, aber die Wahrscheinlichkeit beträgt nicht 100%.

Weitere Informationen zur Funktionsweise des Bloom-Filters finden Sie in dieser Anleitung.



Maven Sucht

Wir werden die Guava-Implementierung des Bloom-Filters verwenden, also fügen Sie eine Guava-Abhängigkeit hinzu
Die neueste Version finden Sie in Maven Central .

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 

Warum einen Blütenfilter verwenden?

Der Bloom-Filter ist sparsam und schnell ausgelegt . Wenn wir es verwenden, können wir die Wahrscheinlichkeit falsch positiver Antworten klären, die wir akzeptieren möchten , und gemäß der Konfiguration benötigt der Bloom-Filter so wenig Speicher wie möglich.

Aufgrund seiner Wirtschaftlichkeit passt der Bloom-Filter auch bei einer großen Anzahl von Elementen problemlos in den Speicher. Einige Datenbanken, einschließlich Cassandra und Oracle, verwenden diesen Filter für erste Überprüfungen, bevor auf die Festplatte oder den Cache zugegriffen wird, z. B. wenn eine Anforderung für eine bestimmte ID empfangen wird.

Wenn der Filter angibt, dass keine ID vorhanden ist, beendet die Datenbank möglicherweise die Verarbeitung der Anforderung und kehrt zum Client zurück. Andernfalls wird die Abfrage auf die Festplatte verschoben und das gefundene Element zurückgegeben.

Erstellen eines Bloom-Filters

Angenommen, wir möchten einen Bloom-Filter für nicht mehr als 500 Ganzzahlen erstellen und werden mit einer Wahrscheinlichkeit von einem Prozent (0,01) für falsch positive Ergebnisse verdreifacht.

Dazu können wir die BloomFilter Klasse aus der Guava-Bibliothek verwenden. Es ist erforderlich, die Anzahl der an den Filter gemeldeten Elemente und die gewünschte Wahrscheinlichkeit von Fehlalarmen zu übertragen:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01); 

Fügen Sie nun dem Filter einige Zahlen hinzu:

 filter.put(1); filter.put(2); filter.put(3); 

Wir haben nur drei Elemente hinzugefügt und die maximale Anzahl von Einsätzen bestimmt - 500, daher sollte unser Bloom-Filter ziemlich genaue Ergebnisse liefern. Testen Sie es mit der Methode mightContain() :

 assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse(); 

Wie der Name schon sagt, können wir nicht 100% sicher sein, dass sich dieses Element wirklich im Filter befindet, wenn die Methode true zurückgibt.

In unserem Fall, wenn mightContain() true zurückgibt, 99%, dass sich das Element im Filter befindet, und 1%, dass das Ergebnis falsch positiv ist. Wenn der Filter false zurückgibt, können Sie zu 100% sicher sein, dass das Element fehlt.

Übersättigter Blütenfilter

Beim Entwerfen eines Bloom-Filters ist es wichtig, einen ausreichend genauen Wert für die erwartete Anzahl von Elementen bereitzustellen. Andernfalls gibt unser Filter viel häufiger falsch positive Ergebnisse zurück, als wir möchten. Betrachten Sie ein Beispiel.

Angenommen, wir erstellen einen Filter mit der gewünschten Wahrscheinlichkeit eines falsch positiven Ergebnisses von einem Prozent und der erwarteten Anzahl von Elementen von fünf, fügen dann aber 100.000 Elemente ein:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Wenn Sie so wenige Elemente erwarten, nimmt der Filter nur sehr wenig Speicherplatz ein.
Nach dem Hinzufügen einer viel größeren Anzahl von Elementen wird der Filter jedoch übersättigt und hat eine höhere Wahrscheinlichkeit, ein falsch positives Ergebnis zu erzeugen als das gewünschte Prozent.

Beachten Sie, dass die Methode mightContatin() auch für einen Wert, den wir zuvor nicht in den Filter mightContatin() true zurückgibt.

Fazit

In diesem kurzen Tutorial haben wir uns mit der Wahrscheinlichkeit der Datenstruktur des Bloom-Filters befasst - unter Verwendung der Guava-Implementierung.

Die Implementierung all dieser Beispiele und Codefragmente finden Sie im GitHub-Projekt .

Dies ist ein Maven-Projekt, daher sollte der Import und Start nicht schwierig sein.

DAS ENDE

Wir warten auf Kommentare und Fragen, die wie immer hier hinterlassen werden können, und gehen zum Tag der offenen Tür zum Kurslehrer Michail Gorshkow .