Text Differenz Algorithmus

Question

Ich brauche einen Algorithmus, der zwei Textdateien vergleichen und markieren ihre Differenz und (noch besser!) Kann ihre Differenz in einer sinnvollen Art und Weise (wie zwei ähnliche Dateien sollten eine Ähnlichkeitswert höher als zwei unterschiedliche Dateien berechnen, mit dem Wort „ähnlich“ definiert in den normalen Bedingungen). Es klingt einfach zu implementieren, aber es ist nicht.

Die Umsetzung kann in C # oder Python sein.

Danke.

Answer 1

In Python gibt es difflib , wie auch andere vorgeschlagen haben.

difflib bietet das SequenceMatcher -Klasse, die verwendet werden, können Sie ein geben Ähnlichkeitsverhältnis. Beispiel Funktion:

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()

Answer 2

kann ich empfehlen, einen Blick auf Neil Fraser Code und Artikel zu übernehmen:

google-diff-match-patch

  

Derzeit verfügbar in Java,   JavaScript, C ++ und Python. Ungeachtet   die Sprache, jede Bibliothek verfügt über die   gleiche API und die gleiche Funktionalität.   Alle Versionen haben auch umfassende   Testrahmen.

Neil Fraser: Diff Strategies - für Theorie und Implementierung Anmerkungen

Answer 3

Lesen Sie difflib . (Python)

Das wird die Diffs in verschiedenen Formaten berechnen. Sie könnten dann die Größe des Kontext diff als Maß dafür, wie unterschiedlich zwei Dokumente sind?

Answer 4

Bazaar enthält einen alternativen Unterschied Algorithmus, genannt

Ihr gegenwärtiges Verständnis ist, dass die beste Lösung für das Kürzeste Script bearbeiten (SES) Problem ist Myers „middle-Schlange“ Methode mit der Hirsch linearen Raum Verfeinerung.

Der Myers-Algorithmus ist beschrieben in:

  

E. Myers, `` Eine O (ND) Difference   Algorithmus und seine Variationen, ‚‘
  Algorithmica 1, 2 (1986), 251-266.

Das GNU Diff verwendet den Myers-Algorithmus.

Der „Ähnlichkeitswert“ Sie sprechen von der „Edit-Distanz“ in der Literatur genannt, die die Anzahl der Einsätze ist oder löschen notwendig, eine Sequenz in die andere zu verwandeln.

Beachten Sie, dass eine Reihe von Menschen, den Levenshtein-Distanz-Algorithmus genannt hat, aber das ist, wenn auch einfach zu implementieren, nicht die optimale Lösung, da es ineffizient ist (erfordert die Verwendung einer möglicherweise großen m Matrix n *) und bietet keine „Skript bearbeiten“, die die Reihenfolge der Änderungen ist, die verwendet werden könnten, eine Sequenz, in die andere und umgekehrt zu verwandeln.

Für einen guten Myers / Hirsch Implementierung Blick auf:

http://www.ioplex.com/~miallen /libmba/dl/src/diff.c

Die besondere Bibliothek, die es innerhalb von nicht mehr aufrechterhalten enthalten ist, aber mein Wissen des diff.c Modul selbst ist nach wie vor richtig.

Mike

Wenn Sie eine feinere Körnung als Linien benötigen, können Sie Levenshtein Entfernung verwenden. Levenshtein-Distanz ist eine Straight-Forward-Maßnahme, wie man ähnliche zwei Texte sind.
Sie können auch die Bearbeitungsprotokolle zu extrahieren verwenden, um und kann ein sehr feinkörniges diff, ähnlich wie auf den Bearbeitungsverlauf Seiten von SO. Seien Sie gewarnt, wenn, dass Levenshtein Abstand recht werden CPU- und speicherintensiv zu berechnen, so difflib verwenden, wie Douglas Leder, vorgeschlagen wird höchstwahrscheinlich schneller zu gehen.

Cf. auch diese Antwort .

Es gibt eine Reihe von Abstandsmetriken, wie Paradoja erwähnt ist die Levenshtein-Distanz, aber es gibt auch NYSIIS und Soundex . In Bezug auf die Python-Implementierungen, habe ich py-editdist und Advas vor. Beide sind schön, in dem Sinne, dass Sie eine einzelne Zahl zurück als Punktzahl. Schauen Sie sich Advas zuerst, es implementiert eine Reihe von Algorithmen.

