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.
la source