Approche heuristique pour une mise en œuvre flexible du DIFF

12

J'ai créé une implémentation DIFF pour comparer les révisions de documents au travail. Il est basé sur une différence O (ND) Algorithme et ses variations .

Une chose qui est devenue importante est de prendre la liste des changements et de les interpréter en texte lisible par l'homme. Bien que l'algorithme actuel soit très efficace, il l'est tellement qu'il est difficile de l'étendre.

Question courte

Je pensais essayer d'utiliser A * et une heuristique qui ajoute des pénalités pour les "tours". L'idée étant de lisser inutiles "ajouter, supprimer, ajouter, supprimer, ajouter, supprimer" afin qu'il soit plus facile d'analyser quelque chose qu'un humain peut lire. Fondamentalement, transformez mon problème de chemin le plus court en un problème de chemin le plus simple .

Et bien sûr, ne pas créer de sortie qui est toujours "Supprimer tout , Ajouter tout "

Cela vous semble-t-il raisonnable?

Y a-t-il une priorité pour l'utilisation d'une heuristique dans une implémentation DIFF? Qu'est-ce que l'heuristique?

Le problème:

Si une longue phrase est supprimée et une autre longue phrase supprimée, mais qu'ils partagent au moins un mot, dites "avec". Laisser le mot commun seul (en ne l'ajoutant pas et en le supprimant) créera le chemin le plus court. Cependant, cela obscurcit vraiment le contexte du changement pour un humain essayant de lire une impression des changements.

Exemple avec le DIFF actuel:

  • Ancien texte: Nettoyer: laver à l'eau et sécher avec de l'air d'atelier.
  • Nouveau texte: Nettoyer: essuyer avec de l'acétone et un chiffon non pelucheux.
  • Modifier la liste des notes:
    • Changer "Powerwash et brushing" en "Essuyer avec de l'acétone"
    • Remplacez «air de magasin» par «acétone et chiffon non pelucheux»

Remarque: "Changer" est utilisé au lieu de "supprimer 'air de magasin', ajouter 'acétone'"

Comme vous pouvez le voir, la deuxième note perd tout le contexte et sans toujours regarder les anciens et nouveaux jeux de texte, vous ne pouvez pas comprendre ce que cela signifie.

Remarque sur la ponctuation:

J'ai délimité la ponctuation comme des "mots" séparés pour que j'obtienne

  • Ajouter "("

au lieu de

  • Remplacez «Réparer» par «(Réparer»

parce que c'était odieux. Cependant, cela signifie que s'il y a même une virgule dans les deux textes (par opposition au mot "avec" dans l'exemple précédent), la même chose se produit.

Solution possible:

Je pense que je pourrais utiliser un algorithme de recherche de chemin différent à la place qui peut me donner la flexibilité d'ajouter du poids à différents "chemins" de changement qui pourraient avoir plus de sens pour une personne. Peut-être que je pourrais même faire en sorte que les déplacements vers des nœuds contenant de la ponctuation aient peu de poids (je ne sais pas comment cela affecterait d'autres choses).

Ensuite, je pourrais obtenir l'exemple précédent pour répertorier les éléments suivants:

  • Modifier la liste des notes:
    • Changer "Powerwash et brushing avec de l'air de l'atelier" en "Essuyer avec de l'acétone et un chiffon non pelucheux"

Voir! Beaucoup plus clair!

Je sais que je prendrais un coup de performance, et je devrais peut-être faire une refonte assez importante de mon programme, mais il est plus important d'avoir le résultat final que je veux.

Conclusion:

Encore une fois, existe-t-il une priorité pour l'utilisation d'une heuristique dans une implémentation DIFF, et qu'est-ce que c'est?

D'autres pensées? Un investissement en temps raisonnable? D'autres idées? D'autres algorithmes?

Merci d'avance!

ÉDITER:

J'ai essayé de clarifier / solidifier ma question et de généraliser ma question en ajoutant une heuristique à mon algorithme, plutôt qu'en utilisant A *. Fondamentalement, la même chose dans ce cas, mais je pense toujours plus précis maintenant. Ce message était perspicace.

ptpaterson
la source

Réponses:

1

Vous pourriez faire dans une version semblable à vimdiff:

Étape 1: identifier les phrases ajoutées, supprimées et modifiées.

Étape 2: pour chaque phrase modifiée, localisez le premier et le dernier mot modifié et coupez tout ce qui n'est pas entre ces deux mots.

Si vous avez besoin de garder une structure grammaticale plus cohérente, regardez les internes de http://www.languagetool.org/ ou un autre montré sur ce post .

A propos de la présentation: vous pouvez présenter les deux versions de cette phrase l'une sous l'autre. Vous souhaiterez peut-être afficher le contexte de chaque modification. Pour vous inspirer, regardez latexdiff qui peut imprimer le texte ajouté en bleu à sa place finale dans la version finale du texte, et le texte supprimé dans les notes de bas de page (même compatible avec \usepackage[para]{footmisc}).

user2987828
la source
Cela ne concerne que les problèmes d'affichage, pas la question principale de la correspondance heuristique.
Adam Zuckerman
Avez-vous lu mon deuxième paragraphe?
user2987828
J'ai fait. Pourriez-vous développer ce que vous essayez d'expliquer? Ma première (et deuxième) lecture m'a amené à penser que vous décriviez toujours comment afficher les informations, pas les traiter.
Adam Zuckerman
Je suis actuellement en mesure d'utiliser du HTML pour formater les ajouts et les suppressions, le visualiseur d'édition stackexchange est ce qui m'a inspiré. Ce n'est pas mon problème.
ptpaterson
1
J'ai besoin de mieux comprendre comment utiliser une méthode de recherche de graphique différente pour trouver les différences. L'original que j'ai créé crée effectivement un graphique avec des poids égaux de tous les bords et effectue une première recherche de profondeur pour trouver tous les mouvements d'ajout / suppression / conservation jusqu'à la fin. J'envisage d'ajouter différents poids aux bords et d'ajouter une heuristique.
ptpaterson