Bloom Filtre De Mise En Œuvre

À l'aide de filtre de Bloom, on va se l'optimisation de l'espace. Cassandra cadre a également une mise en œuvre de la Floraison de Filtre. Mais, dans le détail, comment est-ce l'optimisation de l'espace atteint?

veuillez marquer certaines de vos questions répondu, et de reformuler un peu à votre question. De cette façon, les gens seront un peu plus désireux de vous aider.
Je suis désolé.comment je vais marquer les questions de répondre?
cliquez sur le droit de la marque , elle s'allume en vert pour la réponse qui vous vous sentez la réponse en fait
Je l'ai déjà.Fait.merci

OriginalL'auteur UVM | 2010-12-28

3

Un filtre de bloom n'est pas un "cadre". Il est vraiment plus comme simplement un algorithme. La mise en œuvre n'est pas très long.

Voici un en Java, j'ai essayé (.jar, le code source et la JavaDoc étant tous disponibles):

"Stand alone implémentations Java de Coucou de Hachage et de Filtres de Bloom" (vous pouvez Google pour cette dans le cas où le lien suivant n'est pas de travailler plus):

http://lmonson.com/blog/?page_id=99

J'ai le code source de la Floraison filtre de l'algorithme mis en œuvre dans Cassandar cadre.
Mais mon souci c'est ici comment l'optimisation de l'espace qui se passe ici?
ah ok, ne savait pas que c'était votre question... L'article sur Wikipédia a un article expliquant comment l'espace de l'efficacité est atteint: en.wikipedia.org/wiki/Bloom_filter Mais c'est un compromis où vous vous engagez à avoir quelques faux positifs, en échange d'une plus efficace de la mémoire de la représentation.
Vous n'êtes pas exonéré de la responsabilité de vérifier les valeurs. La floraison de filtre de réduire le nombre de valeurs que vous avez besoin de vérifier et il vous permet de construire un algorithme qui est optimisé pour la plupart des valeurs correctes plutôt que de ne pas savoir.
ce lien semble être inutile

OriginalL'auteur SyntaxT3rr0r
15

Vous pouvez comprendre comment il économise de l'espace à l'aide de cet exemple :
Disons que je travaille pour Google, dans le Chrome de l'équipe, et je veux ajouter une fonctionnalité du navigateur qui informe l'utilisateur si l'url qu'il a entré une URL malveillante. Donc, j'ai un jeu de données d'environ 1 million Url malveillants, la taille de ce fichier en cours autour de 25 mo. Depuis la taille est assez grande, (grande en comparaison à la taille du navigateur lui-même), je stocke ces données sur un serveur distant.

Cas 1 : j'utilise une fonction de hachage avec une table de hachage. Je décide sur un efficace de la fonction de hachage, et d'exécuter toutes les 1 millions d'url par le biais de la fonction de hachage pour obtenir des clés de hachage. J'ai ensuite faire une table de hachage (un tableau), où la clé de hachage qui pourrait me donner de l'index à la place de cette URL. Alors maintenant, une fois que j'ai haché et rempli de hachage table, je vérifie sa taille. Je l'ai stocké toutes les 1 millions d'Url dans la table de hachage avec ils sont touches. De sorte que la taille est d'au moins 25 MO. Cette table de hachage, en raison de sa taille sera stockée sur un serveur distant. Lorsqu'un utilisateur arrive et entre dans une url dans la barre d'adresse, j'ai besoin de vérifier si elle malveillants. Donc je lance l'url par le biais de la fonction de hachage (le navigateur lui-même peut le faire) et je obtenir une clé de hachage pour cette URL. Maintenant, je dois faire une demande à mon serveur à distance avec clé de hachage, pour vérifier si l'URL donnée dans ma table de hachage avec clé particulier, est le même que ce que l'utilisateur a entré. Si oui, alors il est malveillant et si non, alors il n'est pas malveillant. Ainsi, chaque fois que l'utilisateur entre une URL, une requête vers le serveur distant doit être effectuée pour vérifier si c'est une URL malveillante. Cela prendrait beaucoup de temps et donc faire de mon navigateur lent.

Cas 2 : j'utilise un filtre de bloom. L'ensemble de la liste des 1 millions d'Url sont passés à travers le filtre de bloom à l'aide de plusieurs fonctions de hachage et les positions respectives sont marqués 1, dans un immense tableau de 0s. Disons que nous voulons un taux de faux positif de 1%, à l'aide d'un filtre de bloom calculatrice (http://hur.st/bloomfilter?n=1000000&p=0,01) , nous obtenons la taille de la fleur de filtre nécessaire que seulement 1.13 MO. Cette petite taille est prévu que, même si la taille de la matrice est énorme, nous ne sommes que le stockage de 1 ou de 0 et pas l'Url comme dans le cas de la table de hachage.Ce tableau peut être traitée comme un tableau de bits. Qui est, depuis, nous avons seulement deux valeurs 1 et 0, nous pouvons définir les bits individuels au lieu d'octets. Cela permettrait de réduire l'espace occupé par 8 fois. Cette 1.13 MO bloom filtre, en raison de sa petite taille, peuvent être stockés dans le navigateur web lui-même !! Ainsi, lorsqu'un utilisateur arrive et entre dans une URL, nous avons simplement appliquer les fonctions de hachage (dans le navigateur lui-même), et de vérifier toutes les positions dans la fleur de filtre (qui est stocké dans le navigateur). Une valeur de 0 dans aucune des positions nous dit que cette URL n'est CERTAINEMENT PAS dans la liste des Url malveillants et l'utilisateur peut procéder librement. Ainsi nous n'avons pas d'effectuer un appel vers le serveur et donc un gain de temps. Une valeur de 1 nous dit que l'url PEUT être dans la liste des URL malveillants. Dans ces cas, nous faisons un appel vers le serveur distant et là-bas, nous pouvons utiliser une autre fonction de hachage avec certains de la table de hachage comme dans le premier cas, de récupérer et de vérifier si l'url est effectivement présent. Depuis, la plupart du temps, une url n'est pas susceptible d'être un méchant, le petit filtre de bloom dans le navigateur chiffres et donc de gagner du temps en évitant les appels vers le serveur distant. Dans quelques cas seulement, si le filtre de bloom nous dit que l'url PEUT être malveillant , seulement dans ces cas, nous faisons un appel vers le serveur. Qui POURRAIT' est de 99%.

Donc, à l'aide d'un petit filtre de bloom dans le navigateur, nous avons économisé beaucoup de temps, car nous n'avons pas besoin de faire des appels au serveur pour chaque url est entré.

Voici un simple filtre de bloom mise en œuvre en Python. github.com/tarunsharma1/Bloom-Filter
Alors que la raison de choisir un filtre de Bloom est illustrée par des exemples, la manière dont les données est lui-même stocké n'est pas clair.
donc j'ai fourni l'ensemble du code pour la mise en œuvre dans le commentaire au-dessus du vôtre. L'explication de chaque partie du code est présent dans le git ReadMe. Un tableau de bits est utilisé et la mise en œuvre en Python est indiqué

OriginalL'auteur Tarun

J'ai donc vu cette question avant, et j'ai utilisé les conseils ci-dessus et il s'est avéré être du temps pour moi. J'ai donc écrit mon propre. Il n'est pas entièrement en général, mais je suis sûr que si quelqu'un est désespérée pour la performance, comme je suis ils vont la rendre plus générale par eux-mêmes 🙂

J'ai utilisé Murmure de hachage mise en œuvre que vous pouvez télécharger ici: http://d3s.mff.cuni.cz/~holub/sw/javamurmurhash/

Le code:
package royaume-uni.ac.cam.cl.ss958.SpringBoardSimulation;

    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));
}
}

