Gibt es einen besseren Algorithmus mit einem besseren als brutären Kraft, um ein Diagramm zu erzeugen, dessen Beziehung String-Bearbeitungsabstand= 1 ist?

Question

Ich bin daran interessiert, eine Diagramme zu erstellen, deren Scheitelpunkte Saiten sind und deren Kanten die Beziehung darstellt, einen Bearbeitungsabstand von 1 unter einer bestimmten String-Metrik zu haben.

Ein offensichtlicher Ansatz besteht darin, alle $ \ frac {n ^ 2-n} {2} $ Vergleiche zwischen den $ n $ Scheitelpunkte, geben uns $ o (n ^ 2) $ Zeitkomplexität.

ohne Parallelisierung der Vergleiche gibt es einen besseren Algorithmus in Bezug auf die Zeitkomplexität?

Ich interessiere mich für String-Metriken, in denen Saiten unterschiedlicher Länge erlaubt sind.

Answer 1

Im schlimmsten Fall funktioniert ein solcher Algorithmus $ \ Omega (N ^ 2) $ , da Ihr Diagramm hat$ \ Omega (n ^ 2) $ Kanten.

Übrigens interessieren Sie sich für eine bestimmte Zeichenfolgenmetrik?

Answer 2

Es ist möglich, BK-Bäume zu verwenden, um das zu beschleunigen. Einfügen der $ n $ Elemente in den Baum nimmt $ o (n \ log n) $ Uhrzeit. Danach können Sie den Baum für alle Saiten abfragen, deren Bearbeitungsentfernung genau von Ihrem Eingang entfernt ist. Wenn Sie dies für alle Saiten tun, nimmt erneut $ O (N ^ 2) $ Komplexität, jedoch mit einem sehr kleinen konstanten Faktor ( Diese Seite erwähnt Nur 5-8% des Baumes muss pro Abfrage inspiziert werden ).

Hier ist eine kurze Beschreibung, wie es funktioniert:

Datenstruktur

a bk-baum ist entweder

• leer
• ein Knoten mit einem Root-Wert $ R $ und ein Satz von indizierten Kindern $ c_i $ , jeweils ein BK-Baum (implementiert mithilfe von Hash-Map, dynamisches Array oder ähnliches)

Eine metrische Metrik (wichtige!) Entfernungsfunktion $ d (x, y) $ wird zum Einfügen und zum Abfragen verwendet.

Zeichenfolge $ s $

• Wenn der Baum leer ist, machen Sie es einen neuen Knoten mit $ s $ als Wurzelwert und keine Kinder
• Wenn der Baum ein Knoten mit root $ r $ und kinder $ c_i $ lasst < Span-Klasse="Math-Container"> $ k= D (R, S) $ .
  • Wenn $ k= 0 $ , überspringen, wenn $ s $ bereits am root < / li>
  • ansonsten rekursiv einfügen $ s $ in den $ k $ -th kindbaum $ c_k $ .

Der letzte Schritt stellt sicher, dass alle Knoten in $ C_I $ Abstand $ I $ auf die Wurzel

Abfragezeichenfolge $ s $

• Wenn der Baum leer ist, geben Sie keine Ergebnisse zurück
• Wenn der Baum ein Knoten mit root $ r $ und kinder $ c_i $ lasst < Span-Klasse="Math-Container"> $ k= D (R, S) $ .
  • wenn $ k= 1 $ , fügen Sie $ R $ als Ergebnis hinzu ( Hinweis : Dieser Schritt unterscheidet sich von üblichen BK-Tree-Abfragen)
  • Zusätzlich, rekursiv abfragen $ s $ von den kindern $ c_ {d-1} $ , $ c_d $ und $ c_ {d + 1} $ . Gib alle Ergebnisse von diesen Abfragen auch
  zurück

Der letzte Schritt gibt es die Magie von BK-Bäumen, da es nicht muss, da es die anderen Kinder nicht prüfen muss, da die Entfernung metrisch ist. Hier ist ein Teilnachweis, warum andere nicht geprüft werden müssen:

Nehmen wir an, es gab einige String $ x $ , die Entfernung von unserer Abfrage hat, sodass $ d (s, x)= 1 $ , aber es ist im untergeordneten Baum $ c_ {k + 2} $ . Wir wissen, dass $ d (R, X)= k + 2 $ aus dem Einfügungsverfahren. Dies gibt jedoch (mit der Dreiecks-Ungleichheit für metrische Räume) [/ p>

$$ K + 2= D (R, X) \ LEQ D (R, S) + D (S, X)= K + 1 $$

Das ist jedoch ein Widerspruch! Ähnliche können für alle Kinder mit $ i> k + 1 $ und $ i . Dies bedeutet, dass alle Saiten in anderen Kindern keine Entfernung mit dem Bau haben, also müssen wir sie nicht einmal überprüfen, was die Bearbeitungszeit spart.

Bearbeiten: Eine andere Erklärung: https://signal-noise.xyz / post / bk-baum /