Wie bereits erwähnt, verwendet difflib. Sobald Sie den diffed Ausgang haben, finden Sie in den Levenshtein Abstand der verschiedenen Saiten zu geben ein „Wert“, wie unterschiedlich sie sind.

Sie können die Lösung für das längste gemeinsame Subsequence (LCS) Problem verwenden. Siehe auch die Diskussion über mögliche Wege, um diese Lösung zu optimieren.

Eine Methode, die ich für eine andere Funktionalität eingesetzt haben, zu berechnen, wie viele Daten neu war in einer modifizierten Datei, könnte auch für Sie vielleicht arbeiten.

Ich habe einen diff / patch Implementierung C #, die ich zwei Dateien nehmen können, vermutlich alte und neue Version der gleichen Datei, und berechnen Sie die „Differenz“, aber nicht im üblichen Sinne des Wortes. Grundsätzlich berechne ich eine Reihe von Operationen, die ich auf der alten Version durchführen kann aktualisieren sie den gleichen Inhalt wie die neue Version zu haben.

Um dies zu für die Funktionalität zu nutzen zunächst beschrieben, um zu sehen, wie viele Daten waren neu, ich einfach läuft durch die Operationen und für jede Operation, die wörtlich aus der alten Datei kopiert, die einen 0-Faktor hatten, und jede Operation, dass eingefügt neuer Text (als Teil des Patches verteilt, da es nicht in der alten Datei auftrat) hatte einen 1-Faktor. Alle Zeichen wurden diese Fabrik gegeben, die mir im Grunde eine lange Liste von 0'en gab und 1en.

Alles, was ich musste dann war tun die 0 und 1 ist zu Tally. In Ihrem Fall mit meiner Implementierung, die eine geringe Zahl von 1 im Vergleich zu 0en bedeuten würde, die Dateien sind sehr ähnlich.

Diese Implementierung würde auch Fälle behandeln, in denen die geänderte Datei aus, um Kopien von der alten Datei eingefügt hatte, oder sogar Duplikate (dh. Sie kopieren aus dem Anfang der Datei einen Teil und in der Nähe der Unterseite einfügen), da sie beide Kopien des gleichen Originalteils aus der alten Datei sein würde.

experimentierte ich mit einem Gewicht von Kopien, so dass die erste Kopie als 0 gezählt wird, und nachfolgende Kopien der gleichen Zeichen hatten progressiv höhere Faktoren, um einen Copy / Paste-Betrieb zu geben einig „neuen-Faktor“, aber ich habe nie fertig als das Projekt verschrottet wurde.

Wenn Sie interessiert sind, mein Diff / Patch-Code ist aus meiner Subversion-Repository zur Verfügung.

Werfen Sie einen Blick auf die Fuzzy Modul. Es hat sich schnell (geschrieben in C) basierte Algorithmen für soundex, NYSIIS und Doppel Metaphone.

http:

Eine gute Einführung finden Sie unter //www.informit. com / articles / article.aspx? p = 1848528

Answer 5

Answer 6

Answer 7

Answer 8

Ihr gegenwärtiges Verständnis ist, dass die beste Lösung für das Kürzeste Script bearbeiten (SES) Problem ist Myers „middle-Schlange“ Methode mit der Hirsch linearen Raum Verfeinerung.

Der Myers-Algorithmus ist beschrieben in:

  

E. Myers, `` Eine O (ND) Difference   Algorithmus und seine Variationen, ‚‘
  Algorithmica 1, 2 (1986), 251-266.

Das GNU Diff verwendet den Myers-Algorithmus.

Der „Ähnlichkeitswert“ Sie sprechen von der „Edit-Distanz“ in der Literatur genannt, die die Anzahl der Einsätze ist oder löschen notwendig, eine Sequenz in die andere zu verwandeln.

Beachten Sie, dass eine Reihe von Menschen, den Levenshtein-Distanz-Algorithmus genannt hat, aber das ist, wenn auch einfach zu implementieren, nicht die optimale Lösung, da es ineffizient ist (erfordert die Verwendung einer möglicherweise großen m Matrix n *) und bietet keine „Skript bearbeiten“, die die Reihenfolge der Änderungen ist, die verwendet werden könnten, eine Sequenz, in die andere und umgekehrt zu verwandeln.

