Mise en œuvre du filtre Bloom

J'ai donc vu cette question auparavant, et j'ai utilisé des conseils ci-dessus et il s'est avéré être un moyen de ralentir pour moi. Alors j'ai écrit le mien. Ce n'est pas entièrement général, mais je suis sûr que si quelqu'un est désespéré de la performance comme je suis qu'ils le rendront plus général par eux-mêmes :)

J'ai utilisé Murmur Hash Mise en œuvre que vous pouvez télécharger ici: http://d3s.mff.cuni.cz/~holub/sw/javamurmurHash/ P >

Le code: Package UK.AC.CAM.CL.SS958.SPRINGBOARDSIMULATION; P>

    import ie.ucd.murmur.MurmurHash;

    import java.util.BitSet;
    import java.util.Random;

    public class FastBloomFilter {

        private final BitSet bs;

        final int [] hashSeeds;

        final int capacity;

        public FastBloomFilter(int slots, int hashFunctions) {
            bs = new BitSet(slots);
            Random r = new Random(System.currentTimeMillis());
            hashSeeds = new int[hashFunctions];
            for (int i=0; i<hashFunctions; ++i) {
                hashSeeds[i] = r.nextInt();
            }
            capacity = slots;
        }

        public void add(int value) {
            byte [] b = new byte[] {
                    (byte)(value >>> 24),
                    (byte)(value >>> 16),
                    (byte)(value >>> 8),
                    (byte)value};
            for (int i=0; i<hashSeeds.length; ++i) {
                int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
                bs.set(Math.abs(h)%capacity, true);
            }
        }

        public void clear() {
            bs.clear();
        }

        public boolean mightContain(int value) {
            byte [] b = new byte[] {
                    (byte)(value >>> 24),
                    (byte)(value >>> 16),
                    (byte)(value >>> 8),
                    (byte)value};
            for (int i=0; i<hashSeeds.length; ++i) {
                int h = MurmurHash.hash32(b, 4, hashSeeds[i]);

                if(!bs.get(Math.abs(h)%capacity)) {
                    return false;


            }

            return true;
        }


        public static void main(String [] args) {
            FastBloomFilter bf = new FastBloomFilter(1000, 10);
            System.out.println("Query for 2000: " + bf.mightContain(2000));
            System.out.println("Adding 2000");
            bf.add(2000);
            System.out.println("Query for 2000: " + bf.mightContain(2000));


        }
    }

Vous pouvez comprendre comment cela permet d'économiser de l'espace à l'aide de cet exemple: Disons que je travaille pour Google, dans l'équipe Chrome et je souhaite ajouter une fonctionnalité au navigateur qui notifie l'utilisateur si l'URL qu'il a entrée est une URL malveillante. J'ai donc un jeu de données d'environ 1 million d'URL malveillantes, la taille de ce fichier étant d'environ 25 Mo. Puisque la taille est assez grande, (grande par rapport à la taille du navigateur lui-même), je stocke ces données sur un serveur distant.

Case 1: J'utilise une fonction de hachage avec une table de hachage. Je décide d'une fonction de hachage efficace et d'exécuter toutes les 1 million d'URL à travers la fonction de hachage pour obtenir des clés hachées. Je fais ensuite une table de hachage (un tableau), où la clé de hachage me donnerait l'index pour placer cette URL. Alors maintenant, une fois que j'ai hashé et rempli la table de hachage, je vérifie sa taille. J'ai stocké toutes les 1 million d'URL dans la table de hachage avec des clés. Donc, la taille est d'au moins 25 Mo. Cette table de hachage, due à sa taille, sera stockée sur un serveur distant. Lorsqu'un utilisateur vient et entre une URL dans la barre d'adresse, je dois vérifier s'il est malveillant. Ainsi, je gère l'URL à travers la fonction de hachage (le navigateur lui-même peut le faire) et je reçois une clé de hachage pour cette URL. Je dois maintenant apporter une demande à mon serveur distant avec cette clé de hachage, pour vérifier si l'URL particulière de ma table de hachage avec cette clé particulière est la même que ce que l'utilisateur est entré. Si oui, il est malveillant et si non, ce n'est pas malveillant. Ainsi, chaque fois que l'utilisateur entre une URL, une demande au serveur distant doit être prise pour vérifier s'il s'agit d'une URL malveillante. Cela prendrait beaucoup de temps et rendrait ainsi mon navigateur lent.

Cas 2: J'utilise un filtre de floraison. La liste complète de 1 million d'URL est exécutée dans le filtre de floraison à l'aide de plusieurs fonctions de hachage et les positions respectives sont marquées comme 1, dans un vaste ensemble de 0s. Disons que nous voulons un taux faux positif de 1%, à l'aide d'une calculatrice de filtres de fleurs ( http: // Hur .t / Bloomfilter? N = 1000000 & P = 0.01 ), nous obtenons la taille du filtre de floraison requis comme seulement 1,13 Mo. Cette petite taille est attendue comme étant, même si la taille de la matrice est énorme, nous ne stockons que 1s ou 0s et non les URL comme dans le cas de la table de hachage.Cette tableau peut être traité comme une matrice de bit. C'est-à-dire que nous n'avons que deux valeurs 1 et 0, nous pouvons définir des bits individuels au lieu d'octets. Cela réduirait l'espace pris par 8 fois. Ce filtre de fleurs de 1,13 MB, en raison de sa petite taille, peut être stocké dans le navigateur Web lui-même !! Ainsi, lorsqu'un utilisateur vient et entre une URL, nous appliquons simplement les fonctions de hachage requises (dans le navigateur lui-même) et vérifiez toutes les positions du filtre de floraison (qui est stockée dans le navigateur). Une valeur de 0 dans l'une quelconque des positions nous indique que cette URL n'est définitivement pas dans la liste des URL malveillantes et que l'utilisateur peut se dérouler librement. Ainsi, nous n'avons pas appelé le serveur et avons donc économisé le temps. Une valeur de 1 nous indique que l'URL pourrait figurer dans la liste des URL malveillantes. Dans ces cas, nous appelons un appel au serveur distant et nous pouvons utiliser une autre fonction de hachage avec une table de hachage comme dans le premier cas pour récupérer et vérifier si l'URL est réellement présente. Depuis la majeure partie des temps, une URL n'est pas susceptible d'être malveillante, le petit filtre de floraison dans les chiffres du navigateur qui évitent et évite donc de temps en évitant les appels vers le serveur distant. Ce n'est que dans certains cas, si le filtre de Bloom nous dit que l'URL pourrait être malveillante, uniquement dans ces cas, nous appelons un appel au serveur. Que "pourrait" est à 99%.

Donc, en utilisant un petit filtre de floraison dans le navigateur, nous avons enregistré beaucoup de temps car nous n'avons pas besoin de faire des appels de serveur pour chaque URL entrée.

Vous pouvez utiliser un filtre de floraison basé sur Redis serveur avec Redisson lib. Basé sur 128 bits HighwayHash . Voici un exemple: xxx

J'ai écrit un courte publication sur la mise en œuvre d'un filtre de floraison Utilisation des fonctionnalités Java 8, que j'espère être pertinente pour la question des économies de l'espace. Je suis allé un BORGE PLUS pour discuter de la procédure à bit une collection des filtres de fleurs, lorsque certains systèmes de récupération d'informations feraient cela, ce qui est pertinent pour l'efficacité lorsque vous avez de nombreux filtres de fleurs.