Problem:
Ich habe N (~ 100k-1m) Strings mit jeweils D (z. B. 2000) Zeichen und einem niedrigen Alphabet (zB 3 mögliche Zeichen). Ich möchte diese Saiten so sortieren, dass möglichst wenige Änderungen zwischen benachbarten Saiten möglich sind (zB Hammingdistanz ist gering). Lösung muss nicht die bestmögliche sein, aber je näher desto besser.
Beispiel
%Vor%Gedanken zum Problem
Ich habe das schlechte Gefühl, dass dies ein nicht triviales Problem ist. Wenn wir uns jede Kette als Knoten und die Abstände zu anderen Ketten als Kante vorstellen, dann betrachten wir das Problem des reisenden Verkäufers. Die große Anzahl von Strings bedeutet, dass die Berechnung aller paarweisen Distanzen im Voraus unmöglich ist. Ich denke, dass das Problem in etwas mehr wie das Canadian Traveler verwandelt wird Problem .
Im Moment bestand meine Lösung darin, eine VP-Struktur zu verwenden, um eine gierige Lösung vom Typ "Nächster Nachbar" zu finden das Problem
%Vor%aber die ersten Ergebnisse scheinen schlecht zu sein. Das Hacken von Strings, so dass ähnliche Zeichen näher kommen, mag eine andere Option sein, aber ich weiß wenig darüber, wie gut eine Lösung dies bereitstellen wird oder wie gut sie auf Daten dieser Größe skaliert wird.
Selbst wenn Sie dieses Problem als das Problem des reisenden Verkäufers (TSP) betrachten, glaube ich, dass die Hamming-Abstände der Dreiecksungleichung folgen (Hamming (A, B) + Hamming (B, C) ≤ Hamming (A, C) )), Sie beschäftigen sich also nur mit ΔTSP (dem metrischen Travelling-Salesman-Problem), für das es eine Reihe von Algorithmen gibt, die gute Näherungen bei einem idealen Ergebnis liefern. Insbesondere der Christofides-Algorithmus gibt Ihnen immer einen Pfad von maximal 1,5x der minimal möglichen Länge.
Ja, das ist ein Problem des Reiseverkäufers , aber ich weiß nicht, ob eines der Dutzend Programme unter TSP-Quellcode-Bibliothek kann mit einer Plug-in-Metrik 1 M Punkte direkt nach oben tun.
Ein möglicher zweistufiger Ansatz:
1) Teilen Sie die 1M-Punkte in 50 Cluster auf mit einem Nächste Nachbarsuche . Tun Sie TSP auf den 50 Cluster-Zentren.
2) setze alle 1M - 50 Punkte zwischen die 2 nächsten Zentren; Tue TSP auf jeder Kette von 1M / 50. Hier könnte "50" 100 oder 1000 sein. Wenn 1000 zu groß ist, rekursiv: teile 1000 in 30 Gruppen von je ~ 30 auf.
K-Mittel können 1M Punkte sammeln, aber ich kenne keine schnelle Implementierung mit Plug-In-Metrik. Siehe jedoch scikit-learn clustering
Um einen Schwerpunkt von N Punkten zu finden, eine, die | Mitte - alle anderen | minimiert, du kannst afaik schlagen O (N ^ 2) nur durch das Beste aus einer Stichprobe von sagen sqrt (N) nehmen - sollte gut genug sein. (Oder google / stelle eine separate Frage zum schnellen ungefähren Zentroid).
Packen Sie zuerst die Daten fest, um Speicherzugriffe im gesamten Fluss zu speichern. In diesem Fall codiere a b c als 00 01 10 (Hamming-Abstand zwischen jedem Paar = 1): 2000 x 2 Bits = 500 Bytes. Fwiw, finde min Hammingdist (4k Bits, 10k x 4k) dauert ~ 40 ms auf meinem Mac ppc.
Tags und Links algorithm sorting hamming-distance