Encuentre de manera eficiente cadenas binarias con una distancia de Hamming baja en un conjunto grande

Problema:

Dada una lista grande (~ 100 millones) de enteros de 32 bits sin signo, un valor de entrada entero de 32 bits sin signo 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 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 haga 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 lo anterior 32 veces.

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

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

Responder:

1. No es negativo: d (x, y) ≥ 0
2. Es solo 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 . Existen algoritmos para indexar espacios métricos.

• Árbol métrico (Wikipedia)
• Árbol BK (Wikipedia)
• Árbol M (Wikipedia)
• VP-árbol (Wikipedia)
• Árbol de cobertura (Wikipedia)

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

Nota a pie de página: si está comparando la distancia de Hamming de cadenas de ancho fijo, es posible que pueda obtener una mejora significativa del rendimiento mediante el uso de componentes intrínsecos del ensamblaje o del 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, creo que debería reducirse a solo un par de códigos de operación.

Editar: De acuerdo con varias fuentes, esto es a veces / a menudo más lento que el código habitual de máscara / cambio / agregar. La evaluación comparativa muestra que en mi sistema, una versión C supera a las GCC __builtin_popcounten aproximadamente un 160%.

Anexo: Yo mismo tenía curiosidad por el problema, por lo que describí 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 "capas" 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 hijo que contiene todos los puntos externos. Por tanto, puede pensar en un nodo VP como un nodo BK con dos "capas" muy gruesas en lugar de muchas más finas.

Los resultados se capturaron en mi PC de 3,2 GHz y los algoritmos no intentan utilizar varios núcleos (lo que debería ser fácil). Elegí un tamaño de base de datos de 100 millones de 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: 100 millones de enteros pseudoaleatorios
• Número de pruebas: 1000 para distancia 1..5, 100 para distancia 6..10 y lineal
• Resultados: número medio de consultas (muy aproximado)
• Velocidad: número de consultas por segundo
• Cobertura: porcentaje promedio de base de datos examinada por consulta

                - Árbol BK - - Árbol VP - - Lineal -
Dist Resultados Velocidad Cov Velocidad Cov Velocidad Cov
1 0,90 3800 0,048% 4200 0,048%
2 11300 0,68% 330 0,65%
3130 56 3,8% 63 3,4%
4970 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%
cualquiera 2.2 100%

En su comentario, mencionó:

Creo que los árboles BK podrían mejorarse generando un grupo de árboles BK con diferentes nodos de raíz y extendiéndolos.

Creo que esta es exactamente la razón por la que el árbol VP funciona (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 detalladas con menos puntos. Sospecho que las diferencias son más extremas en espacios de dimensiones superiores.

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

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 de forma recursiva todos los números dentro de esa distancia y los comparo con el conjunto de bits.

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

Usé el código / soluciones de Dietrich como base para agregar mi solución y compararla con la suya. Estas son las velocidades, en consultas por segundo, para distancias máximas de 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 bitset es, con 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 sería 4-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, todavía conduce fácilmente.

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 pueda en aproximadamente 15 segundos (hago rondas con consultas de 1, 2, 4, 8, 16, etc., hasta que hayan transcurrido al menos 10 segundos aprobado 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 el de Dietrich) está aquí (ignore la documentación allí al menos por ahora, no estoy seguro de qué hacer al respecto, pero tree.ccontiene todo el código y mi test.batmuestra cómo compilé y ejecuté (utilicé las banderas de Dietrich Makefile)) . Atajo a mi solución .

Una advertencia: los resultados de mi consulta contienen números solo una vez, por lo que si la lista de entrada contiene números duplicados, eso puede ser deseable o no. En el caso del autor de la pregunta Eric, no hubo duplicados (ver comentario a continuación). En cualquier caso, esta solución podría ser buena para las 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 fin y luego algún otro código convierte los números en otra cosa, por ejemplo, un mapa que asigna un número a una lista de archivos cuyo hash es ese número).

Un enfoque común (al menos común para mí) es dividir su cadena de bits en varios fragmentos y consultar estos fragmentos para obtener una coincidencia exacta como paso previo al filtro. Si trabaja con archivos, cree tantos archivos como fragmentos tenga (por ejemplo, 4 aquí) con cada fragmento permutado al frente y luego clasifique los archivos. Puede usar una búsqueda binaria e incluso puede expandir su búsqueda por encima y por debajo de una parte correspondiente para obtener una bonificación.

Luego, puede realizar un cálculo de la distancia de Hamming bit a bit en los resultados devueltos, que deberían 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: digamos que tiene un montón de cadenas de 32 bits en una base de datos o archivos y que desea encontrar cada hash que se encuentre dentro de una distancia de Hamming de 3 bits o menos de su 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 hashes de 32 bits, islice 1 a 4. O si usa archivos, cree cuatro archivos, cada uno siendo 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. consultar esta tabla de modo que cualquiera de qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Esto le proporciona todas las cadenas que están dentro de los 7 bits ( 8 - 1) de la cadena de consulta. Si usa un archivo, haga 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 hamming exacta por pares con su cadena de bits de consulta (reconstruyendo las cadenas de bits del lado del índice a partir de las cuatro secciones, ya sea desde la base de datos o desde un archivo permutado)

El número de operaciones en el paso 4 debería ser mucho menor que un cálculo hamming completo por pares de toda la tabla y es muy eficiente en la práctica. Además, es fácil fragmentar los archivos en archivos más pequeños si se necesita más velocidad mediante el paralelismo.

