algorithm - impar - Encuentra de manera eficiente cadenas binarias con poca distancia de Hamming en un conjunto grande

hamming code

Question

Problema:

Dada una lista grande (~ 100 millones) de enteros sin signo de 32 bits, un valor de entrada entero sin signo de 32 bits y una Distancia de Hamming máxima, devuelve todos los miembros de la lista que están dentro de la Distancia de Hamming especificada del valor de entrada.

La estructura de datos real para mantener la lista está abierta, los requisitos de rendimiento dictan una solución en la memoria, el costo para construir la estructura de datos es secundario, el bajo costo para consultar la estructura de datos es crítico.

Ejemplo:

For a maximum Hamming Distance of 1 (values typically will be quite small)
And input:
00001000100000000000000001111101
The values:
01001000100000000000000001111101
00001000100000000010000001111101
should match because there is only 1 position in which the bits are different.
11001000100000000010000001111101
should not match because 3 bit positions are different.

Mis pensamientos hasta ahora:

Para el caso degenerado de una Distancia de Hamming de 0, simplemente use una lista ordenada y realice una búsqueda binaria para el valor de entrada específico.

Si la distancia de Hamming solo fuera 1, podría voltear cada bit en la entrada original y repetir las 32 veces anteriores.

¿Cómo puedo de manera eficiente (sin escanear toda la lista) descubrir miembros de la lista con una Distancia de Hamming> 1.

Answer 1

¿Qué hay de ordenar la lista y luego hacer una búsqueda binaria en esa lista ordenada en los diferentes valores posibles dentro de su Hamming Distance?

Answer 2

Escribí una solución en la que represento los números de entrada en un conjunto de bits de 2 ³² bits, por lo que puedo verificar en O (1) si hay un cierto número en la entrada. Luego, para un número consultado y una distancia máxima, genero recursivamente todos los números dentro de esa distancia y los comparo contra el conjunto de bits.

Por ejemplo, para la distancia máxima 5, esto es 242825 números ( suma _{d = 0 a 5} {32 elegir d} ). A modo de comparación, la solución de árboles VP de Dietrich Epp, por ejemplo, atraviesa el 22% de los 100 millones de números, es decir, a través de 22 millones de números.

Utilicé el código / soluciones de Dietrich como base para agregar mi solución y compararla con la suya. Aquí hay velocidades, en consultas por segundo, para distancias máximas hasta 10:

Dist BK Tree VP Tree Bitset Linear
1 10,133.83 15,773.69 1,905,202.76 4.73
2 677.78 1,006.95 218,624.08 4.70
3 113.14 173.15 27,022.32 4.76
4 34.06 54.13 4,239.28 4.75
5 15.21 23.81 932.18 4.79
6 8.96 13.23 236.09 4.78
7 6.52 8.37 69.18 4.77
8 5.11 6.15 23.76 4.68
9 4.39 4.83 9.01 4.47
10 3.69 3.94 2.82 4.13
Prepare 4.1s 21.0s 1.52s 0.13s
times (for building the data structure before the queries)

Para distancias pequeñas, la solución de conjunto de bits es por mucho la más rápida de las cuatro. El autor de la pregunta, Eric, comentó a continuación que la mayor distancia de interés probablemente sea de 4 a 5. Naturalmente, mi solución de bitset se vuelve más lenta para distancias más grandes, incluso más lenta que la búsqueda lineal (para la distancia 32, pasaría por 2 ³² números). Pero para la distancia 9, sigue siendo fácil.

También modifiqué las pruebas de Dietrich. Cada uno de los resultados anteriores es para permitir que el algoritmo resuelva al menos tres consultas y tantas consultas como sea posible en aproximadamente 15 segundos (hago rondas con consultas de 1, 2, 4, 8, 16, etc., hasta que hayan transcurrido al menos 10 segundos) pasado en total). Eso es bastante estable, incluso obtengo números similares por solo 1 segundo.

Mi CPU es un i7-6700. Mi código (basado en Dietrich) está aquí (ignore la documentación allí al menos por ahora, no estoy seguro de qué hacer al respecto, pero tree.c contiene todo el código y mi test.bat muestra cómo compilé y ejecuté (utilicé) las banderas del Makefile de Dietrich)). Acceso directo a mi solución .

