Ich habe zwei Arrays mit 100 Zeichen (maximal, kann weniger oder nicht die gleiche Größe haben), die ich ausrichten möchte. Ich möchte ein "-" hinzufügen, wenn ein anderer Buchstabe als der andere vorhanden ist. Ich fand den Needleman-Wunsch -Algorithmus, der auf dynamischer Programmierung basiert, und den Smith-Waterman Algorithmus, der eine allgemeine lokale Ausrichtungsmethode ist, die ebenfalls auf dynamischer Programmierung basiert, aber zu komplex erscheint Ich will das tun. Ich brauche nur einen einfachen Algorithmus in Java vielleicht über weniger als 50 Zeilen, dieser Code wird danach in Assembler übersetzt, weshalb brauche ich einen einfachen Algorithmus.
Gibt es eine Möglichkeit, diese Art der Ausrichtung mit einem Diff-Algorithmus durchzuführen? Wenn ja, kann mir jemand zeigen, wie ich das mache? Ich habe auf der Biostar-Sektion gesucht, aber es scheint so, als müsste ich die beiden erwähnten Algorithmen verwenden.
Englisch ist nicht meine Muttersprache, also habe ich vielleicht die falschen Suchbegriffe durchsucht.
Mein Programm arbeitet bereits mit dem Needleman-Algorithmus und seinen etwa 200 (ish) Zeilen Code.
Beispiel für die gewünschte Eingabe / Ausgabe:
%Vor%Danke
Verwenden Sie eine Variation der Levenshtein-Distanz, die genau das tut, was Sie wollen:
Ausgabe
%Vor%Code:
%Vor%Die Beschreibung Ihres Problems erinnert mich sofort an die Levenshtein-Distanz und den zugehörigen Algorithmus, der einfach ist (definitiv weniger als 50 Zeilen), basiert aber auch auf dynamischer Programmierung.
Der ursprüngliche Algorithmus berechnet nur die Anzahl der erforderlichen Änderungen, kann jedoch leicht geändert werden, um die erforderlichen Einfügungen, Löschungen und Ersetzungen zu finden. Eigentlich bin ich mir nicht sicher, ob Sie überhaupt mit Substitutionen umgehen wollen, wie würden Sie zB ABC und ADC ausrichten?