计算c中布隆过滤器的汉明距离？

Question

我需要比较两个大小相等的布隆过滤器 BF1 和 BF2 使用 海明距离 将两组之间的距离表示为 Bloom Distance

B(BF1,BF2)=one(BF1 & BF2)/SIZEOF(BF1)
Where the one() function counts number of set bits in the ANDed bloom filter.

我采用了 Path similarity evaluation using Bloom filters 第 3 节（第 4 页。相似性指标）中的这个公式。

我已经实现了以下 C 代码来完成它，但它确实不起作用。

#include <stdlib.h>
#include <stdio.h>
const int BF_LEN= 1024;

char *BF1;//=malloc(BF_LEN*sizeof(char));
char *BF2;//=malloc(BF_LEN*sizeof(char));
char *buf;//=malloc(BF_LEN*sizeof(char));
char *buf_ptr=NULL;
int set_bits_count=0;
float similarity=0.0;

u_int32_t NumberOfSetBits(u_int32_t i)
{
    return (((((i - ((i >> 1) & 0x55555555)) & 0x33333333) + (((i - ((i >> 1) & 0x55555555)) >> 2) & 0x33333333) + (((i - ((i >> 1) & 0x55555555)) & 0x33333333) + (((i - ((i >> 1) & 0x55555555)) >> 2) & 0x33333333) >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

void main()
{
    BF1=malloc(BF_LEN*sizeof(char));
    BF2=malloc(BF_LEN*sizeof(char));
    buf=malloc(BF_LEN*sizeof(char));
 //Edit2:initialize them to 0
for(int j=0;j<BF_LEN;j++)    
        {
            BF1[j]='[=10=]';
            BF2[j]='[=10=]';
            buf[j]='[=10=]';
        }
    BF1="BF1 is filled with some characters";
    BF2="BF2 is filled with some characters and more";

    for(int j=0; j<BF_LEN; j++)
    {
        buf[j]=BF1[j]&BF2[j];
    }

    buf_ptr=buf;

    for(int m=0; m<BF_LEN; m++) //This is for the **one()** function
        set_bits_count+=NumberOfSetBits(*buf_ptr++);

    similarity=1-set_bits_count/(float)BF_LEN;
    printf("%.2f",similarity);
//Edit1: Following Comments
    free(BF1);
    free(BF2);
    free(buf);
}

NumberOfSetBits() 采用自 Set bit counter

Answer 1

请尝试使用此代码。汉明距离是异或的人口计数：

 void hamming()
 {
    static const unsigned int BF_LEN = 1024;

    char BF1[BF_LEN];
    char BF2[BF_LEN];

    unsigned int set_bits_count = 0;
    float similarity = 0.0f;

    memset(BF1,'[=10=]',BF_LEN);
    memset(BF2,'[=10=]',BF_LEN);
    strcpy(BF1, "BF1 is filled with some characters");
    strcpy(BF2, "BF2 is filled with some characters and more");

    for(unsigned int j = 0; j < BF_LEN; j += sizeof(T_Uint32))
    {
        set_bits_count += hammingDistance(*(T_Uint32*)&BF1[j], *(T_Uint32*)&BF2[j]);
    }


    similarity = 1.0f - set_bits_count/(float)BF_LEN;
    printf("%.2f", similarity);
}

//Reference: P. Wegner, Comm. ACM, Vol. 3, Issue 5, 1960. 
T_Uint getNrOfBitsSet(T_Uint32 bits)
{     
  T_Uint bitsSet = 0;

  while (bits)
  {
    bits &= bits - 1; // clears the least significant bit set
    ++bitsSet;
  }
  return bitsSet;
}

T_Uint hammingDistance(T_Uint32 a, T_Uint32 b)
{
    return getNrOfBitsSet(a^b);
}

计算c中布隆过滤器的汉明距离？

Calculate hamming distance of bloom filters in c?

c

bitwise-operators

hamming-distance

bitwise-and

bloom-filter