OriginalL'auteur siemanko

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

RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
//initialize bloom filter once with 
//expectedInsertions = 55000000
//falseProbability = 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject(someStateHere1));
bloomFilter.add(new SomeObject(someStateHere2));
//does it contain object?
bloomFilter.contains(new SomeObject(someStateHere3));

OriginalL'auteur Nikita Koksharov

0

J'ai écrit un court post sur la mise en œuvre de la fleur de filtre à l'aide de Java 8, qui, je l'espère, est pertinente pour la question de la réduction de l'espace. Je suis allé un peu plus loin pour discuter de la façon dont à peu tranche une collection de filtres de bloom, lorsque certains systèmes de recherche d'information serait le faire, ce qui est pertinent à l'efficience lorsque vous avez beaucoup de filtres de bloom.

J'ai lu votre post. Qu'est-ce que l'o/p que vous obtenez lorsque vous exécutez le code?
J'ai bien aimé votre blog
Pas sûr de ce que vous voulez dire o/p? Le taux de faux positifs de p dépend des fonctions de hachage (avec cette application vous pouvez fournir arbitraire de fonctions de hachage), le nombre de fonctions de hachage (k), la taille (m), et la quantité de données que vous mettez dans. Il pourrait être plus convivial pour l'envelopper afin de vous fournir une fonction de hachage famille et et une valeur de p, alors le générateur de rapports sur les chiffres de k et m pour vous. Mais alors, la goyave est très bon, le post est juste pour illustrer la structure de données.

OriginalL'auteur richardstartin

Vous devez vous connecter pour publier un commentaire.