Für einen guten Myers / Hirsch Implementierung Blick auf:

Answer 9

Answer 10

Wenn Sie eine feinere Körnung als Linien benötigen, können Sie Levenshtein Entfernung verwenden. Levenshtein-Distanz ist eine Straight-Forward-Maßnahme, wie man ähnliche zwei Texte sind.
Sie können auch die Bearbeitungsprotokolle zu extrahieren verwenden, um und kann ein sehr feinkörniges diff, ähnlich wie auf den Bearbeitungsverlauf Seiten von SO. Seien Sie gewarnt, wenn, dass Levenshtein Abstand recht werden CPU- und speicherintensiv zu berechnen, so difflib verwenden, wie Douglas Leder, vorgeschlagen wird höchstwahrscheinlich schneller zu gehen.

Cf. auch diese Antwort .

Answer 11

Es gibt eine Reihe von Abstandsmetriken, wie Paradoja erwähnt ist die Levenshtein-Distanz, aber es gibt auch NYSIIS und Soundex . In Bezug auf die Python-Implementierungen, habe ich py-editdist und Advas vor. Beide sind schön, in dem Sinne, dass Sie eine einzelne Zahl zurück als Punktzahl. Schauen Sie sich Advas zuerst, es implementiert eine Reihe von Algorithmen.

Answer 12

Wie bereits erwähnt, verwendet difflib. Sobald Sie den diffed Ausgang haben, finden Sie in den Levenshtein Abstand der verschiedenen Saiten zu geben ein „Wert“, wie unterschiedlich sie sind.

Answer 13

Sie können die Lösung für das längste gemeinsame Subsequence (LCS) Problem verwenden. Siehe auch die Diskussion über mögliche Wege, um diese Lösung zu optimieren.

Answer 14

Eine Methode, die ich für eine andere Funktionalität eingesetzt haben, zu berechnen, wie viele Daten neu war in einer modifizierten Datei, könnte auch für Sie vielleicht arbeiten.

Ich habe einen diff / patch Implementierung C #, die ich zwei Dateien nehmen können, vermutlich alte und neue Version der gleichen Datei, und berechnen Sie die „Differenz“, aber nicht im üblichen Sinne des Wortes. Grundsätzlich berechne ich eine Reihe von Operationen, die ich auf der alten Version durchführen kann aktualisieren sie den gleichen Inhalt wie die neue Version zu haben.

Um dies zu für die Funktionalität zu nutzen zunächst beschrieben, um zu sehen, wie viele Daten waren neu, ich einfach läuft durch die Operationen und für jede Operation, die wörtlich aus der alten Datei kopiert, die einen 0-Faktor hatten, und jede Operation, dass eingefügt neuer Text (als Teil des Patches verteilt, da es nicht in der alten Datei auftrat) hatte einen 1-Faktor. Alle Zeichen wurden diese Fabrik gegeben, die mir im Grunde eine lange Liste von 0'en gab und 1en.

Alles, was ich musste dann war tun die 0 und 1 ist zu Tally. In Ihrem Fall mit meiner Implementierung, die eine geringe Zahl von 1 im Vergleich zu 0en bedeuten würde, die Dateien sind sehr ähnlich.

Diese Implementierung würde auch Fälle behandeln, in denen die geänderte Datei aus, um Kopien von der alten Datei eingefügt hatte, oder sogar Duplikate (dh. Sie kopieren aus dem Anfang der Datei einen Teil und in der Nähe der Unterseite einfügen), da sie beide Kopien des gleichen Originalteils aus der alten Datei sein würde.

experimentierte ich mit einem Gewicht von Kopien, so dass die erste Kopie als 0 gezählt wird, und nachfolgende Kopien der gleichen Zeichen hatten progressiv höhere Faktoren, um einen Copy / Paste-Betrieb zu geben einig „neuen-Faktor“, aber ich habe nie fertig als das Projekt verschrottet wurde.

Wenn Sie interessiert sind, mein Diff / Patch-Code ist aus meiner Subversion-Repository zur Verfügung.

Answer 15

Werfen Sie einen Blick auf die Fuzzy Modul. Es hat sich schnell (geschrieben in C) basierte Algorithmen für soundex, NYSIIS und Doppel Metaphone.

http:

Eine gute Einführung finden Sie unter //www.informit. com / articles / article.aspx? p = 1848528