Algorithme de comparaison de texte
nous avons une exigence dans le projet que nous devons comparer deux textes ( update1, update2) et trouver un algorithme pour définir combien de mots et combien de phrases ont changé.
y a-t-il des algorithmes que je puisse utiliser? Je ne cherche même pas de code. Si je connais l'algorithme, je code en java. Remercier.
6 réponses
typiquement, ceci est accompli en trouvant le plus longue suite commune (communément appelé le problème LCS). C'est ainsi que des outils comme diff fonctionnent. Bien sûr, diff est un outil orienté ligne, et il semble que vos besoins sont quelque peu différents. Cependant, je suppose que vous avez déjà construit un moyen de comparer des mots et des phrases.
un algorithme de comparaison de séquences O(NP) est utilisé par le moteur diff de subversion.
pour votre information, il y a des implémentations avec différents langages de programmation par moi-même dans la page suivante de github.
une sorte de variante diff pourrait être utile, par exemple wdiff
si vous décidez de concevoir votre propre algorithme, vous allez devoir aborder la situation où une phrase a été insérée. Par exemple pour les deux documents suivants:
The men are bad. I hate the men
et
The men are bad. John likes the men. I hate the men
votre outil devrait être capable de regarder à l'avance pour reconnaître que dans le le second, I hate the men n'a pas été remplacé par John likes the men , mais au contraire est intacte, et une nouvelle phrase insérée avant. c'est-à-dire qu'il doit signaler l'insertion d'une phrase, et non le changement de quatre mots suivi d'une nouvelle phrase.
l'algorithme spécifique utilisé par diff et la plupart des autres utilitaires de comparaison est D'Eugene Myer, un algorithme de différence O(ND) et ses Variations . Il y a une implémentation Java disponible dans le paquet java-diff-utils .
voici deux articles qui décrivent d'autres algorithmes de comparaison de textes qui devraient généralement produire des différences "meilleures" (p. ex. plus petites, plus significatives):
- Tichy, Walter F., "La Chaîne de Corde de Correction de Problème avec le Bloc se Déplace" (1983). Rapports Techniques En Informatique. Journal 378.
- Paul Heckel, "Une Technique pour Isoler les Différences Entre les Fichiers", Communications of the ACM, Avril 1978, Volume 21, Numéro 4
le premier article cite le second et mentionne ceci à propos de son algorithme:
Heckel [3] a souligné des problèmes similaires avec les techniques LCS et a proposé un algorithme de lime linéaire pour détecter les mouvements de blocs. L'algorithme effectue adéquatement s'il y a peu de symboles dupliqués dans les chaînes. Cependant, l'algorithme donne mauvais résultats sinon. Par exemple, étant donné les deux chaînes AABB et bbaa , L'algorithme d'Heckel ne parvient pas à trouver un substrat commun.
le premier papier a été mentionné dans cette réponse et le second dans cette réponse , à la fois à la question similaire SO:
la difficulté vient en comparant de grands fichiers efficacement et avec de bonnes performances. J'ai donc mis en place une variante de L'algorithme Myers o(ND) diff - qui fonctionne assez bien et précis (et supporte le filtrage basé sur l'expression régulière):
algorithme peut être testé ici: becke.ch comparer application web
et un peu plus d'informations sur la page d'accueil: becke.comparer outil