Comprendre le filtre bloom

Question

je prenais un coup d'œil à l'exemple suivant: https://www.timdoug.com/etc/bloom_filter.c

pour essayer de comprendre le filtre bloom

-je obtenir à cette partie du code que je ne peux pas understnad:

for (i = 0; i < NUM_HASHES; i++) { 
     /* xor-fold the hash into FILTER_SIZE bits */ 
     hash[i] = (hash[i] >> FILTER_SIZE)^
        (hash[i] & FILTER_BITMASK); 
     /* set the bit in the filter */ 
     filter[hash[i] >> 3] |= 1 << (hash[i] & 7); 
    } 

Qu'est-ce qui se passe exactement ici et pourquoi cela est-il effectué (je comprends les opérateurs mais je ne comprends pas pourquoi ils sont utilisés ici)

Answer 1

Pour moi cette partie de l'algorithme semble boguée (au moins dans le cas où FILTER_SIZE est censé être choisi librement): Supposons que FILTER_SIZE est 10 (plutôt que 20). L'expression (hash[i] >> FILTER_SIZE) peut alors donner un résultat avec 22 bits (plutôt que 12), ce qui conduira plus tard à un accès au filtre hors limites.

maintenant à l'explication: Le but de l'expression

hash[i] = (hash[i] >> FILTER_SIZE)^(hash[i] & FILTER_BITMASK); 

est de transformer hachage [i] dans un index de bit valide (plus quelques randomizing avec l'aide de l'opération ^). Pour faciliter la compréhension, laissons de côté le peu de confusion avec l'opérateur^(peut facilement être ajouté à nouveau). Ensuite, l'algorithme pourrait (de façon plus propre, et, espérons-le, correctement pour toutes les valeurs de FILTER_SIZE) être réécrit comme:

for (i = 0; i < NUM_HASHES; ++i) { 
    unsigned int bitIndex = hash[i] % (FILTER_SIZE_BYTES * 8); 
    unsigned int byteIndex = bitIndex/8; 
    unsigned int bitInByte = bitIndex % 8; 
    filter[byteIndex] |= (1 << bitInByte); 
}