Cómo encontrar el vector más cercano en {0,1,2}^12, una y otra vez

Question

Estoy buscando un espacio de vectores de longitud 12, con entradas 0, 1, 2. Por ejemplo, uno de esos vectores es
001122001122. Tengo alrededor de mil buenos vectores y cerca de mil vectores malos. Para cada vector malo, necesito ubicar el vector bueno más cercano. La distancia entre dos vectores es solo el número de coordenadas que no coinciden. Los buenos vectores no están especialmente bien organizados, y la razón por la que son "buenos" no parece ser útil aquí. Mi principal prioridad es que el algoritmo sea rápido.

Si hago una búsqueda simple y exhaustiva, tengo que calcular unas 1000 * 1000 distancias. Eso parece bastante espeluznante.

Si aplico el algoritmo de Dijkstra primero usando los vectores buenos, puedo calcular el vector más cercano y la distancia mínima para cada vector en el espacio, de modo que cada vector malo requiera una búsqueda simple. Pero el espacio tiene 3^12 = 531,441 vectores, por lo que la precomputación es de medio millón de cálculos de distancia. No hay mucho ahorro.

¿Puede ayudarme a pensar en una mejor manera?

Editar: Desde que las personas preguntaron seriamente qué los hace "buenos": Cada vector representa una descripción de una imagen hexagonal de seis triángulos equiláteros, que es la imagen 2D de una disposición 3D de cubos (piense en Q-bert generalizado). Los triángulos equiláteros son mitades de caras de cubos (45-45-90), inclinados en perspectiva. Seis de las coordenadas describen la naturaleza del triángulo (piso percibido, pared izquierda, pared derecha), y seis coordenadas describen la naturaleza de los bordes (continuidad percibida, dos tipos de discontinuidad percibida). Los 1000 buenos vectores son los que representan hexágonos que se pueden ver al ver cubos en perspectiva. El motivo de la consulta es aplicar correcciones locales a un mapa hexagonal llena de triángulos ...

Answer 1

Esto se parece mucho a lo que los correctores ortográficos tienen que hacer. El truco generalmente es abusar de tries.

Lo más básico que puede hacer es construir un trie sobre los buenos vectores, luego hacer un relleno de inundación priorizando las ramas con pocos desajustes. Esto será muy rápido cuando haya un vector cercano, y degenerará a fuerza bruta cuando el vector más cercano esté muy lejos. No está mal.

Pero creo que puedes hacerlo mejor. Los vectores defectuosos que comparten el mismo prefijo harán el mismo trabajo inicial de bifurcación, por lo que podemos intentar compartir eso también. Así que también construimos un trie sobre los vectores malos y los hacemos todos a la vez.

No hay garantías de que esto es correcto, ya que tanto el algoritmo y el código son a la parte superior de mi cabeza:

var goodTrie = new Trie(goodVectors) 
var badTrie = new Trie(badVectors) 
var result = new Map<Vector, Vector>() 
var pq = new PriorityQueue(x => x.error) 
pq.add(new {good: goodTrie, bad: badTrie, error: 0}) 
while pq.Count > 0 
    var g,b,e = q.Dequeue() 
    if b.Count == 0: 
     //all leafs of this path have been removed 
     continue 
    if b.IsLeaf: 
     //we have found a mapping with minimum error for this bad item 
     result[b.Item] = g.Item 
     badTrie.remove(b) //prevent redundant results 
    else: 
     //We are zipping down the tries. Branch to all possibilities. 
     q.EnqueueAll(from i in {0,1,2} 
        from j in {0,1,2} 
        select new {good: g[i], bad: b[j], error: e + i==j ? 0 : 1}) 

return result 

Una optimización final podría ser la de volver a ordenar los vectores así posiciones con alto nivel de coincidencia entre los malos los vectores son lo primero y comparten más trabajo.

Answer 2

Mi geometría computacional es muy duro, pero parece que usted debería ser capaz de:

1. Calcular el Voronoi diagram para su conjunto de buenos vectores.
2. Calcula BSP tree para las celdas del diagrama.

El diagrama de Voronoi le dará un casco convexo de la 12ª dimensión para cada vector bueno que contenga todos los puntos más cercanos a ese vector.

El árbol BSP le dará una forma rápida de determinar en qué celda se encuentra un vector y, por lo tanto, qué buen vector es el más cercano.

EDIT: Me acabo de dar cuenta de que está utilizando distancias Hamming en lugar de distancias euclidianas. No estoy seguro de cómo esto podría adaptarse para adaptarse a esa restricción. Lo siento.

Answer 3

Solo para mantener las cosas en perspectiva y estar seguro de que no está optimizando cosas innecesarias, el enfoque de la fuerza bruta sin ninguna optimización lleva 12 segundos en mi máquina.

Código en Mathematica:

bad = Table[RandomInteger[5, 12], {1000}]; 
good = Table[RandomInteger[2, 12], {1000}]; 
distance[a_, b_] := Total[Sign@Abs[a - b]]; 

bestMatch = #[[2]] & /@ 
    Position[ 
    Table[Ordering@ 
     Table[distance[good[[j]], bad[[i]]], {j, Length@good}], {i, 
     Length@bad}], 1] // Timing 

Como se puede esperar, el tiempo sigue un O (n^2) la ley:

Answer 4

3^12 no es un espacio de búsqueda muy grande. Si la velocidad es esencial y la generalidad del algoritmo no lo es, puede asignar cada vector a un int en el rango 0..531440 y usarlo como un índice en una tabla precalculada de "vectores buenos más cercanos".

Si le diera a cada entrada de esa tabla una palabra de 32 bits (que es más que suficiente), estaría buscando aproximadamente 2 MB para la tabla, a cambio de un "cálculo" casi instantáneo.

editar: esto no es muy diferente de la precomputación que sugiere la pregunta, pero mi punto es que dependiendo de la aplicación, no hay necesariamente ningún problema al hacerlo así, especialmente si haces todos los cálculos previos antes de la aplicación incluso corre.

Answer 5

Suponiendo una representación empaquetada para los vectores, se puede completar un cálculo de distancia (comparando un vector bueno y uno incorrecto para obtener la distancia) en aproximadamente 20 ciclos de reloj o menos. Por lo tanto, se pueden hacer un millón de cálculos de dicha distancia en 20 millones de ciclos o (suponiendo una CPU de 2 GHz) 0.01 segundos. ¿Estos números ayudan?

PD: 20 ciclos es una sobreestimación conservadora.