Una advertencia: los resultados de mi consulta contienen números solo una vez, por lo tanto, si la lista de entrada contiene números duplicados, puede ser deseable o no. En el caso del autor Eric, no hubo duplicados (ver comentario más abajo). En cualquier caso, esta solución podría ser buena para personas que no tienen duplicados en la entrada o no quieren o necesitan duplicados en los resultados de la consulta (creo que es probable que los resultados de la consulta pura sean solo un medio para un final y luego algún otro código convierte los números en otra cosa, por ejemplo, un mapa mapeando un número a una lista de archivos cuyo hash es ese número).

Answer 3

Puede precomputar todas las variaciones posibles de su lista original dentro de la distancia hamming especificada y almacenarla en un filtro bloom. Esto le da un "NO" rápido pero no necesariamente una respuesta clara sobre "SÍ".

Para SÍ, almacene una lista de todos los valores originales asociados con cada posición en el filtro de floración, y examínelos de uno en uno. Optimice el tamaño de su filtro de floración para intercambios de velocidad / memoria.

No estoy seguro de si todo funciona exactamente, pero parece un buen enfoque si tiene memoria RAM en tiempo de ejecución para grabar y está dispuesta a pasar mucho tiempo en precomputación.

Answer 4

Un enfoque común (al menos común para mí) es dividir la cadena de bits en varios fragmentos y consultar en estos fragmentos para una coincidencia exacta como paso de prefiltrado. Si trabaja con archivos, puede crear tantos archivos como bloques (por ejemplo, 4 aquí) con cada fragmento permutado al frente y luego ordenar los archivos. Puedes utilizar una búsqueda binaria e incluso puedes expandir tu búsqueda por encima y por debajo de un fragmento correspondiente para obtener bonificaciones.

A continuación, puede realizar un cálculo de distancia hamming bit a bit en los resultados devueltos, que debería ser solo un subconjunto más pequeño de su conjunto de datos general. Esto se puede hacer usando archivos de datos o tablas SQL.

Entonces, para recapitular: supongamos que tiene un conjunto de cadenas de 32 bits en una base de datos o archivos y que quiere encontrar cada hash que se encuentre a 3 bits o menos de la cadena de bits de "consulta":

1. cree una tabla con cuatro columnas: cada una contendrá una porción de 8 bits (como una cadena o int) de los hash de 32 bits, islice 1 a 4. O si usa archivos, cree cuatro archivos, cada uno de los cuales es una permutación de las rebanadas que tienen un "islice" al frente de cada "fila"

2. corte su cadena de bits de consulta de la misma manera en qslice 1 a 4.

3. consulte esta tabla de manera que cualquiera de qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4 . Esto le proporciona cada cadena que está dentro de 7 bits ( 8 - 1 ) de la cadena de consulta. Si usa un archivo, realice una búsqueda binaria en cada uno de los cuatro archivos permutados para obtener los mismos resultados.

4. para cada cadena de bits devuelta, calcule la distancia de exclusión exacta por pares con la cadena de bits de consulta (reconstruyendo las cadenas de bits del lado del índice de las cuatro divisiones, ya sea desde el DB o desde un archivo permutado)

El número de operaciones en el paso 4 debe ser mucho menor que el cálculo completo de la tabla completa y es muy eficiente en la práctica. Además, es fácil fragmentar los archivos en archivos más pequeños a medida que se necesita más velocidad usando el paralelismo.

Ahora, por supuesto, en su caso, usted está buscando una auto unión de género, es decir, todos los valores que se encuentran a cierta distancia el uno del otro. El mismo enfoque todavía funciona en mi humilde opinión, aunque tendrá que expandirse hacia arriba y hacia abajo desde un punto de partida para las permutaciones (usando archivos o listas) que comparten el fragmento de inicio y calcular la distancia de martillado para el clúster resultante.

Si se ejecuta en memoria en lugar de archivos, su conjunto de datos de cadenas de 100M 32 bits estaría en el rango de 4 GB. Por lo tanto, las cuatro listas permutadas pueden necesitar alrededor de 16 GB + de RAM. Aunque obtengo excelentes resultados con los archivos mapeados en memoria en su lugar y debo tener menos RAM para los conjuntos de datos de tamaño similar.

Hay implementaciones de código abierto disponibles. Lo mejor en el espacio es, en mi humilde opinión, el hecho para Simhash por Moz , C ++ pero diseñado para cadenas de 64 bits y no para 32 bits.

Este enfoque de la distancia de corte delimitada fue descrito por primera vez por Moses Charikar en su documento seminal "simhash" y en la correspondiente patent Google:

5. BÚSQUEDA CERCANA MÁS CERCANA APROXIMADA EN EL ESPACIO MARÍTIMO

[...]

