Le principe du filtre de floraison est très simple: il s'agit de hacher une chaîne dans une clé entière, puis de sélectionner une séquence de bits très longue, qui commence par 0, et de changer 0 à cette position à 1 dans la clé; La prochaine fois qu'une chaîne entrera en jeu, la clé de valeur après le hachage, et si la valeur de ce bit est également 1, cela signifie que la chaîne existe.
Si vous suivez la méthode ci-dessus, il ne sera pas différent de l'algorithme de hachage, et il y a encore des duplications de l'algorithme de hachage.
Le filtre Bloom hache une chaîne en plusieurs clés, donc je vais simplement suivre le livre.
Créez d'abord une constante binaire de 1,6 milliard, puis définissez les 1,6 milliards de bits binaires à zéro. Pour chaque chaîne, 8 générateurs aléatoires différents (F1, F2, ..., F8) sont utilisés pour générer 8 empreintes digitales d'informations (F1, F2, ..., F8). Ensuite, un générateur de nombres aléatoires G est utilisé pour cartographier ces huit empreintes digitales d'information à 8 nombres naturels G1, G2, ..., G8 en 1 à 1,6 milliard. Maintenant, changez tous les bits binaires dans ces 8 positions à 1. De cette façon, un filtre de floraison est construit.
Alors, comment détecter si une chaîne existe déjà?
Utilisez maintenant 8 générateurs de nombres aléatoires (F1, F2, ..., F8) pour générer 8 empreintes digitales d'information S1, S2, ..., S8 pour cette chaîne, puis correspondez à ces 8 empreintes digitales d'informations aux 8 bits binaires du filtre de floraison, à savoir T1, T2, ..., T8. Si la chaîne existe, alors évidemment les bits binaires correspondant à T1, T2, ..., T8 devrait être 1. C'est comment déterminer s'il existe déjà une chaîne.
En fait, le filtre Bloom est une extension de l'algorithme de hachage. Comme il s'agit essentiellement d'un hachage, il y aura certainement des lacunes. En d'autres termes, il y aura certainement des erreurs de jugement. Une chaîne n'est pas apparue, mais le jugement du filtre Bloom est apparu. Bien que la possibilité soit très petite, elle existe.
Alors, comment réduire cette probabilité? Tout d'abord, on peut imaginer que si 8 empreintes digitales d'information sont étendues à 16 erreurs, la probabilité sera certainement réduite, mais il faut également considérer que, de cette manière, le nombre de chaînes qu'un filtre de floraison peut stocker est également réduite de 1 fois; De plus, sélectionnez une bonne fonction de hachage, et il existe de nombreux types de méthodes de hachage pour les chaînes, y compris de très bonnes fonctions de hachage.
Le filtre en bronze est principalement utilisé pour filtrer les URL malveillantes. Toutes les URL malveillantes sont construites sur un filtre en bronze, puis l'utilisateur est accessible par l'URL. S'il s'agit d'une URL malveillante, l'utilisateur sera informé. De cette façon, nous pouvons également définir une liste blanche pour certaines URL qui ont souvent des erreurs de jugement, puis faire correspondre les URL qui sont jugées existantes et les URL de la liste blanche. S'ils sont dans la liste blanche, ils seront libérés. Bien sûr, cette liste blanche ne peut pas être trop grande, ni trop grande, et la probabilité d'une erreur de filtre de floraison est très petite. Les lecteurs intéressés peuvent vérifier le taux d'erreur du filtre Bloom.
Ce qui suit est le code source de la version Java du filtre Bloom:
import java.util.bitset; / ** * * @author xkey * / classe publique BloomFilter {private static final int Default_size = 2 << 24; // Longueur du bit du filtre Bloom Final Final Static int [] SEEDS = {3,5,7, 11, 13, 31, 37, 61}; // Le numéro de premier ordre peut être sélectionné pour réduire le taux d'erreur; Private Static SimpleHash [] func = new SimpleHash [SeedS.Length]; public static void addValue (valeur de chaîne) {for (SimpleHash f: func) // hache la valeur de chaîne en 8 entiers ou plus, puis passer à 1 sur les bits de ces entiers bits.set (f.hash (valeur), true); } public static void add (string value) {if (value! = null) addValue (value); } public static booléen contient (valeur de chaîne) {if (value == null) return false; booléen ret = true; Pour (SimpleHash F: Func) // En fait, il n'est pas nécessaire de les exécuter tous ici. Juste ret == false une fois, alors la chaîne ne sera pas incluse. ret = ret && bits.get (f.hash (valeur)); return ret; } public static void main (String [] args) {String value = "www.vevb.com"; for (int i = 0; i <seeds.length; i ++) {func [i] = new SimpleHash (default_size, seeds [i]); } add (valeur); System.out.println (contient (valeur)); }} classe SimpleHash {// Cette chose est équivalente à la structure dans C ++ Private int Cap; SEMENT INT PRIVÉ; public SimpleHash (int cap, int seed) {this.cap = cap; this.seed = semence; } public int hash (String Value) {// stand hash, il est très important de sélectionner une bonne fonction de hachage int résultat = 0; int len = value.length (); for (int i = 0; i <len; i ++) {result = semed * result + value.charat (i); } return (cap - 1) & result; }} Résumé: Bloom Filter est une innovation dans les algorithmes de hachage, et il consomme également très peu d'espace et a un faible taux d'erreur. En bref, cette idée innovante mérite d'être apprise et est une utilisation du type de données comme Bit.
La méthode de mise en œuvre Java du filtre Bloom est tout le contenu que j'ai partagé avec vous. J'espère que vous pourrez vous faire référence et j'espère que vous pourrez soutenir Wulin.com plus.