hashfunction 출력을 bloomfilter 인덱스에 매핑하는 방법은 무엇입니까?

Question

해시 함수 출력이 블룸 필터 인덱스에 매핑되는 방법에 대한 개요를 제공하여 도움을받을 수 있습니까? bloomfilters에 대한 개요는 다음과 같습니다.

Answer 1

해시 함수의 출력은 피어 필터 인덱스 사용되는 K 해시 기능별

에 매핑되는 방법을 개략적 그들은 블룸 필터만큼의 비트에 맵핑 해시는 해시 테이블의 해시 버킷에 매핑됩니다. 따라서 일반적으로 32 비트 정수를 생성하는 해시 함수를 말한 다음 계수 %을 사용하여 비트 인덱스 0 << i < n을 얻습니다. 여기서 n은 블룸 필터의 비트 수입니다.

은의 해시 함수가 0에서 2^32-1로 번호를 생성한다고 가정 해 봅시다 매우 구체적이를 만들려면, 당신의 꽃 필터 1000 비트가 있습니다 :

int bit_index = hash_function(input_value) % 1000; 

그것은 여기에 2 점에 유의하는 것이 중요합니다^32-1은 1000보다 훨씬 큽니다. 대신 해시 함수가 상당히 균등하게 분산 된 숫자를 생성했지만 0과 1023 사이의 숫자 만 생성하면 모듈러스 연산 후에 bit_index가 0..23에 두 배가 될 것입니다 (예를 들어, 입력 2와 1002 모두 포스트 모듈러스 값 2가되지만 입력 값 25 만 25가 출력되기 때문에). 이러한 이유로 32 비트를 생성하는 해시 함수가있는 경우 블룸 필터를 사용하여 2의 거듭 제곱 수의 크기로 블룸 필터를 사용하고 해시 값의 섹션을 슬라이스하여 독립 해시 함수처럼 사용할 수 있습니다 - 당신이 링크하는 위키피디아 기사에서 모두 설명했습니다. 해시 함수의 "클러스터링"결함은 그대로 출력을 통해 전달되므로 양질의 해시 함수가 필요합니다. 소수 비트를 갖는 것은 가난한 해싱을 완화하는 한 가지 방법입니다. 그럼에도 불구하고 좋은 해시 함수를 사용하면 2의 제곱으로 비트 연산을 사용하여 비트 인덱스를 쉽게 추출 할 수 있습니다. 필요한 경우 비트 모듈을 빠르게 변환 할 수 있습니다. 그러나 해시 함수는 전반적인 성능 프로파일 실제로 특히 나쁜

BOOST_STATIC_ASSERT(MD5_DIGEST_LENGTH >= sizeof(int)); 
int bit_index = *reinterpret_cast<unsigned int*>(p) % num_of_bloom_filter_bits; 

했다 : -

을 편집 MD5 기능의 데이터의 MD5_DIGEST_LENGTH 바이트에 unsigned char* "P"를 반환 가정 주소 코멘트 ...

, 난 당신이 시도 제안 아이디어 - 죄송합니다 - 나는 왜 그 순간 두 가지 이유를 설명 할 것입니다. 먼저, 무엇을하는지에 대한 질문에 대답하기 위해 : BOOST_STATIC_ASSERT()은 전달 된 표현식이 false으로 평가되면 컴파일 오류를 제공하도록 설계되었습니다. 여기에 기본적으로 MD5 해시 텍스트의 문자 크기 인 MD5_DIGEST_LENGTH은 최소한 int 정수 유형에 대해 시스템에서 사용하는 바이트 수만큼이어야한다는 요구 사항을 문서화하는 방법입니다. (그 크기는 아마 4 바이트이지만 8 일 수도 있습니다.)이 요구 사항은 다음 줄의 reinterpret_cast이 안전한지 확인하기위한 것입니다. MD5 해시의 텍스트 표현의 시작 부분에있는 바이트의 값을 읽은 것처럼 그 바이트에 int이있는 것처럼 읽습니다. 따라서 int 크기가 인 경우 4이며 MD5 해시는 댓글에서와 같이 "0cc175b9c0f1b6a831c399e269772661"입니다. 첫 번째 4 바이트는 "0cc1"입니다. 해당 텍스트의 ASCII 코드는 48, 99, 99, 49 십진수입니다.그들이 int으로 읽혀질 때, CPU의 엔디안에 따라 값은 다를 수 있지만, 기본적으로 256 * 3과 256 * 2에 세 번 더하기 256을 더한 숫자 중 하나를 얻을 것입니다 번호.

• 는 MD5 문자열의 각 문자는 두 숫자 (ASCII 코드 48-57) 또는 "A"를 통해 "F"편지입니다 :

  이유는 나는이 특히 나쁜 생각은했다 (97-102). 이 16 개의 값은 한 바이트가 가질 수있는 변형의 16 번째이며, 생성하는 int 값은 32 비트를 차지하지만 실제로는 2^16 개의 고유 값을 갖습니다.

• 일부 컴퓨터에서는 int이 2, 4, 8 등의 배수 인 메모리 주소에 정렬되어야합니다. reinterpret_cast - 호환되지 않는 주소에서 텍스트가 시작될 경우 컴퓨터가 중단 될 수 있습니다. 참고 : Intel & AMD는 정렬 요구 사항이 없지만 올바르게 정렬 된 데이터에서 작동하는 것이 더 빠를 수 있습니다.

그래서, 또 다른 제안은 다음의 MD5 표현이 데이터 버퍼보다 ​​짧았다 경우 BOOST_STATIC_ASSERT이 필요하지 않도록

다음

// create a buffer of the right size to hold a valid unsigned long in hex representation... 
char data[sizeof(unsigned long) * 2 + 1]; 

// copy as much of the md5 text as will fit into the buffer, NUL terminating it... 
sprintf(data, "%.*s", sizeof data - 1, md5); 

// convert to an unsigned long... 
m = strtoul(data, /*endptr*/ NULL, /*base*/ 16); 

, 그것은 단지 초기 부분은 안전하게 복사 할 수있다.

비 암호화 해시 함수를 사용하는 것이 훨씬 쉽습니다. 일반적으로 숫자의 readble 텍스트 버퍼 표현이 ​​아닌 숫자를 반환하기 때문에 모든 넌센스를 피할 수 있습니다.