Come trovare il vettore più vicino in {0,1,2}^12, più e più volte

Question

Sto cercando uno spazio di vettori di lunghezza 12, con voci 0, 1, 2. Ad esempio, uno di tali vettori è
001122001122. Ho circa un migliaio di buoni vettori e circa un migliaio di vettori cattivi. Per ogni vettore errato ho bisogno di localizzare il vettore buono più vicino. La distanza tra due vettori è solo il numero di coordinate che non corrispondono. I buoni vettori non sono particolarmente ben disposti, e la ragione per cui sono "buoni" non sembra essere d'aiuto qui. La mia priorità principale è che l'algoritmo sia veloce.

Se eseguo una ricerca esaustiva semplice, devo calcolare circa 1000 * 1000 distanze. Sembra abbastanza spessa.

Se applico l'algoritmo di Dijkstra prima utilizzando i buoni vettori, posso calcolare il vettore più vicino e la distanza minima per ogni vettore nello spazio, in modo che ogni vettore errato richieda una ricerca semplice. Ma nello spazio ci sono 3^12 = 531.441 vettori, quindi la precomputazione è di mezzo milione di calcoli a distanza. Non molti risparmi.

Potete aiutarmi a pensare a un modo migliore?

Edit: Dato che la gente ha chiesto ardentemente ciò che li rende "buona": Ogni vettore rappresenta una descrizione di un quadro esagonale di sei triangoli equilateri, che è l'immagine 2D di una disposizione 3D di cubi (si pensi generalizzata Q-bert). I triangoli equilateri sono metà di facce di cubi (45-45-90), inclinati in prospettiva. Sei delle coordinate descrivono la natura del triangolo (pavimento percepito, parete sinistra, parete destra) e sei coordinate descrivono la natura dei bordi (continuità percepita, due tipi di discontinuità percepita). I 1000 buoni vettori sono quelli che rappresentano esagoni che possono essere visti quando si vedono i cubi in prospettiva. La ragione per la ricerca è quello di applicare le correzioni locali ad una mappa esagonale piena di triangoli ...

Answer 1

questo suona un po 'come quello che correttori ortografici devono fare. Il trucco è generalmente quello di abusare di tries.

La cosa più semplice che si può fare è costruire un trie sui buoni vettori, quindi eseguire un riempimento a pieno ritmo assegnando priorità ai rami con pochi disallineamenti. Questo sarà molto veloce quando c'è un vettore vicino, e degenererà alla forza bruta quando il vettore più vicino è molto lontano. Non male.

Ma penso che tu possa fare meglio. I vettori non validi che condividono lo stesso prefisso eseguiranno lo stesso lavoro di ramificazione iniziale, quindi possiamo provare a condividerli. Quindi costruiamo anche un trie sui cattivi vettori e lo facciamo in un colpo solo.

garanzie che sia corretto, dal momento che sia l'algoritmo e il codice sono fuori dalla parte superiore della mia testa:

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 

Un'ottimizzazione finale potrebbe essere quella di riordinare i vettori in modo da posizioni con alto accordo tra il cattivo i vettori vengono prima e condividono più lavoro.

Answer 2

mio geometria computazionale è molto ruvida, ma sembra che si dovrebbe essere in grado di:

1. calcolare il Voronoi diagram per il tuo set di buoni vettori.
2. Calcolare lo BSP tree per le celle del diagramma.

Il diagramma di Voronoi ti darà uno scafo convesso di 12 ° dimensione per ogni vettore buono che contiene tutti i punti più vicini a quel vettore.

L'albero BSP vi fornirà un modo veloce per determinare quale cella si trova all'interno di un vettore e, quindi, quale vettore è più vicino.

EDIT: Ho appena notato che si stanno utilizzando distanze di hamming invece di distanze euclidee. Non sono sicuro di come questo possa essere adattato per soddisfare questo limite. Scusate.

Answer 3

Solo per mantenere le cose in prospettiva ed essere sicuri di non ottimizzare le cose inutili, l'approccio della forza bruta senza ottimizzazione richiede 12 secondi nella mia macchina.

Codice in 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 

Come ci si potrebbe aspettare, il tempo segue un O (n^2) legge:

Answer 4

3^12 non è uno spazio di ricerca molto grande. Se la velocità è essenziale e la generalità dell'algoritmo non lo è, puoi semplicemente associare ciascun vettore a un int nell'intervallo 0..531440 e utilizzarlo come indice in una tabella precompuita di "vettori buoni più vicini".

Se si dà a ciascuna voce di quella tabella una parola a 32 bit (che è più che sufficiente), si dovrebbe considerare circa 2 MB per la tabella, in cambio di un "calcolo" praticamente istantaneo.

modifica: questo non è molto diverso dalla precomputazione suggerita dalla domanda, ma il mio punto è proprio che a seconda dell'applicazione, non c'è necessariamente alcun problema nel farlo in quel modo, specialmente se si fanno tutti i calcoli prima dell'applicazione corre anche.

Answer 5

Assumendo una rappresentazione impacchettata per i vettori, un calcolo di distanza (confronto tra un vettore buono e un vettore errato per ottenere la distanza) può essere completato in circa 20 cicli di clock o meno. Quindi un milione di calcoli della distanza può essere fatto in 20 milioni di cicli o (supponendo una CPU a 2 GHz) 0,01 sec. Questi numeri aiutano?

PS: - 20 cicli è una sopravvalutazione prudente.