Faire des diffs mot-à-mot nativement

[Seb35]

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.

[Seb35]

J’ai forké le repo original https://github.com/Seb35/PHP-Longest-Common-Substring et y ai appliqué le patch UTF-8 (+pull request) et l’adaptation à des tokens est faite dans la branche dev-tokenisation.

Pour l’amélioration de la consommation mémoire – en plus de la tokenisation qui va réduire d’environ 6^2 la taille de la matrice, le 6 est la longueur moyenne d’un mot français (trouvée sur des fora, sérieux bien sûr) – il faudrait implémenter la remarque très juste faite sur Wikipédia « Keep only the last and current row of the DP table to save memory ( O ( min ( r , n ) ) instead of O ( n r ) ) ». Ceci résoudrait en très grande partie les problèmes de place mémoire trop importante.