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éfini 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

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

difflib propose la classe SequenceMatcher , qui peut être utilisé 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 2

Je peux recommander de consulter le code et les articles de Neil Fraser:

google-diff-match-patch

  

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

Neil Fraser: stratégies de développement - pour des notes de théorie et de mise en œuvre

Answer 3

Consultez 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

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

Answer 5

Ma compréhension actuelle est que la meilleure solution au problème du script de montage le plus court (SES) est Myers " middle-snake " avec l’affinement linéaire de Hirschberg.

L’algorithme de Myers est décrit dans:

  

E. Myers, `` An O (ND) Difference   Algorithme et ses variations, ''
  Algorithmica 1, 2 (1986), 251-266.

L'utilitaire GNU diff utilise l'algorithme Myers.

Le "score de similarité" vous parlez de ce que vous appelez la " modifier la distance " dans la littérature, le nombre d'insertions ou de suppressions nécessaires pour transformer une séquence en une autre.

Notez que plusieurs personnes ont cité l’algorithme de distance de Levenshtein mais qu’il est facile à implémenter, il n’est pas la solution optimale, car il est inefficace (nécessite l’utilisation d’une matrice n * m potentiellement énorme) et ne fournit pas les informations nécessaires. "modifier le script" qui est la séquence de modifications pouvant être utilisée pour transformer une séquence en une autre, et inversement.

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

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

La bibliothèque particulière dans laquelle elle se trouve n'est plus conservée, mais à ma connaissance, le module diff.c est toujours correct.

Mike

Answer 6

Si vous avez besoin d’une granularité plus fine que les lignes, vous pouvez utiliser la distance de Levenshtein. La distance de Levenshtein est une mesure simple sur la façon dont deux textes similaires sont.
Vous pouvez également l'utiliser pour extraire les journaux de montage. Vous pouvez utiliser un diff très fin, similaire à celui des pages d'historique d'édition de SO. Soyez averti cependant que la distance de Levenshtein peut être assez longue à calculer, ce qui nécessite beaucoup de temps en ressources processeur. Par conséquent, utiliser difflib, comme l'a suggéré Douglas Leder, sera probablement plus rapide.

Cf. cette réponse .

Answer 7

Il existe un certain nombre de mesures de distance, comme paradoja l'a mentionné, la distance de Levenshtein, mais il existe également des NYSIIS et Soundex . Pour ce qui est des implémentations Python, j’ai utilisé py-editdist et ADVAS avant. Les deux sont sympas dans le sens où vous obtenez un nombre unique comme score. Découvrez d'abord ADVAS, il implémente de nombreux algorithmes.

Answer 8

Comme indiqué, utilisez difflib. Une fois que vous avez la sortie différée, vous pouvez trouver la distance de Levenshtein des différentes chaînes pour donner une " valeur " de leur différence.

Answer 9

Vous pouvez utiliser la solution au problème de la sous-requête la plus longue . Voir également la discussion sur les moyens possibles d'optimiser cette solution.

Answer 10

Une méthode que j'ai employée pour calculer une nouvelle quantité de données dans un fichier modifié pourrait également fonctionner pour vous.

J'ai une implémentation diff / patch C # qui me permet de prendre deux fichiers, probablement l'ancienne et la nouvelle version du même fichier, et de calculer la "différence", mais pas au sens habituel du mot. En gros, je calcule un ensemble d'opérations que je peux effectuer sur l'ancienne version pour la mettre à jour afin qu'elle ait le même contenu que la nouvelle version.

Pour utiliser ceci avec la fonctionnalité initialement décrite, pour voir combien de données étaient nouvelles, j’ai simplement exécuté les opérations, et pour chaque opération copiée à partir de l’ancien fichier, qui avait un facteur 0, et chaque opération le nouveau texte inséré (distribué dans le cadre du correctif, puisqu'il ne figurait pas dans l'ancien fichier) avait un facteur 1. Cette usine a été attribuée à tous les personnages, ce qui m'a donné une longue liste de 0 et de 1.

Tout ce que je devais alors faire était de totaliser les 0 et les 1. Dans votre cas, avec mon implémentation, un faible nombre de 1 par rapport à 0 signifierait que les fichiers sont très similaires.

Cette implémentation gèrerait également les cas où le fichier modifié aurait inséré des copies de l’ancien fichier hors d’ordre, voire en double (c’est-à-dire que vous copiez une partie du début du fichier et que vous la collez vers le bas), car elles seraient tous deux des copies de la même partie originale de l'ancien fichier.

J'ai essayé de peser des copies, de sorte que la première copie comptait pour 0 et les copies suivantes des mêmes caractères avaient des facteurs progressivement plus élevés, afin de donner à l'opération de copier / coller du "nouveau facteur", mais je ne terminé lorsque le projet a été abandonné.

Si cela vous intéresse, mon code diff / patch est disponible dans mon référentiel Subversion.

Answer 11

Consultez le module Fuzzy . Il possède des algorithmes rapides (écrits en C) pour soundex, NYSIIS et double métaphone.

Vous trouverez une bonne introduction à l'adresse: http: //www.informit. com / articles / article.aspx? p = 1848528