Ahora, por supuesto, en su caso, está buscando un tipo de autounión, es decir, todos los valores que están a cierta distancia entre sí. El mismo enfoque todavía funciona en mi humilde opinión, aunque tendrá que expandir hacia arriba y hacia abajo desde un punto de partida para las permutaciones (usando archivos o listas) que comparten el fragmento inicial y calcular la distancia de hamming para el grupo resultante.

Si se ejecuta en memoria en lugar de archivos, su conjunto de datos de cadenas de 32 bits de 100M 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 archivos mapeados en memoria y debo menos RAM para 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 de 32 bits.

Este enfoque distancia happing acotada fue descrita por primera AFAIK por Moses Charikar en su "simhash" seminal papel y la correspondiente Google patente :

5. BÚSQUEDA APROXIMADA DE VECINOS MÁS CERCANOS EN EL ESPACIO DE HAMMING

[...]

Dados los 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 bits más cercanos a q (en el orden lexicográfico obtenido por bits permutados por σ). Ahora buscamos en cada uno de los órdenes ordenados O σ examinando los elementos arriba y abajo 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 del algoritmo C

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

Esto también se explica en el documento Detección de casi duplicados para rastreo web de Gurmeet Singh Manku, Arvind Jain y Anish Das Sarma:

3. EL PROBLEMA DE LA DISTANCIA DEL MARTILLO

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

[...]

Intuición: considere una tabla ordenada de huellas dactilares verdaderamente aleatorias de 2 df-bit. Concéntrese solo en los bits d 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 2 d bits, 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, una sola sonda es suficiente para identificar todas las huellas dactilares que coinciden con F en las posiciones de bit más significativas. Dado que | d - d | es pequeño, también se espera que el número de estos partidos sea pequeño. Para cada huella dactilar coincidente, podemos averiguar fácilmente si difiere de F en la mayoría de las k posiciones de bits o no (estas diferencias, naturalmente, se limitarían a las f - d posiciones de bits menos significativas).

El procedimiento descrito anteriormente nos ayuda a ubicar una huella digital 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 una pequeña cantidad de tablas adicionales ordenadas, como se describe formalmente en la siguiente sección.

Nota: publiqué una respuesta similar a una pregunta relacionada solo con base de datos

Puede calcular previamente todas las variaciones posibles de su lista original dentro de la distancia de hamming especificada y almacenarla en un filtro de floración. 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 revíselos uno por uno. Optimice el tamaño de su filtro de floración para compensaciones de velocidad / memoria.

No estoy seguro de si todo funciona exactamente, pero parece un buen enfoque si tiene RAM en tiempo de ejecución para grabar y está dispuesto a pasar mucho tiempo en el cálculo previo.

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

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

• Para cada miembro de la lista, calcule todos los valores posibles con una 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 , pruebe si está en la entrada original. Puede usar una matriz con tamaño 2 ^ 32 o un mapa hash para hacer esta verificació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.

El algoritmo se inicia 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 el número de conjuntos disjuntos. Cuando el algoritmo termina, la estructura de datos de conjuntos disjuntos tendrá todos los valores con distancia de Hamming <= k agrupados en conjuntos disjuntos. Esta estructura de datos de conjuntos disjuntos se puede calcular en un tiempo casi lineal .

Aquí hay una idea simple: haga un tipo de base de bytes de los enteros de entrada de 100 m, el byte más significativo primero, haciendo un seguimiento de los límites del cubo en los primeros tres niveles en alguna estructura externa.

Para realizar consultas, comience con un presupuesto de distancia de dy su palabra de entrada w. Para cada segmento en el nivel superior con valor de byte b, calcule la distancia de Hamming d_0entre by el byte superior de w. Busque de forma recursiva ese depósito con un presupuesto de d - d_0: es decir, para cada valor de byte b', d_1sea ​​la distancia de Hamming entre b'y el segundo byte de w. Busque de forma recursiva en la tercera capa con un presupuesto de d - d_0 - d_1, y así sucesivamente.

Tenga en cuenta que los cubos forman un árbol. Siempre que su presupuesto sea negativo, deje de buscar en ese subárbol. Si desciende de forma recursiva a una hoja sin gastar su presupuesto de distancia, ese valor de hoja debería ser parte de la salida.

Aquí hay una forma de representar la estructura del límite del depósito externo: tenga una matriz de longitud 16_777_216 ( = (2**8)**3 = 2**24), donde el elemento en el índice ies el índice inicial del depósito que contiene valores en el rango [256 * i, 256 * i + 255]. Para encontrar el índice uno más allá del final de ese depósito, busque el índice i + 1 (o use el final de la matriz para i + 1 = 2 ** 24).

El presupuesto de memoria es de 100 m * 4 bytes por palabra = 400 MB para las entradas y 2 ** 24 * 4 bytes por dirección = 64 MiB para la estructura de indexación, o apenas medio concierto en total. La estructura de indexación es una sobrecarga del 6.25% sobre los datos brutos. Por supuesto, una vez que haya construido la estructura de indexación, solo necesita almacenar el byte más bajo de cada palabra de entrada, ya que los otros tres están implícitos en el índice de la estructura de indexación, para un total de ~ (64 + 50) MB.

Si su entrada no se distribuye uniformemente, puede permutar los bits de sus palabras de entrada con una permutación (única, compartida universalmente) que coloca toda la entropía hacia la parte superior del árbol. De esa forma, el primer nivel de poda eliminará porciones más grandes del espacio de búsqueda.

Probé algunos experimentos, y esto funciona tan bien como la búsqueda lineal, a veces incluso peor. Hasta aquí esta idea elegante. Bueno, al menos es eficiente en memoria.