Bearbeiten Abstand Algorithmen und Levenshtein Abstand wie LCS Methode sind vorteilhaft. Sie werden jedoch verwendet, um ein Wort in ein anderes zu ändern. Auf diese Weise können Sie herausfinden, wie Sie ein Wort mit möglichst wenigen Änderungen in ein anderes Wort ändern können. Aber sie sind nicht nützlich, um minimale Änderungen in zwei Wörterbüchern zu finden.
Das längste gemeinsame Teilfolge (LCS) Problem ist die längste Teilfolge gemeinsam für alle Sequenzen in einer Reihe von Sequenzen (oft nur zwei) zu finden. Beachten Sie, dass sich subsequence von einem Teilstring unterscheidet, siehe Teilstring vs. Teilsequenz. Es ist ein klassisches Informatikproblem, die Grundlage von Dateivergleichsprogrammen wie diff, und hat Anwendungen in der Bioinformatik.
von LCS oder anderen Methoden, für jedes Wort in list1, feststellen, dass, wie die Wort Änderungen auf einen anderen in Liste 2. zum Beispiel zwischen Fuß & Füßen: LCS = FT, Differenz = oo = > ee. Sie sollten einen zweiteiligen Graph erstellen, den der erste Teil aus Differenzwörtern erstellt, und den zweiten Teil aus list1. Jeder Knoten in dem zweiten Teil ist mit einer eigenen verwandten Differenz in dem ersten Teil verbunden.
Ich nehme an, Länge und Gesamtteil der Wörter sind begrenzt.
Wir können dieses Problem mit Graphen modellieren. Weisen Sie jede Änderung einem Knoten zu. z. B. e → i (die eine der Änderungen bestimmt) ist die Bezeichnung für einen Knoten. Zum Beispiel, wenn die gesamte Operation des Formulars p → q auf einen Teil im bipartiten Graphen gesetzt ist und die Gesamtdifferenz für jedes Wortpaar eins ist und Edge collection's definiert Edge uv verbindet Vertex U mit V wenn word (u) (im zweiten Teil), um zum korrekten Wort zu wechseln, braucht V's Änderungen. Sie haben einen maximalen 25 * 26 Knoten im ersten Teil (für dieses Beispiel). Wenn in Ihrem Fall Länge> = 1, so müssen Sie ein Limit festlegen. Ich nehme an, dass der größte Teil der Änderung für jedes Wort gleich 3 ist. Und so haben wir 3 * 35K maximalen Knoten im ersten Teil. Jetzt können Sie Problem lösen, indem Sie Satz des Knotens im ersten Teil wählen, der maximales Wort im zweiten Teil bedeckt werden kann (Ihre wählte sollte Wortänderung zum korrekten Wort vorkommen).
Suchen Sie in diesem Diagramm den minimalen Vertexschnitt, um den Knoten zu finden, den sie für Ihre Anfrage verwenden können. Wiederholen Sie den Schnittscheitelalgorithmus, bis Sie eine gute Antwort erhalten.
Sie können eine Art von Grenzen verwenden, um die Größe des Diagramms zu reduzieren, z. B. alle Knoten im ersten Teil mit dem Grad 1 zu entfernen, da diese Knoten mit genau einem Wort verbunden sind, also scheinen sie nutzlos zu sein.
Diese Graphensimulation kann Ihr Problem lösen. Mit der aktuellen Problembeschreibung funktioniert diese Algorithmusgrenze ordnungsgemäß.
zum Beispiel: 
Es ist beispielsweise für die Grenzen in diesem Graphen (entfernen alle Knoten im Betriebsteil, dass sie 1 Flanke haben):
1-entfernen Knoten 4, weil es nur angeschlossen ist (nicken), dann entfernen node (nicken) 2-entfernen node 2, weil es nur mit (sghoul) verbunden ist, dann entfernen Knoten (sghoul) 3-jetzt entfernen node 3, weil es nur verbunden ist (goud) [sghoul wird im letzten Schritt entfernt], entfernen Sie dann node (goud)
und jetzt haben Sie eine Operation oo => ee und Sie können dies wählen.
Ich werde mehr denken und versuchen, diesen Text zu bearbeiten.
Wollen Sie auch das i -> a in 4 und 5 finden? Mit anderen Worten, würdest du zählen, dass ich zu a 4 mal oben oder nur 2 vorkommt? – ex0du5
Gute Frage. Ich denke, wenn die Veränderung als Teil einer anderen Veränderung auftritt, sollte sie nicht gezählt werden. Also, ich zähle nur 2. – Reactormonk
hast du ein Limit für die Länge der Wörter? –