Encuentre eficientemente cuerdas binarias con baja distancia de hamming en un conjunto grande
https://stackoverflow.com/questions/6389841
-
29-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Problema:
Dada una lista grande (~ 100 millones) de enteros de 32 bits sin firmar, un valor de entrada entero de 32 bits sin firmar y un máximo Distancia de hamming, devuelva 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 secundaria, el bajo costo para consultar la estructura de datos es fundamental.
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, solo use una lista ordenada y haga una búsqueda binaria del valor de entrada específico.
Si la distancia de Hamming solo fuera 1, podría voltear cada broca en la entrada original y repetir las anteriores 32 veces.
¿Cómo puedo eficientemente (sin escanear toda la lista) descubrir a los miembros de la lista con una distancia de hamming> 1?
Solución
Pregunta: ¿Qué sabemos sobre la distancia de Hamming D (X, Y)?
Responder:
- No es negativo: d (x, y) ≥ 0
- Es solo cero para entradas idénticas: d (x, y) = 0 ⇔ x = y
- Es simétrico: d (x, y) = d (y, x)
- Obedece el desigualdad triangular, d (x, z) ≤ d (x, y) + d (y, z)
Pregunta: ¿Por qué nos importa?
Responder: Porque significa que la distancia de hamming es un métrico para espacio métrico. Hay algoritmos para indexar espacios métricos.
- Árbol métrico (Wikipedia)
- Bk-árbol (Wikipedia)
- Árbol mero (Wikipedia)
- Vicepresidente (Wikipedia)
- Árbol de cubierta (Wikipedia)
También puede buscar algoritmos para la "indexación espacial" en general, armado con el conocimiento de que su espacio no es euclidiano, sino que es un espacio métrico. Muchos libros sobre este tema Cubre la indexación de cadenas utilizando una métrica como la distancia de Hamming.
Nota: Si está comparando la distancia de hamming de las cadenas de ancho fijo, es posible que pueda obtener una mejora significativa del rendimiento mediante el uso de intrínsecos de ensamblaje o procesador. Por ejemplo, con GCC (manual) tu hiciste esto:
static inline int distance(unsigned x, unsigned y)
{
return __builtin_popcount(x^y);
}
Si luego le informa a GCC que está compilando una computadora con SSE4A, entonces creo que eso debería reducirse a solo un par de códigos de operación.
Editar: Según varias fuentes, esto a veces es/a menudo más lento que el código habitual de máscara/cambio/agregado. Benchmarking muestra que en mi sistema, una versión C de GCC superan a __builtin_popcount por alrededor del 160%.
Apéndice: Tenía curiosidad por el problema yo mismo, así que perfilé tres implementaciones: búsqueda lineal, árbol BK y vp árbol. Tenga en cuenta que los árboles VP y BK son muy similares. Los niños de un nodo en un árbol BK son "conchas" de árboles que contienen puntos que son 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 afuera. Por lo tanto, puede pensar en un nodo VP como un nodo BK con dos "conchas" muy gruesas en lugar de muchas más finas.
Los resultados fueron capturados en mi PC de 3.2 GHz, y los algoritmos no intentan utilizar múltiples núcleos (que deberían ser fáciles). Elegí un tamaño de base de datos de 100 m pseudorandom enteros. 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: 100m pseudorandom enteros
- Número de pruebas: 1000 para la distancia 1..5, 100 para la distancia 6..10 y lineal
- Resultados: # promedio de éxitos de consulta (muy aproximado)
- 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 tu comentario, mencionaste:
Creo que los árboles BK podrían mejorarse generando un montón de árboles BK con diferentes nodos raíz y extendiéndolos.
Creo que esta es exactamente la razón por la cual el árbol VP funciona (ligeramente) mejor que el árbol BK. Siendo "más profundo" en lugar de "menos profundo", se compara con más puntos en lugar de usar comparaciones de grano más fino contra menos puntos. Sospecho que las diferencias son más extremas en los espacios dimensionales superiores.
Un consejo final: los nodos de hoja en el árbol deben ser solo matrices de enteros planos para un escaneo lineal. Para conjuntos pequeños (tal vez 1000 puntos o menos), esto será más rápido y más eficiente en la memoria.
Otros consejos
Escribí una solución en la que represento los números de entrada en un bitset de 232 bits, por lo que puedo verificar o (1) si cierto número está en la entrada. Luego, para un número consultado y una distancia máxima, generé recursivamente todos los números dentro de esa distancia y los verifique con el bitset.
Por ejemplo, para la distancia máxima 5, esto es 242825 números (sumad = 0 a 5 {32 elige 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, 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, a 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 de bitset es, con mucho, la más rápida de los 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 232 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 dejar que el algoritmo resuelva al menos tres consultas y tantas consultas como pueda en aproximadamente 15 segundos (hago rondas con 1, 2, 4, 8, 16, etc. aprobado en total). Eso es bastante estable, incluso obtengo números similares por solo 1 segundo.
Mi CPU es una 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 el tree.c contiene todo el código y mi test.bat Muestra cómo compilé y corrí (usé las banderas de Dietrich's 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 o no desearse. En cuestión del caso del autor 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 trozos y consultar en estos trozos para una coincidencia exacta como paso previo al filtro. Si trabaja con archivos, crea tantos archivos como tiene fragmentos (por ejemplo, 4 aquí) con cada fragmento permitido en el frente y luego ordene los archivos. Puede usar una búsqueda binaria e incluso puede expandir su búsqueda arriba y debajo de un trozo coincidente para obtener bonificación.
Luego puede realizar un cálculo de distancia de hamming de bit en los resultados devueltos, que solo debería ser un subconjunto más pequeño de su conjunto de datos general. Esto se puede hacer utilizando archivos de datos o tablas SQL.
Entonces, para recapitular: digamos que tiene un montón de cadenas de 32 bits en un DB o archivos y que desea encontrar todos los hash que están a una distancia de 3 bits de hamming o menos de su cadena de bits "consulta":
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, crea cuatro archivos, cada uno es una permutación de los cortes que tienen Un "islice" en la parte delantera de cada "fila"
Corta tu cadena de bit de consulta de la misma manera en QSlice 1 a 4.
consulta esta tabla de tal manera que cualquiera de
qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Esto te da todas las cadenas que están dentro de 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.Para cada cadena de bits devuelta, calcule el par de parejas de distancia exacta con su cadena de bits de consulta (reconstruyendo las cadenas de bits del lado del índice de las cuatro rebanadas desde el DB o desde un archivo permutado)
El número de operaciones en el Paso 4 debe ser mucho menor que un cálculo de hamming completo en pares de toda su mesa y es muy eficiente en la práctica. Además, es fácil fragmentar los archivos en archivos más pequeños como necesidad de más velocidad utilizando el paralelismo.
Ahora, por supuesto, en su caso, está buscando una especie de auto unir, que son todos los valores que están a cierta distancia el uno del otro. El mismo enfoque aún funciona en mi humilde opinión, aunque tendrá que expandirse hacia arriba y hacia abajo desde un punto de partida para permutaciones (usando archivos o listas) que comparten el fragmento inicial y calculan la distancia de hamming para el clúster resultante.
Si se ejecuta en la memoria en lugar de los archivos, su conjunto de datos de Strings de 100 m 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 archivos mapeados de 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 Simhash de Moz, C ++ pero diseñado para cadenas de 64 bits y no 32 bits.
Este enfoque de distancia feliz limitada fue descrita por primera vez AFAIK por Moses Charikar En su seminal "Simhash" papel y el Google correspondiente patentar:
- Seguimiento de vecinos más cercanos al espacio de vecino más cercano en el espacio de Hamming
[...]
Vectores de bits dados que consisten en 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 permitidos por σ. Dado un vector de bit de consulta Q, encontramos al vecino más cercano aproximado al hacer 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 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 expandido en esto en su papel "Encontrar páginas web casi duplicadas: una evaluación a gran escala de algoritmos":
3.3 Los resultados para el algoritmo c
Participamos la cadena de bits de cada página en 12 piezas de 4 bytes no superpuestas, creando piezas de 20B, 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 diferencia de hasta 11, es decir, C-Similarity 373, pero podría perderse algunos para diferencias más grandes.
Esto también se explica en el periódico Detectar casi duplicados para rastreo web por Gurmeet Singh Manku, Arvind Jain y Anish Das Sarma:
- El problema de la distancia de hamming
Definición: Dada una colección de huellas digitales F -bit y una huella digital de consulta F, identifique si una huella digital existente difiere de F en la mayoría de los 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 2 huellas dactilares de 2 df bits. Concéntrese en los bits D más significativos de la tabla. Una lista de estos números de bits D equivale a "casi un contador" en el sentido de que (a) unas pocas combinaciones de bits 2 d existen, y (b) se duplican muy pocas combinaciones de bits D. Por otro lado, los bits de F - D menos significativos son "casi aleatorios".
Ahora elija D tal que | D - D | es un entero pequeño. Dado que la tabla está ordenada, una sola sonda es suficiente para identificar todas las huellas digitales que coinciden con las posiciones de bits más significativas. Desde | D - D | es pequeño, también se espera que el número de tales partidos sea pequeño. Para cada huella digital coincidente, podemos determinar fácilmente si difiere de F en la mayoría de las posiciones de bits o no (estas diferencias se restringirían naturalmente a las posiciones de bits menos importantes de F-D).
El procedimiento descrito anteriormente nos ayuda a localizar una huella digital existente que difiere de las posiciones de b bit, todos los cuales están restringidos para estar entre los bits de F-D menos significativos de F. Esto se encarga de un buen número de casos. Para cubrir todos los casos, es suficiente 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 un Pregunta relacionada solo con DB
Puede precomputar 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 rápido "no" 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 Bloom, y revíselos uno a la vez. Optimice el tamaño de su filtro de floración para las compensaciones de velocidad / memoria.
No estoy seguro de si todo funciona exactamente, pero parece un buen enfoque si tienes un ram de tiempo de ejecución para quemar y estás dispuesto a pasar mucho tiempo en precomputación.
¿Qué tal ordenar la lista y luego hacer una búsqueda binaria en esa lista ordenada en los diferentes valores posibles dentro de la distancia de Hamming?
Un enfoque posible para resolver este problema es usar un Estructura de datos de set de disjusto. 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 todos los posibles valor con 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 calculado valor, prueba 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 sindicales ejecutadas en una variable.
Comienza el algoritmo con n conjuntos de disjunto (donde n es el número de elementos en la entrada). Cada vez que ejecuta una operación sindical, disminuye en 1 el número de conjuntos disjuntos. Cuando el algoritmo termina, la estructura de datos del conjunto de disjunto tendrá todos los valores con la distancia de hamming <= k agrupado en conjuntos disjuntos. Esta estructura de datos del conjunto disjunto se puede calcular en casi tiempo lineal.
