#1873 : DiffMatchPatch.java

La bibliothèque d'algorithmes diff-match-patch de Google par Neil Fraser, intégrée directement dans ProjectForge sous le package d'origine name.fraser.neil.plaintext. Sous licence Apache 2.0. Fournit la comparaison de texte synchrone (diff), la correspondance floue (match) et l'application de correctifs (patch) — les mêmes algorithmes qui alimentent Google Docs, Etherpad et la comparaison de révisions de Wikipédia. Utilisé par ProjectForge pour le suivi des modifications de texte et la comparaison de versions.

Origine et licence

• Auteur : Neil Fraser (fraser@google.com), Google Inc.
• Copyright : 2006 Google Inc.
• Licence : Apache License 2.0
• Projet original : google-diff-match-patch sur GitHub
• Page d'accueil : http://code.google.com/p/google-diff-match-patch/ (Google Code original, maintenant archivé)
• Package préservé : name.fraser.neil.plaintext — le nom exact du package de la bibliothèque d'origine

Aperçu de l'algorithme

La bibliothèque implémente trois algorithmes connexes, tous opérant sur du texte brut :

1. Diff — Algorithme de différence O(ND) de Myers

Calcule l'ensemble minimal de modifications pour transformer le texte1 en texte2. L'algorithme central est l'algorithme de diff de Myers (1986), qui trouve le script d'édition le plus court en utilisant une approche O(ND) en temps/espace où N est la somme des longueurs des chaînes et D est le nombre de différences.

• Énumération des opérations : DELETE, INSERT, EQUAL — chaque diff est une liste chaînée d'opérations
• Optimisations : suppression des préfixes/suffixes communs, pré-comparaison au niveau des lignes (drapeau checklines), terminaison anticipée basée sur une échéance
• Post-traitement : diff_cleanupSemantic() rend les diffs lisibles par l'humain ; diff_cleanupEfficiency() optimise pour le traitement machine ; diff_cleanupMerge() fusionne les opérations adjacentes égales/de suppression
• Nettoyage sémantique : reconnaît les limites de phrases/paragraphes, les courtes égalités isolées et les changements d'espacement pour une sortie plus intuitive

2. Match — Algorithme Bitap (Shift-Or)

Localise la meilleure correspondance approximative pour un motif dans un texte plus grand. Utilise l'algorithme Bitap (également connu sous le nom de shift-or ou algorithme de Baeza-Yates–Gonnet) qui :

• Encode le motif comme un masque de bits des positions des caractères
• Utilise des opérations bit à bit pour une correspondance de chaîne approximative en O(n)
• Prend en charge la correspondance floue avec un seuil d'erreur configurable (Match_Threshold)
• Utilise un système de score sensible à la localité (Match_Distance) pour préférer les correspondances proches de l'emplacement attendu

3. Patch — Format de diff unifié + application floue

Crée des correctifs (représentations textuelles des diffs) qui peuvent être sérialisés, transmis et appliqués à d'autres textes :

• Utilise un format de diff unifié : @@ -début,longueur +début,longueur @@ contexte
• Les correctifs peuvent être appliqués avec une tolérance pour la dérive des numéros de ligne (contexte Patch_Margin pour la correspondance)
• patch_apply() tente une correspondance floue lorsque le contexte exact ne correspond pas — utilise l'algorithme Match en interne
• Prend en charge l'application partielle des correctifs avec des résultats indiquant quels correctifs ont réussi

Paramètres de configuration clés

Champ	Valeur par défaut	Objectif
Diff_Timeout	1,0 seconde	Secondes maximales pour un calcul de diff avant de retourner un résultat partiel (0 = infini)
Diff_EditCost	4	Coût d'une opération d'édition vide — des valeurs plus élevées produisent des diffs plus propres et moins fragmentés
Match_Threshold	0,5	Seuil de correspondance floue (0,0 = exact, 1,0 = très lâche)
Match_Distance	1000	Bonus de localité — distance en caractères de l'emplacement de correspondance attendu
Patch_DeleteThreshold	0,5	À quel point les blocs de suppression doivent correspondre au contenu attendu pour être acceptés
Patch_Margin	4	Nombre de caractères de contexte autour des morceaux de correctif
Match_MaxBits	32	Largeur de bits pour l'algorithme Bitap (correspond à la taille d'un int Java)

Structure de données : Diff (classe interne)

Les diffs sont représentés comme une LinkedList<Diff> où chaque Diff est une classe statique interne avec :

• Operation operation — DELETE, INSERT ou EQUAL
• String text — le segment de texte pour cette opération

Assistant interne : LinesToCharsResult

Une optimisation pour les grands textes : convertit les lignes en caractères Unicode uniques, effectue le diff sur la représentation compressée, puis reconstruit la sortie au niveau des lignes. Cela réduit considérablement l'espace de comparaison pour le texte orienté ligne (par exemple, le code source).

Imports

• java.io.UnsupportedEncodingException
• java.net.URLDecoder / URLEncoder — Pour encoder la sortie diff pour une transmission sécurisée via URL
• java.util.* — Listes, Maps, ArrayLists, LinkedLists, motifs regex

Utilisation dans ProjectForge

ProjectForge intègre cette bibliothèque plutôt que de dépendre d'un JAR externe. Cela a probablement été fait parce que :

1. La bibliothèque est stable et change rarement (la dernière mise à jour significative était le port Java vers 2010)
2. L'intégration évite les problèmes de gestion des dépendances
3. Le nom du package (name.fraser.neil.plaintext) est distinct et sans conflit
4. Elle peut avoir des modifications personnalisées pour les besoins spécifiques de ProjectForge (bien que le code semble être le port standard)

DiffMatchPatch est utilisé pour suivre les modifications apportées aux champs de texte dans les objets de données de ProjectForge — montrant ce qui a changé entre les versions d'une adresse, d'une description de projet ou d'un autre contenu textuel.

48a93dedb Journal console coloré. Export UserGroupCache pour le débogage et la comparaison de travail maintenant. CollectionUtil amélioré. KotlinStringExtension.shortenMiddle() ajouté.