legilibre / archeo-lex-web Goto Github PK

Quoique j’y ai déjà passé du temps pour faire des diffs “lisibles”, la situation est améliorable. #2 va changer la logique interne mais le rendu devrait être identique à l’actuel.

Basiquement, je me suis tourné vers l’algorithme de Ratcliff-Obershelp, qui ne semble pas très connu, mais qui est tout de même implémenté dans la librairie standard difflib de Python. Essentiellement il recherche les plus grandes zones contiguës de texte, puis, à gauche et à droite recherche à nouveau les plus grandes zones contiguës de texte, et ainsi de suite. Ce qui n’est pas dans les zones contiguës de texte sont des différences (suppression, ajout ou modification).

Cœur du problème : là où les choses deviennent plus discutables, c’est sur la quantité d’alternances "texte identique" / "textes différents" et a fortiori lorsque les "textes différents" impliquent des retours à la ligne et a fortiori lorsque l’un des "textes différents" a un retour à la ligne et pas l’autre. Cela donne parfois un aspect visuel d’une « soupe de rose, vert et gris ».

Dans la 1re version qui travaillait au niveau du caractère (version toujours actuelle mais pas pour longtemps), j’imposais que les zones de texte commun fassent au moins 5 caractères ou aient un retour à la ligne (cette 2e condition est, je pense, importante car un retour à la ligne est fortement signifiant, et a contrario s’il était mis dans les "textes différents" cela ferait 2 retours à la ligne (un rose + un vert).

J’ai dans l’idée que pour optimiser la lisibilité des diffs il faut d’abord obtenir un diff minimal ou quasi-minimal puis appliquer une fonction globale de "balance" qui rendrait l’aspect visuel convenable. Possiblement des raffinements pourraient ensuite être appliqués.

1. La version brute – le diff minimal ou quasi-minimal – peut s’obtenir facilement avec un des algorithmes existants (Myers ou Ratcliff-Obershelp, les deux sont disponibles dans la classe Diff). J’entends par "diff quasi-minimal" un diff dont le script d’édition n’est pas forcément minimal (au sens de Myers), c’est (pour ce que j’en connais) Ratcliff-Obershelp.
2. La fonction globale de "balance" est le point central de cette issue. Il s’agirait d’équilibrer les alternances "texte identique"/"textes différents" (les "textes différents" étant de 3 types : ajout, suppression, modification) en tenant compte des retours à la ligne. Il est possible qu’il faille traiter de façons différentes des retours à la ligne détectés comme "texte identique" dans le diff minimal, en fonction du contexte. Possiblement une des choses qui auraient un poids plus important serait également les points de numérotation "\na. ", "\nb. "… ou "\n1. ", "\n2. "….
3. La fonction de raffinement serait pour changer localement certains détails. Pour rendre à César, c’est ma mère qui a pensé à ce point : les accords des verbes (ou autres) qui changent notamment sur des singulier/pluriel, par exemple "Est autorisé la vente de produits de beauté." → "Sont autorisés la vente de produits de beauté et le prêt de glaces parfumées à la vanille." peut devenir "-Est-+Sont+ autorisé+s+ la vente de produits de beauté+ et le prêt de glaces parfumées à la vanille+."

Noter que le résultat de cette issue sera de faire des diffs "plus grands" en faisant globalement disparaître des parties de "texte identique" au profit des "textes différents", au point parfois que des articles montreront des diffs "article entièrement réécrit" alors qu’on pourrait trouver des expressions isolées identiques. Cela serait une feature et non un bug car a contrario (la situation actuelle) il y aurait des expressions isolées autour desquelles danseraient le reste du texte, alors même que, par exemple, ces expressions isolées seraient dans des paragraphes "globalement différents", il s’agit donc de diminuer l’importance d’expressions isolées par rapport à la masse globale du texte.

L’algorithme actuel de diff mot-à-mot utilise une bibliothèque de longest common substring qui est en O(n^2) en mémoire (n = nombre de caractères), ce qui peut faire beaucoup sur les gros articles (puisque les diffs se font article par article).

PHP donne une erreur fatale lorsque toute la mémoire allouée pour PHP (paramètre memory_limit) est atteint. D’après ce que j’ai trouvé, il n’est pas vraiment possible de transformer cela en une exception alors que ça aurait été bien dans notre cas : si on ne peut pas faire du diff caractère-par-caractère, ne faire que du mot-à-mot ou lign-à-ligne. Au mieux il est possible d’avoir une fonction de shutdown qui peut afficher une belle erreur (au lieu d’une moche erreur). I find a bit silly to trigger an unrecoverable error when maximum error is reached, you could juste trigger an exception saying some memory allocation failed.

Ce bug se propose d’isoler l’environnement d’exécution du diff afin de simuler une exception le cas échéant, je dirais en créant un binaire PHP qui effectue le calcul et renvoit un code d’erreur en cas d’erreur. Ainsi l’interface web n’est pas atteinte par la fatal error.

Mais j’ai pour projet de faire des diffs nativement mot-à-mot (alors que ceux-ci sont caractère-par-caractère avec une fonction postérieure d’allonger les zones communes intra-mot afin, au final, de n’avoir que du mot-à-mot), ce qui devrait mitiger le besoin de résoudre cette issue. Mais cette issue ne concerne que le problème système de dépassement de mémoire.

L’algorithme actuel de ce qui est appelé "diff mot-à-mot" est en fait un diff caractère-par-caractère (Ratcliff-Obershelp qui a l’avantage de donner des diffs humainement plus compréhensible que les diffs minimaux produits par Myers) dans lequel est ajouté une fonction permettant de rétrécir les zones communes aux frontières mot / non-mot, ce qui de facto crée des diffs mot-à-mot.

En partie pour des raisons de performances, il est (probablement) préférable de travailler nativement au niveau du mot. Cela fait moins de tokens et il n’y a pas besoin de post-traitements (ou du moins ça élimine le post-traitement actuel).

Une "difficulté" (ou disons un peu de temps en plus) est que je n’ai trouvé qu’une seule implémentation de l’algo de longest common substring et que celui-ci ne travaille que sur des caractères. Pour 3 raisons, celui-ci ne me convient plus : il ne traite que des caractères (et non des tokens même si sa première étape est de tokeniser), il n’est pas compatible UTF-8 mais seulement ASCII (j’ai patché cela pour le site archeo-lex.fr mais ça n’est pas durable), il est en O(n^2) en mémoire et en temps alors qu’on peu faire mieux (cf ci-après).

Ainsi il faudrait :

• modifier les fonctions de diff haut-niveau afin de traiter des tokens (en l’occurence des mots),
• implémenter l’algo de longest common substring de façon plus efficace et sur des tokens.

Annexe : amélioration de l’algo de longest common substring (LCS mais à ne pas confondre avec longest common subsequence). Deux pistes à mettre en concurrence :

• étudier la construction de generalised suffix trees, possiblement/probablement à l’aide de l’algorithme d’Ukkonen et voir l’article LCS pour calculer la LCS à partir du generalised syntax tree,
• prendre l’algorithme de Myers du script d’édition minimal de transformation d’une chaîne en une autre et garder en mémoire au cours du déroulement de l’algorithme le plus grand snake par diagonale. Sauf erreur de raisonnement de ma part (et il faudrait s’en convaincre), le longest common substring est le plus grand snake de la diagonale gagnante (celle qui termine en première et qui est donc le script d’édition minimal). Ainsi fait, cet algorithme est en O(ND) en temps et O(N) en mémoire. Quoique D puisse être égal à N dans le cas de chaînes complètement différentes, le cas classique est des chaînes assez similaires et donc D << N.