Dados vectores de bits que constan de d bits cada uno, elegimos N = O (n 1 / (1+)) permutaciones aleatorias de los bits. Para cada permutación aleatoria σ, mantenemos un orden ordenado O σ de los vectores de bits, en orden lexicográfico de los bits permutados por σ. Dado un vector de bits de consulta q, encontramos el vecino más cercano aproximado haciendo lo siguiente:

Para cada permutación σ, realizamos una búsqueda binaria en O σ para localizar los dos vectores de bit más cercanos a q (en el orden lexicográfico obtenido por bits permutados por σ). Ahora buscamos en cada una de las órdenes ordenadas O σ examinando los elementos por encima y por debajo de la posición devuelta por la búsqueda binaria en orden de la longitud del prefijo más largo que coincide con q.

Monika Henziger amplió esto en su artículo "Encontrar páginas web casi duplicadas: una evaluación a gran escala de algoritmos" :

3.3 Los resultados para el algoritmo C

Dividimos la cadena de bits de cada página en 12 piezas de 4 bytes que no se superponen, creando 20B piezas y calculamos la similitud en C de todas las páginas que tenían al menos una pieza en común. Se garantiza que este enfoque encuentre todos los pares de páginas con una diferencia de hasta 11, es decir, la similitud C 373, pero podría pasar por alto algunas diferencias más grandes.

Esto también se explica en el documento Detecting Near-Duplicates para rastreo web por Gurmeet Singh Manku, Arvind Jain y Anish Das Sarma:

3. EL PROBLEMA DE LA DISTANCIA DE HAMMING

Definición: Dada una colección de huellas dactilares f-bit y una huella dactilar F de consulta, identifique si una huella digital existente difiere de F en un máximo de k bits. (En la versión de modo por lotes del problema anterior, tenemos un conjunto de huellas dactilares de consulta en lugar de una huella digital de consulta única)

[...]

Intuición: considere una tabla ordenada de 2 df-bit huellas digitales verdaderamente al azar. Concéntrese solo en los bits más significativos de la tabla. Una lista de estos números de d-bit equivale a "casi un contador" en el sentido de que (a) existen bastantes combinaciones de bits de 2 d, y (b) muy pocas combinaciones de d-bits están duplicadas. Por otro lado, los bits f - d menos significativos son "casi aleatorios".

Ahora elija d tal que | d - d | es un pequeño entero. Dado que la tabla está ordenada, basta con una sola sonda para identificar todas las huellas dactilares que coinciden con F en las posiciones de bit más significativas. Desde | d - d | es pequeño, también se espera que el número de tales coincidencias sea pequeño. Para cada huella dactilar coincidente, podemos deducir fácilmente si difiere de F en la mayoría de las k posiciones de bit o no (estas diferencias estarían restringidas naturalmente a las posiciones de bit f-d menos significativas).

El procedimiento descrito anteriormente nos ayuda a ubicar una huella dactilar existente que difiere de F en k posiciones de bits, todas las cuales están restringidas a estar entre los bits f - d menos significativos de F. Esto se ocupa de un buen número de casos. Para cubrir todos los casos, basta con construir un pequeño número de tablas ordenadas adicionales, como se describe formalmente en la siguiente sección.

Nota: publiqué una respuesta similar a una pregunta relacionada con DB solo

Answer 5

Un posible enfoque para resolver este problema es usar una estructura de datos Disjoint-set . La idea es fusionar miembros de la lista con la distancia de Hamming <= k en el mismo conjunto. Aquí está el esquema del algoritmo:

• Para cada miembro de la lista, calcule cada valor posible con la distancia de Hamming <= k. Para k = 1, hay 32 valores (para valores de 32 bits). Para k = 2, 32 + 32 * 31/2 valores.

  • Para cada valor calculado, prueba si está en la entrada original. Puede usar una matriz con tamaño 2 ^ 32 o un mapa hash para hacer esta comprobación.

  • Si el valor está en la entrada original, realice una operación de "unión" con el miembro de la lista .

  • Mantenga el número de operaciones de unión ejecutadas en una variable.

Comienza el algoritmo con N conjuntos disjuntos (donde N es el número de elementos en la entrada). Cada vez que ejecuta una operación de unión, disminuye en 1 la cantidad de conjuntos disjuntos. Cuando el algoritmo finaliza, la estructura de datos disjuntos tendrá todos los valores con la distancia de Hamming <= k agrupados en conjuntos disjuntos. Esta estructura de datos disjuntos se puede calcular en tiempo casi lineal .

Answer 6

