¿Cómo se correlaciona la salida de la función de hash con los índices de bloomfilter?

Question

¿Alguien me puede ayudar al proporcionar un esquema sobre cómo se asigna la salida de la función hash a los índices de filtro bloom? Aquí hay una descripción general en bloomfilters.

Answer 1

un esquema de cómo la salida de la función hash se asigna a una índices filtro Bloom

Para cada uno de los k funciones hash en uso, se asignan a un poco en el filtro de la floración tan hashes se asignan a cubos hash en una tabla hash. Por lo tanto, muy comúnmente podría decirse que una función hash genera enteros de 32 bits, luego use el operador de módulo % para obtener un índice de bit 0 << i < n donde n es la cantidad de bits en su filtro bloom.

Para que esto sea muy concreto, digamos que una función hash genera números de 0 a 2^32-1, y hay 1.000 bits en el filtro de la floración:

int bit_index = hash_function(input_value) % 1000; 

Es importante señalar aquí que 2^32-1 es masivamente mayor que 1000. Supongamos que la función hash generó números bastante distribuidos equitativamente pero solo entre 0 y 1023 inclusive, luego después de la operación del módulo sería dos veces más probable que bit_index estuviera en el 0..23 rango en comparación con 24..999 (porque, por ejemplo, las entradas 2 y 1002 dan como resultado un valor de módulo posterior de 2, pero solo una entrada de 25 produce una salida de 25). Por esa razón, si tiene una función hash que genera 32 bits, quizás desee usar un filtro de bloom del tamaño de una cantidad de bits que sea una potencia de dos, luego recorte secciones del valor hash para usarlo como si tuviera funciones hash independientes. - todo explicado en el artículo de wikipedia que vincula. Sin embargo, esto requiere una función hash de buena calidad, ya que cualquier falla de "agrupamiento" en la función hash pasará sin ser mitigada a la salida; tener un número primo de bits es una forma de mitigar dicho hash pobre. Aún así, con buenas funciones hash, las potencias de dos también facilitan la extracción de índices de bits utilizando operaciones AND a nivel de bit y, si es necesario, un desplazamiento de bit, que puede ser más rápido que el módulo entero, aunque las funciones hash probablemente van a empequeñecer esa consideración en el perfil de rendimiento general.

Editar - abordar los comentarios ...

Asumiendo que su función MD5 de devolver un "p" unsigned char* a MD5_DIGEST_LENGTH bytes de datos, me sugirieron intenta:

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

que en realidad era un particularmente malo idea - lo siento - explicaré las dos razones por qué en un momento. En primer lugar, para responder a su pregunta sobre lo que hace: BOOST_STATIC_ASSERT() está diseñado para darle un error de compilación si la expresión que ha pasado se ha evaluado como false. Aquí, básicamente es una forma de documentar el requisito de que MD5_DIGEST_LENGTH, que es el tamaño en caracteres de la representación textual del hash MD5, sea al menos tan larga como la cantidad de bytes que usa su sistema para un tipo entero int. (Ese tamaño es probablemente de 4 bytes, pero podría ser 8.) Ese requisito está destinado a garantizar que el reinterpret_cast en la siguiente línea sea seguro. Lo que hace es leer un valor de los bytes al comienzo de la representación textual del hash MD5 como si esos bytes contuvieran un int. Entonces, digamos que su int tamaño es 4, MD5 hash es "0cc175b9c0f1b6a831c399e269772661" como en su comentario: los primeros 4 bytes contienen "0cc1". Los códigos ASCII para ese texto son 48, 99, 99, 49 decimal.Cuando se leen en un int, dependiendo de la endianidad de la CPU, el valor puede variar, pero básicamente obtendrá uno de esos números multiplicado por 256^3 más otro multiplicado por 256^2 más un tercero por 256 más el final número.

Las razones por las que dijeron que esto era una mala idea en particular son:

• cada carácter de la cadena MD5 es o bien un dígito (códigos ASCII 48-57) o una carta de "a" a "f" (97-102). Esos 16 valores son una décimo sexta parte de la variación que un byte puede tener, y mientras que el valor int que usted genera ocupa 32 bits, en realidad solo obtiene 2^16 valores distintos.
• en algunas computadoras, int s deben alinearse en una dirección de memoria que es un múltiplo de 2, 4, 8 etc. El reinterpret_cast - si el texto comienza a comenzar en una dirección incompatible, podría bloquear su computadora. Nota: Los AMD de Intel & no tienen tal requisito de alineación, aunque puede ser más rápido para ellos operar con datos alineados correctamente.

Por lo tanto, otra sugerencia:

// 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); 

En este caso, si la representación MD5 fue más corto que el búfer de datos, sólo la parte inicial de la misma sería copiado de manera segura, por lo que no se requiere la BOOST_STATIC_ASSERT.

Es mucho más fácil utilizar una función hash no criptográfica, ya que generalmente solo le devolverá un número en lugar de una representación legible de texto legible del número, para que pueda evitar todas estas tonterías.