cadenas de clasificación de manera que la distancia de Hamming es baja entre las cuerdas adyacentes

Question

Problema:

tengo N (~ 100k-1m) cuerdas cada D (por ejemplo, 2000) caracteres de longitud y con un alfabeto baja (por ejemplo 3 caracteres posibles) Me gustaría ordenar estas cadenas de manera que haya tan pocos cambios posibles entre cadenas adyacentes (por ejemplo, la distancia cortada es baja). La solución no tiene que ser lo mejor posible, pero cuanto más cerca, mejor.

Ejemplo

N=4 
D=5 
//initial strings 
1. aaacb 
2. bacba 
3. acacb 
4. cbcba 

//sorted so that hamming distance between adjacent strings is low 
1. aaacb 
3. acacb (Hamming distance 1->3 = 1) 
4. cbcba (Hamming distance 3->4 = 4) 
2. bacba (Hamming distance 4->2 = 2) 

Pensamientos sobre el problema

que tienen una mala sensación de que esto es un problema no trivial. Si pensamos en cada cadena como un nodo y las distancias a otras cadenas como una ventaja, entonces estamos viendo un problema de vendedor ambulante. La gran cantidad de cadenas significa que el cálculo de todas las distancias por pares de antemano es potencialmente inviable, creo que convertir el problema en algo más como el Canadian Traveller Problem.

Por el momento mi solución ha sido utilizar un VP tree para encontrar una solución tipo codicioso vecino más cercano al problema

curr_string = a randomly chosen string from full set 
while(tree not empty) 
    found_string = find nearest string in tree 
    tree.remove(found_string) 
    sorted_list.add(curr_string) 
    curr_string = found_string 

pero los resultados iniciales parecen ser pobre. Las cadenas hash para que otras más similares estén más cerca pueden ser otra opción, pero sé muy poco acerca de qué tan buena será la solución que esto proporcionará o qué tan bien se escalará a datos de este tamaño.

Answer 1

Incluso si considera este problema como similar al problema del vendedor ambulante (TSP), creo que las distancias de Hamming seguirán la desigualdad del triángulo (Hamming (A, B) + Hamming (B, C) ≤ Hamming (A, B, C)), por lo que en realidad solo se trata de ΔTSP (el problema del vendedor ambulante métrico), para el cual hay una serie de algoritmos que ofrecen buenas aproximaciones con un resultado ideal. En particular, el Christofides algorithm siempre le dará una ruta de 1,5 veces la longitud mínima posible.

Answer 2

Sí Esto es una Traveling salesman problem, pero no sé si alguna de las docenas de programas bajo TSP source code library puede hacer 1M puntos hacia arriba, con un plug-in métrica.

Un posible enfoque de 2 etapas:

1) Dividir los puntos 1M en 50 agrupaciones con un Nearest neighbor search. Haga TSP en los 50 centros de clúster.

2) poner todos los 1M - 50 puntos entre los 2 centros más cercanos; haga TSP en cada cadena de 1M/50. Aquí "50" podría ser 100 o 1000. Si 1000 es demasiado grande, recurse: divida 1000 en 30 clústeres de ~ 30 cada uno.

K-means puede agrupar 1M puntos, pero una vez más no sé de una implementación rápida con la métrica del complemento. Véase, no obstante scikit-learn clustering

Para encontrar un centro de gravedad de N puntos, uno que minimiza | centro - todos los demás |, que puede vencer yo sepa O (n^2) sólo por tomando lo mejor de una muestra aleatoria de decir sqrt (N) - debería ser lo suficientemente bueno. (O google/haga una pregunta por separado sobre el centroide aproximado rápido).

Primero empaquete los datos para guardar los accesos de memoria en todo el flujo. En este caso, codifique a b c como 00 01 10 (distancia de Hamming entre cada par = 1): 2000 x 2 bits = 500 bytes. Fwiw, encontrar min Hammingdist (4k bits, 10k x 4k) lleva ~ 40 mseg en mi mac ppc.