Entwicklertools · Textvergleich
Wie ein Textunterschied geänderte Zeilen findet: LCS und der Myers-Algorithmus
· Wie es funktioniert
Text-Diff Algorithmen Entwickler-Workflow
Erklärt die Idee der längsten gemeinsamen Teilsequenz hinter dem zeilenbasierten Vergleich und warum der Myers-Algorithmus ihn schnell genug gemacht hat, um sofort ausgeführt zu werden, sogar innerhalb einer Browser-Registerkarte.
Zwei Dateien, eine Frage: Welche Zeilen blieben erhalten? – Frames-Vergleich, bei dem die längste Reihe von Zeilen ermittelt wird, die beiden Versionen gemeinsam sind, und nicht die übereinstimmenden Zeilennummern
Zwei Revisionen kommen nicht mit Beschriftungen an, aus denen hervorgeht, welche Zeilen überlebt haben. ToolAcre teilt jeden Text zunächst in eine geordnete Liste auf und sucht dann nach einer langen Teilsequenz, die in beiden Listen in derselben Reihenfolge erscheint. Zeilen außerhalb dieses gemeinsamen Rückgrats werden eher zu Hinzufügungen oder Entfernungen als zu vermuteten Änderungen.
Das Ergebnis enthält die ursprünglichen einsbasierten Positionen für beide Seiten. Eine unveränderte Zeile besitzt auf jeder Seite eine Zahl, auf der linken Seite nur eine Entfernung und auf der rechten Seite nur eine Addition. Diese Buchhaltung macht die angezeigte Geschichte auch dann überprüfbar, wenn wiederholte Zeilen mehr als eine plausible Ausrichtung ergeben.
Warum Diff bei Zeilen und nicht bei Zeichen funktioniert – wie die Aufteilung in Zeilenumbrüchen einen Text in eine Folge vergleichbarer Einheiten umwandelt und warum sich Prosa dadurch anders verhält als Code
Die Implementierung behandelt eine vollständige Zeile als Vergleichseinheit. Zeilenumbrüche prägen daher das Ergebnis: Eine Ein-Wort-Bearbeitung innerhalb eines in einer Zeile gespeicherten Absatzes ersetzt die gesamte Zeile, während dieselbe Prosa, Satz für Satz angeordnet, einen viel kleineren Bereich isolieren kann.
Der Zeilenvergleich ist keine Zeichenanalyse, die sich hinter einer anderen Anzeige verbirgt. `splitLines` erstellt Arrays und die LCS-Tabelle vergleicht einen Zeilenschlüssel mit einem anderen. Diese vorhersehbare Granularität eignet sich für Quell- und Konfigurationsdateien, kann jedoch nicht die genauen Buchstaben hervorheben, die in einem übereinstimmend aussehenden Ersatz geändert wurden.
Längste gemeinsame Teilsequenz im Klartext – führt die LCS-Idee anhand eines fünfzeiligen Beispiels durch und zeigt, wie alles außerhalb der Teilsequenz zu einer Einfügung oder Löschung wird
Stellen Sie sich die linken Linien A, B, C, D, E und die rechten Linien A, C, E vor. A, C und E bilden eine geordnete gemeinsame Teilfolge. B und D liegen außerhalb davon, sodass das Ergebnis zwei Entfernungen und drei unveränderte Zeilen meldet, ohne dass eine der entfernten Zeilen mit einer Ersetzung gepaart werden muss.
Die Tabelle zeichnet für jedes verbleibende Positionspaar die beste verfügbare gemeinsame Länge auf. Der Wiederaufbau schreitet durch diese Werte voran. Gleiche Tasten rücken auf beiden Seiten vor; andernfalls entscheidet der größere Nachbarwert, ob eine linke Entfernung oder eine rechte Addition ausgegeben wird.
Der Myers-Algorithmus und warum Geschwindigkeit wichtig ist – erklärt ohne Formeln, wie die Verfolgung des kürzesten Bearbeitungsskripts den Vergleich bei Dateien mit Tausenden von Zeilen schnell ermöglicht
Die Arbeitsmappe nennt Myers, aber `diff.js` implementiert explizit die einfache dynamische Programmierung mit der längsten gemeinsamen Teilsequenz. Sein Kommentar gibt O(n·m) Zeit und Speicher für die abweichende Mitte an. Die Behauptung, Myers- oder Shortest-Edit-Graph-Verhalten würde den tatsächlich ausgelieferten Code durch einen bekannten Algorithmus ersetzen.
ToolAcre begrenzt diese Kosten vor der Zuteilung. Gleiche Präfixe und Suffixe werden in linearen Durchgängen entfernt, und jede unterschiedliche Mitte darf höchstens 2,000 Zeilen enthalten. Die Matrix ist ein `Uint32Array`; Das dokumentierte schlechteste zulässige Quadrat belegt etwa sechzehn Megabyte und nicht unbegrenzte, eingerahmte Werte.
ToolAcre verwendet eine LCS-Tabelle, nicht den in der Gliederung genannten Myers-Algorithmus
Vergleichen Sie ein Änderungsprotokoll, das „Suche hinzugefügt“, „Export korrigiert“ und „Hilfe aktualisiert“ enthält, mit einer Überarbeitung, die den ersten und dritten Eintrag beibehält, aber vor dem letzten „Filter hinzugefügt“ einfügt. Die allgemeinen Einträge verankern den Pfad, „Fester Export“ wird entfernt und „Filter hinzugefügt“ wird hinzugefügt.
Der Algorithmus bezeichnet dieses Paar nicht als geänderte Zeile. Sein Zeilenvokabular ist nur gleich, hinzufügen und entfernen, sodass eine Textersetzung als eine Entfernung gefolgt von einer Hinzufügung erscheint. Die Zusammenfassung zählt diese Vorgänge separat und markiert die Texte nur dann als identisch, wenn beide Zählungen Null sind.
Warum zwei korrekte Diffs unterschiedlich aussehen können – zeigt, wie Verbindungen zwischen gleich kurzen Bearbeitungsskripten erklären, warum ein Tool eine Leerzeile und ein anderes eine schließende Klammer dafür verantwortlich macht
Wiederholte oder austauschbare Zeilen können mehrere gemeinsame Teilsequenzen derselben Länge erzeugen. ToolAcre löst einen Gleichstand auf, indem es eine Entfernung bevorzugt, wenn die beiden benachbarten Tabellenwerte gleich sind. Eine andere korrekte Implementierung wählt möglicherweise zuerst eine Ergänzung und präsentiert eine anders aussehende Ausrichtung mit den gleichen Bearbeitungskosten.
Aus diesem Grund kann es vorkommen, dass eine Leerzeile oder eine schließende geschweifte Klammer in verschiedenen Tools an ein anderes Element angehängt wird. Die Diskrepanz bedeutet nicht automatisch, dass bei einem der beiden Vergleiche Inhalte verloren gehen. Lesen Sie die ursprünglichen Zeilennummern und die umgebenden unveränderten Zeilen, bevor Sie Darstellungsunterschiede als konkurrierende Tatsachenbehauptungen behandeln.
Was dies nicht abdeckt – semantischer oder struktureller Vergleich, Bewegungserkennung und Hervorhebung auf Wortebene liegen außerhalb dessen, was ein zeilenbasierter Diff berechnet
Nichts in diesem Pfad analysiert Syntaxbäume, erkennt umbenannte Bezeichner, beschriftet verschobene Blöcke oder versteht die Prosabedeutung. Ein verschobener Absatz verstößt gegen die Anforderung der gemeinsamen Reihenfolge und kann einmal als entfernt und einmal als hinzugefügt angezeigt werden. Das Tool berechnet auch keine Hervorhebungen auf Zeichen- oder Wortebene innerhalb von Zeilen.
Diese Auslassungen sind Grenzen, keine versteckten Modi. Verwenden Sie einen sprachbewussten Prüfer für semantische Ansprüche und Versionskontrolle für den Zusammenführungsverlauf. Text diff beantwortet die engere Frage, wie sich zwei geordnete Zeilensequenzen unterscheiden, und lässt den Menschen dann interpretieren, ob diese Textänderungen wichtig sind.
Imbiss: Was die hervorgehobenen Zeilen wirklich bedeuten – fasst zusammen, wie man einen Zeilenunterschied als kürzeste Bearbeitungsgeschichte liest und wie der Textvergleich von ToolAcre dies in Ihrem Tab ausführt, ohne etwas hochzuladen
Lesen Sie die grünen und roten Zeilen als eine von LCS abgeleitete Erklärung, nicht als Beweis für die Absicht des Autors. Das Kürzen von Präfixen und Suffixen verändert den Arbeitsaufwand, jedoch nicht die endgültige Zeilenabrechnung. Der Originaltext bleibt in jeder Zeile erhalten, auch wenn die Groß-/Kleinschreibung oder Leerzeichenoptionen lockere Schlüssel für den Abgleich bereitstellen.
Der Vergleich wird über importierte Browsermodule ausgeführt und mit DOM-Textknoten gerendert; Es gibt keinen Konvertierungsendpunkt im Werkzeugweg. Probieren Sie ein fünfzeiliges Beispiel aus, tauschen Sie die Seiten aus und laden Sie die fleckenförmige Ausgabe herunter, um zu sehen, wie die Richtung Hinzufügungen in Entfernungen ändert, ohne die Semantik neu zu erfinden.