Pregunta: ¿Qué sabemos sobre la distancia de Hamming d (x, y)?

Responder:

1. No es negativo: d (x, y) ≥ 0
2. Solo es cero para entradas idénticas: d (x, y) = 0 ⇔ x = y
3. Es simétrico: d (x, y) = d (y, x)
4. Obedece a la desigualdad del triángulo , d (x, z) ≤ d (x, y) + d (y, z)

Pregunta: ¿Por qué nos importa?

Respuesta: Porque significa que la distancia de Hamming es una métrica para un espacio métrico . Hay algoritmos para indexar espacios métricos.

• Árbol métrico (Wikipedia)
• BK-tree (Wikipedia)
• M-tree (Wikipedia)
• VP-tree (Wikipedia)
• Árbol de portada (Wikipedia)

También puede buscar algoritmos para "indexación espacial" en general, armados con el conocimiento de que su espacio no es euclidiano, sino que es un espacio métrico. Muchos libros sobre este tema cubren la indexación de cadenas usando una métrica como la distancia de Hamming.

Nota al pie: Si está comparando la distancia de Hamming de las cadenas de ancho fijo, es posible que pueda obtener una mejora significativa en el rendimiento mediante el uso de intrínsecos de ensamblaje o procesador. Por ejemplo, con GCC ( manual ) haces esto:

static inline int distance(unsigned x, unsigned y)
{
return __builtin_popcount(x^y);
}

Si luego informa a GCC que está compilando para una computadora con SSE4a, entonces creo que debería reducirse a solo un par de códigos de operación.

Editar: Según varias fuentes, a veces / a menudo es más lento que el código de máscara / cambio / adición habitual. La evaluación comparativa muestra que en mi sistema, una versión C supera a la __builtin_popcount de GCC en aproximadamente un 160%.

Adición: tenía curiosidad sobre el problema, por lo que perfilé tres implementaciones: búsqueda lineal, árbol BK y árbol VP. Tenga en cuenta que los árboles VP y BK son muy similares. Los hijos de un nodo en un árbol BK son "caparazones" de árboles que contienen puntos que están cada uno a una distancia fija del centro del árbol. Un nodo en un árbol VP tiene dos hijos, uno que contiene todos los puntos dentro de una esfera centrada en el centro del nodo y el otro niño que contiene todos los puntos externos. Así que puedes pensar en un nodo VP como un nodo BK con dos "shells" muy gruesas en lugar de muchos más finos.

Los resultados fueron capturados en mi PC a 3.2 GHz, y los algoritmos no intentan utilizar múltiples núcleos (lo cual debería ser fácil). Elegí un tamaño de base de datos de 100M enteros pseudoaleatorios. Los resultados son el promedio de 1000 consultas para la distancia 1..5 y 100 consultas para 6..10 y la búsqueda lineal.

• Base de datos: enteros pseudoaleatorios 100M
• Número de pruebas: 1000 para la distancia 1..5, 100 para la distancia 6..10 y lineal
• Resultados: # promedio de aciertos de consulta (muy aproximados)
• Velocidad: número de consultas por segundo
• Cobertura: porcentaje promedio de la base de datos examinada por consulta

-- BK Tree -- -- VP Tree -- -- Linear -- Dist Results Speed Cov Speed Cov Speed Cov 1 0.90 3800 0.048% 4200 0.048% 2 11 300 0.68% 330 0.65% 3 130 56 3.8% 63 3.4% 4 970 18 12% 22 10% 5 5700 8.5 26% 10 22% 6 2.6e4 5.2 42% 6.0 37% 7 1.1e5 3.7 60% 4.1 54% 8 3.5e5 3.0 74% 3.2 70% 9 1.0e6 2.6 85% 2.7 82% 10 2.5e6 2.3 91% 2.4 90% any 2.2 100%

En su comentario, usted mencionó:

Creo que los BK-trees podrían mejorarse mediante la generación de un montón de árboles BK con diferentes nodos de raíz y su diseminación.

Creo que esta es exactamente la razón por la cual el árbol VP se comporta (ligeramente) mejor que el árbol BK. Al ser "más profundo" en lugar de "menos profundo", se compara con más puntos en lugar de utilizar comparaciones más precisas con menos puntos. Sospecho que las diferencias son más extremas en los espacios dimensionales superiores.

Un consejo final: los nodos de hojas en el árbol deberían ser matrices planas de enteros para un escaneo lineal. Para juegos pequeños (tal vez 1000 puntos o menos) esto será más rápido y más eficiente en la memoria.