Рассчитать расстояние Хемминга для фильтров Блума в с? - PullRequest
Новая
       99

Рассчитать расстояние Хемминга для фильтров Блума в с?

0 голосов
/ 19 октября 2018

Мне нужно сравнить два одинаковых по размеру фильтра Блума BF1 и BF2 для их сходства, используя расстояние Хэмминга , которое выражает расстояние между двумя наборами как расстояние Блума

B (BF1, BF2) = один (BF1 и BF2) / SIZEOF (BF1)
Где функция one () считает числоустановленных битов в фильтре Блэда AND.

Я принял эту формулу из Оценка сходства путей с использованием фильтров Блума раздел 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]='\0';
            BF2[j]='\0';
            buf[j]='\0';
        }
    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 () Принята с Установить счетчик битов

1 Ответ

0 голосов
/ 19 октября 2018

Пожалуйста, попробуйте этот код.Дистанция Хэмминга - это численность населения с XOR: 

 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,'\0',BF_LEN);
    memset(BF2,'\0',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);
}
...