Algorithme de différence de texte

Question

J'ai besoin d'un algorithme capable de comparer deux fichiers texte et de mettre en évidence leur différence et (encore mieux!) De calculer leur différence de manière significative (comme deux fichiers similaires devraient avoir un score de similarité supérieur à deux fichiers dissemblables, avec le mot "similaire" définis dans les termes normaux). Cela semble facile à mettre en œuvre, mais ce n’est pas le cas.

L'implémentation peut être en c # ou en python.

Merci.

Answer 1

Je peux vous recommander de prendre un coup d'oeil à Neil Fraser du code et des articles:

google-diff-match-patch

Actuellement disponible en Java, JavaScript, C++ et Python. Quel que soit de la langue, chaque bibliothèque dispose de la même API et les mêmes fonctionnalités. Toutes les versions ont aussi complet harnais de test.

Neil Fraser: Diff Stratégies pour la théorie et la mise en œuvre des notes

Answer 2

En Python, il existe difflib , comme d'autres l'ont suggéré.

difflib propose la classe SequenceMatcher , qui peut être utilisée pour vous donner un rapport de similarité. Exemple de fonction:

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

Answer 3

Regardez difflib . (Python)

Cela calculera les diffs dans divers formats. Vous pouvez ensuite utiliser la taille du diff de contexte pour mesurer la différence entre deux documents.

Answer 4

Ma compréhension est que la meilleure solution pour la plus courte Modifier le Script (SES) problème est Myers "moyen-serpent" avec la Hirschberg linéaire de l'espace de raffinement.

Le Myers algorithme est décrit dans:

E. Myers, `Un O(ND) Différence Algorithme et de Ses Variations,"
Algorithmica 1, 2 (1986), 251-266.

La GNU diff utilitaire utilise le Myers algorighm.

Le "score de similarité" dont vous parlez s'appelle la "distance d'édition" dans la littérature, qui est le nombre d'insertions ou suppressions nécessaires à la transformation d'une séquence à l'autre.

Note qu'un certain nombre de personnes ont cité l'algorithme de Levenshtein, mais qui est, quoique facile à mettre en œuvre, pas la solution optimale, car il est inefficace (nécessite l'utilisation d', éventuellement, un énorme n*m la matrice) et ne fournit pas le "edit script" qui est la suite de modifications qui pourraient être utilisés pour la transformation d'une séquence à l'autre, et inversement.

Pour une bonne Myers / Hirschberg de mise en œuvre de regarder:

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

La bibliothèque particulière qu'il est contenu à l'intérieur n'est plus maintenu, mais à ma connaissance, la diff.c module lui-même est toujours correcte.

Mike

Answer 5

Bazaar contient un algorithme de différence alternatif, appelé patience diff (il y a plus d'informations dans les commentaires sur cette page) qui est prétendu être meilleur que l'algorithme traditionnel de diff. Le fichier 'patiencediff.py' dans la distribution bazaar est une interface simple en ligne de commande.