Heuristischer Ansatz zur flexiblen DIFF-Implementierung

12

Ich habe eine DIFF-Implementierung erstellt, um Dokumentrevisionen bei der Arbeit zu vergleichen. Es basiert auf einem O (ND) -Differenzalgorithmus und seinen Variationen .

Eine Sache, die wichtig geworden ist, ist es, die Liste der Änderungen zu übernehmen und sie in für Menschen lesbaren Text zu interpretieren. Während der aktuelle Algorithmus sehr effizient ist, ist er so effizient, dass es schwierig ist, ihn zu erweitern.

Kurze Frage

Ich habe darüber nachgedacht, A * und eine Heuristik zu verwenden, die Strafen für "Abbiegungen" hinzufügt. Die Idee war , unnötiges "Hinzufügen, Löschen, Hinzufügen, Löschen, Hinzufügen, Löschen" auszugleichen, damit es einfacher ist, etwas zu analysieren, das ein Mensch lesen kann. Verwandle mein Problem mit dem kürzesten Pfad in ein Problem mit dem einfachsten Pfad .

Und natürlich nicht ausgegeben erstellen , die immer „Delete alles , hinzufügen alles

Hört sich das vernünftig an?

Gibt es eine Priorität für die Verwendung einer Heuristik in einer DIFF-Implementierung? Was ist die Heuristik?

Das Problem:

Wenn ein langer Satz gelöscht und ein weiterer langer Satz entfernt wird, sie aber mindestens ein Wort teilen, sagen Sie "mit". Wenn Sie das gemeinsame Wort alleine lassen (indem Sie es nicht gleichzeitig hinzufügen und löschen), wird der kürzeste Weg gefunden. Dies verschleiert jedoch wirklich nur den Kontext der Änderung für einen Menschen, der versucht, einen Ausdruck der Änderungen zu lesen.

Beispiel mit aktuellem DIFF:

  • Alter Text: Reinigen: Powerwash und Trockenblasen mit Ladenluft.
  • Neuer Text: Reinigen: Mit Aceton und einem fusselfreien Tuch abwischen.
  • Notizliste ändern:
    • Ändern Sie "Powerwash und Föhnen" auf "Mit Aceton abwischen"
    • Ändern Sie "Ladenluft" in "Aceton und ein fusselfreies Tuch"

Hinweis: "Ändern" wird anstelle von "Shop Air löschen, Aceton hinzufügen" verwendet.

Wie Sie sehen können, verliert die zweite Note ALLEN Kontext. Wenn Sie sich nicht die vollständigen alten und neuen Textsätze ansehen, können Sie nicht verstehen, was dies bedeutet.

Anmerkung zur Zeichensetzung:

Ich habe die Interpunktion als separate "Wörter" eingegrenzt, damit ich sie bekomme

  • Hinzufügen "("

Anstatt von

  • Ändern Sie "Reparieren" in "(Reparieren").

denn das war widerlich. Dies bedeutet jedoch, dass dasselbe passiert, wenn in beiden Texten sogar ein Komma steht (im Gegensatz zum Wort "mit" im vorherigen Beispiel).

Mögliche Lösung:

Ich denke, ich könnte stattdessen einen anderen Algorithmus für die Pfadfindung verwenden, der mir die Flexibilität gibt, verschiedenen "Änderungspfaden" Gewicht zu verleihen, die für eine Person möglicherweise sinnvoller sind. Vielleicht könnte ich sogar dafür sorgen, dass Reisen zu Knoten, die Interpunktion enthalten, ein geringes Gewicht haben (nicht sicher, wie sich dies auf andere Dinge auswirken würde).

Dann könnte ich das vorige Beispiel dazu bringen, Folgendes aufzulisten:

  • Notizliste ändern:
    • Ändern Sie "Powerwash und Föhnen mit Ladenluft" in "Mit Aceton und einem fusselfreien Tuch abwischen"

Sehen! Viel klarer!

Ich weiß, dass ich einen Leistungseinbruch hinnehmen würde, und ich muss möglicherweise mein Programm gründlich überarbeiten, aber es ist wichtiger, das gewünschte Endergebnis zu erzielen.

Endeffekt:

Gibt es wieder einen Vorrang für die Verwendung einer Heuristik in einer DIFF-Implementierung, und was ist das?

Andere Gedanken? Eine angemessene Zeitinvestition? Andere Ideen? Andere Algorithmen?

Danke im Voraus!

BEARBEITEN:

Ich habe versucht, meine Frage zu klären / zu festigen und meine Frage zu verallgemeinern, um meinem Algorithmus eine Heuristik hinzuzufügen, anstatt A * zu verwenden. Grundsätzlich dasselbe in diesem Fall, aber ich denke jetzt noch genauer. Dieser Beitrag war aufschlussreich.

ptpaterson
quelle

Antworten:

1

Sie könnten in einer vimdiff-ähnlichen Version tun:

Schritt 1: Identifizieren von hinzugefügten, gelöschten und geänderten Sätzen.

Schritt 2: Suchen Sie für jeden geänderten Satz das erste und das letzte geänderte Wort und schneiden Sie alles ab, was nicht zwischen diesen beiden Wörtern liegt.

Wenn Sie eine kohärentere Grammatikstruktur benötigen, schauen Sie sich die Interna von http://www.languagetool.org/ oder einer anderen in diesem Beitrag gezeigten an .

Über die Präsentation: Sie können beide Versionen dieses Satzes untereinander präsentieren. Möglicherweise möchten Sie den Kontext für jede Änderung anzeigen. Schauen Sie sich zur Inspiration latexdiff an, das den hinzugefügten Text in blau an der letzten Stelle in der endgültigen Textversion und den gelöschten Text in Fußnoten (sogar kompatibel mit \usepackage[para]{footmisc}) drucken kann .

user2987828
quelle
Hiermit werden nur Anzeigeprobleme behandelt, nicht die Hauptfrage des heuristischen Abgleichs.
Adam Zuckerman
Hast du meinen zweiten Absatz gelesen?
User2987828
Ich tat. Könnten Sie näher auf das eingehen, was Sie zu erklären versuchen? Meine erste (und zweite) Lektüre hat mich zu dem Schluss gebracht, dass Sie immer noch beschrieben haben, wie die Informationen angezeigt und nicht verarbeitet werden sollen.
Adam Zuckerman
Ich bin derzeit in der Lage, HTML zum Formatieren der hinzugefügten und entfernten Elemente zu verwenden. Der Viewer zum Bearbeiten von StackExchange hat mich inspiriert. Das ist nicht mein Problem.
Ptpaterson
1
Ich muss besser verstehen, wie ich eine andere Diagrammsuchmethode verwenden kann, um die Unterschiede zu finden. Das Original, das ich erstellt habe, erstellt effektiv ein Diagramm mit der gleichen Gewichtung aller Kanten und führt zuerst eine Tiefensuche durch, um alle Bewegungen zum Hinzufügen / Entfernen / Beibehalten bis zum Ende zu finden. Ich denke darüber nach, die Kanten mit unterschiedlichen Gewichten zu versehen und eine Heuristik hinzuzufügen.
Ptpaterson