Das Prinzip des Bloom -Filters ist sehr einfach: Es besteht darin, eine Zeichenfolge in einen Ganzzahlschlüssel zu haben und dann eine sehr lange Bitsequenz auszuwählen, die mit 0 beginnt und 0 an dieser Position in den Schlüssel zu 1 ändert. Das nächste Mal, wenn eine Zeichenfolge hereinkommt, der Wertschlüssel nach Hash, und wenn der Wert auf diesem Bit auch 1 ist, bedeutet dies, dass die Zeichenfolge existiert.
Wenn Sie der obigen Methode folgen, unterscheidet sich dies nicht vom Hash -Algorithmus, und es gibt immer noch Duplikationen des Hash -Algorithmus.
Der Bloom -Filter hasht eine Zeichenfolge in mehrere Schlüssel, also werde ich einfach dem Buch folgen.
Erstellen Sie zuerst eine binäre Konstante von 1,6 Milliarden und stellen Sie dann alle 1,6 Milliarden binären Bits auf Null ein. Für jede Zeichenfolge werden 8 verschiedene Zufallsgeneratoren (F1, F2, ..., F8) verwendet, um 8 Informationsfingerabdrücke (F1, F2, ..., F8) zu generieren. Anschließend wird ein Zufallszahlengenerator G verwendet, um diese acht Informationsfingerabdrücke auf 8 natürliche Zahlen G1, G2, ..., G8 in 1 bis 1,6 Milliarden zuzuordnen. Ändern Sie nun alle binären Bits in diesen 8 Positionen auf 1. Auf diese Weise wird ein Blütefilter gebaut.
Wie kann ich also feststellen, ob bereits eine Zeichenfolge existiert?
Verwenden Sie nun 8 Zufallszahlengeneratoren (F1, F2, ..., F8), um 8 Informationsfingerabdrücke S1, S2, ..., S8 für diese Zeichenfolge zu generieren, und entsprechen diesen 8 Informationsfingerabdrücken dann den 8 binären Bits des Bloom -Filters, nämlich T1, T2, ..., T8. Wenn die Saite existiert, sollten die binären Bits, die T1, T2, ..., T8 entsprechen, offensichtlich sein 1. Auf diese Weise können Sie feststellen, ob eine Zeichenfolge bereits vorhanden ist.
Tatsächlich ist der Blütefilter eine Erweiterung des Hash -Algorithmus. Da es im Wesentlichen ein Hash ist, wird es definitiv Mängel geben. Mit anderen Worten, es wird definitiv Fehleinschätzungen geben. Eine Zeichenfolge ist nicht erschienen, aber das Urteil des Blütenfilters ist erschienen. Obwohl die Möglichkeit sehr klein ist, existiert sie.
Wie kann man diese Wahrscheinlichkeit verringern? Zunächst kann man sich vorstellen, dass die Wahrscheinlichkeit definitiv reduziert wird, wenn 8 Informationsfingerabdrücke auf 16 Fehler verlängert werden, aber auch berücksichtigt werden sollte, dass auf diese Weise die Anzahl der Zeichenfolgen, die ein Bloomfilter speichern kann, auch um 1 Mal reduziert wird. Wählen Sie außerdem eine gute Hash -Funktion aus, und es gibt viele Arten von Hash -Methoden für Zeichenfolgen, einschließlich sehr guter Hash -Funktionen.
Der Bronzefilter wird hauptsächlich zum Filtern von böswilligen URLs verwendet. Alle böswilligen URLs basieren auf einem Bronzefilter, und dann wird der Benutzer von der URL zugegriffen. Wenn es sich in einer böswilligen URL befindet, wird der Benutzer benachrichtigt. Auf diese Weise können wir auch eine Whitelist für einige URLs festlegen, die häufig Fehler im Urteil haben, und dann die URLs übereinstimmen, die als Existenz und die URLs in der Whitelist beurteilt werden. Wenn sie in der Whitelist sind, werden sie freigelassen. Natürlich kann dieser Whitelist nicht zu groß sein, und es ist auch nicht zu groß, und die Wahrscheinlichkeit eines Blütenfilterfehlers ist sehr klein. Interessierte Leser können die Fehlerrate des Bloom -Filters überprüfen.
Das Folgende ist der Quellcode der Java -Version von Bloom Filter:
import Java.util.bitset; /** * * @Author xkey */public class Bloomfilter {private statische endgültige int default_size = 2 << 24; // Bitlänge des BLOOM -Filters private statische endgültige int [] Seeds = {3,5,7, 11, 13, 31, 37, 61}; // Die Hauptnummer, die hier die Fehlerrate ausgewählt werden kann. private static SimpleHash [] func = new SimpleHash [Seeds.length]; public static void addValue (String -Wert) {für (SimpleHash f: func) // Hash den String -Wert in 8 oder mehr Ganzzahlen und dann zu 1 in den Bits dieser Ganzzahlen bits.set (f.hash (value), true); } public static void add (String -Wert) {if (value! = null) addValue (value); } public static boolean enthält (String -Wert) {if (value == null) return false; boolean ret = true; Für (SimpleHash F: func) // In der Tat müssen sie nicht alle hier ausführen. Einmal ret == falsch, dann wird die Zeichenfolge nicht enthalten. ret = ret && bits.get (f.hash (Wert)); Return Ret; } public static void main (String [] args) {String value = "www.vevb.com"; für (int i = 0; i <Seeds.length; i ++) {func [i] = new SimpleHash (default_size, Seeds [i]); } add (value); System.out.println (enthält (Wert)); }} class SimpleHash {// Dieses Ding entspricht der Struktur in C ++ privat int Cap; privates Int -Samen; public SimpleHash (int Cap, int Seed) {this.cap = cap; this.seed = samen; } public int Hash (String -Wert) {// Stand Hash, es ist sehr wichtig, eine gute Hash -Funktion int result = 0 auszuwählen; int len = value.length (); für (int i = 0; i <len; i ++) {result = Seed * result+value.charat (i); } return (CAP - 1) & Ergebnis; }} Zusammenfassung: Der Bloom -Filter ist eine Innovation in Hashing -Algorithmen und verbraucht auch nur sehr wenig Platz und hat eine niedrige Fehlerrate. Kurz gesagt, diese innovative Idee ist es wert, gelernt zu werden und eine Verwendung von Datentypen wie Bit.
Die Java -Implementierungsmethode des Bloom -Filters ist der gesamte Inhalt, den ich mit Ihnen geteilt habe. Ich hoffe, Sie können Ihnen eine Referenz geben und ich hoffe, Sie können wulin.com mehr unterstützen.