Bloom Hash filtre renvoie beaucoup trop de collisions

Question

J'ai essayé d'implémenter mon propre filtre Bloom (simple) mais je suis bloqué sur le hachage, je comprends le concept de hachage de l'élément plusieurs fois et de remplir le tableau de bits avec les indices.

Cependant, je vois une tonne de collisions dans mon hachage, j'utilise un algorithme de hachage (j'ai essayé FNV, murmurhash et maintenant farmhash) avec diverses graines (basées sur les nanosecondes actuelles).

Je dois faire quelque chose de mal, je calcule les fonctions k en suivant les information here et en fixant la même quantité de graines.

Toute aide serait géniale, merci.

const farmhash = require('farmhash'); 
 

 
class BloomFilter { 
 
\t constructor(items, input) 
 
\t { 
 
\t \t const BITS_PER_ITEM = 15; //~0.1% false positive rate 
 
\t \t this.m = Buffer.alloc(items.length * BITS_PER_ITEM); // setup bit array 
 
\t \t this.k = Math.ceil(BITS_PER_ITEM * 0.7); // amount of hash functions we need to use 
 
\t \t this.seeds = []; 
 
\t \t this.input = input; 
 
\t \t this.items = items; 
 

 
\t \t this.setSeeds(); 
 
\t \t this.insertItems(); 
 
\t } 
 

 
\t get time() 
 
\t { 
 
\t \t let hrTime = process.hrtime() 
 
\t \t return hrTime[1]; 
 
\t } 
 

 
\t setSeeds() 
 
\t { 
 
\t \t for(let i = 0; i <= this.k; i++) this.seeds.push(this.time); 
 
\t } 
 
\t 
 
\t insertItems() 
 
\t { 
 
\t \t console.log('Total buffer size: ' + this.m.length); 
 

 
\t \t let collisions = 0; 
 
\t \t this.items.forEach(value => { \t \t \t 
 
\t \t \t this.getBufferIndices(value).map(index => { 
 
\t \t \t \t if(this.m[index] === 1) collisions++; 
 
\t \t \t \t this.m[index] = 1; 
 
\t \t \t }); 
 
\t \t }); 
 

 
\t \t console.log('Total collisions: ' + collisions); 
 
\t } 
 

 
\t getBufferIndices(value) 
 
\t { 
 
\t \t let indicies = []; 
 

 
\t \t this.seeds.forEach(seed => indicies.push(farmhash.hash32WithSeed(value, seed) % this.m.length)); 
 

 
\t \t return indicies; 
 
\t } 
 
} 
 

 
module.exports = BloomFilter;

Answer 1

D'après ce que je me souviens de filtres de Bloom, une collision se produit lorsque tous les k index pour une valeur particulière correspondent à ceux d'une valeur différente.

Il semble que vous ayez compté un compartiment (this.m[index]) ayant déjà été défini comme étant une collision.

Le code suivant (non testé) doit compter les collisions réelles:

let collisions = 0; 

this.items.forEach(value => {   
    let overlap = 0; 
    this.getBufferIndices(value).map(index => { 
    if(this.m[index] === 1) overlap++; 
    this.m[index] = 1; 
    }); 
    if (overlap === this.k) collisions++; 
}); 

Comme @Thomas souligne à juste titre dans son commentaire, au lieu d'utiliser .map() (qui crée un nouveau tableau), vous devez utiliser .forEach():

this.getBufferIndices(value).forEach(index, ...); 

Et getBufferIndices(), vous pouvez utiliser .map() au lieu de .forEach():

getBufferIndices(value) { 
    return this.seeds.map(seed => (farmhash.hash32WithSeed(value, seed) % this.m.length)); 
}