ordinamento delle stringhe in modo che la distanza di Hamming è bassa tra le stringhe adiacenti

Question

Problema:

ho N (~ 100k-1m) Corde ciascun D (ad esempio, 2000) caratteri e con un basso alfabeto (ad esempio 3 caratteri possibili). Vorrei ordinare queste stringhe in modo tale che ci siano meno modifiche possibili tra stringhe adiacenti (ad es. La distanza di hamming è bassa). La soluzione non deve essere la migliore possibile ma più vicina e migliore.

Esempio

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) 

Pensieri sul problema

Ho una brutta sensazione che questo è un problema non banale. Se consideriamo ogni stringa come un nodo e le distanze rispetto ad altre stringhe come un margine, allora stiamo esaminando un problema di commesso viaggiatore. Il gran numero di stringhe significa che il calcolo di tutte le distanze a due a due è potenzialmente irrealizzabile, penso che trasformare il problema in qualcosa di più come lo Canadian Traveller Problem.

Al momento la mia soluzione è stata quella di utilizzare un VP tree per trovare una soluzione di tipo vicino di golosi più vicino 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 

ma i primi risultati sembrano essere poveri. Le stringhe di hashing in modo che quelle più simili siano più vicine potrebbero essere un'altra opzione, ma io so poco su quanto sia valida una soluzione che fornirà o quanto bene si ridurrà ai dati di queste dimensioni.

Answer 1

Anche se si considera questo problema simile al problema del commesso viaggiatore (TSP), credo che le distanze di Hamming seguiranno la disuguaglianza triangolare (Hamming (A, B) + Hamming (B, C) ≤ Hamming (A, C)), quindi hai solo a che fare con ΔTSP (il problema del venditore ambulante metrico), per il quale ci sono un certo numero di algoritmi che danno buone approssimazioni ad un risultato ideale. In particolare, lo Christofides algorithm ti darà sempre un percorso di massimo 1,5 volte la lunghezza minima possibile.

Answer 2

Sì, questo è un Traveling salesman problem, ma non so se una qualsiasi delle decine di programmi sotto TSP source code library può fare 1M punti verso l'alto, con un plug-in metrica.

Un possibile approccio 2 stadi:

1) dividere i punti 1M in 50 gruppi con un Nearest neighbor search. Fare TSP sui 50 centri dei cluster.

2) inserire tutti i punti 1M - 50 tra i 2 centri più vicini; fare TSP su ogni stringa di 1M/50. Qui "50" potrebbe essere 100 o 1000. Se 1000 è troppo grande, ricorrere: dividere 1000 in 30 gruppi di ~ 30 ciascuno.

K-means può cluster punti 1M, ma ancora una volta non conosco un'implementazione veloce con metrica plug-in. Vedere però scikit-learn clustering

Per trovare un baricentro di N punti, uno che minimizza | Centre - tutti gli altri |, si può battere afaik O (N^2) solo prendendo il meglio di un campione casuale di say sqrt (N) - dovrebbe essere abbastanza buono. (O google/poni una domanda a parte sul centroide approssimativo veloce).

Prima pacchettizzare i dati saldamente per salvare gli accessi alla memoria nell'intero flusso. In questo caso, codificare a b c come 00 01 10 (distanza di Hamming tra ciascuna coppia = 1): 2000 x 2 bit = 500 byte. Fwiw, trovare min Hammingdist (4k bit, 10k x 4k) richiede ~ 40 msec sul mio mac ppc.