#1873: DiffMatchPatch.java

Googles diff-match-patch Algorithmus-Bibliothek von Neil Fraser, direkt in ProjectForge unter dem ursprünglichen Paket name.fraser.neil.plaintext eingebettet. Lizenziert unter Apache License 2.0. Bietet synchronen Textvergleich (Diff), unscharfe Suche (Match) und Patch-Anwendung (Patch) — dieselben Algorithmen, die Google Docs, Etherpad und Wikipedias Versionsvergleich antreiben. Wird von ProjectForge für Textänderungsverfolgung und Versionsvergleiche verwendet.

Ursprung und Lizenz

• Autor: Neil Fraser (fraser@google.com), Google Inc.
• Urheberrecht: 2006 Google Inc.
• Lizenz: Apache License 2.0
• Originalprojekt: google-diff-match-patch auf GitHub
• Homepage: http://code.google.com/p/google-diff-match-patch/ (ursprüngliches Google Code, jetzt archiviert)
• Paket beibehalten: name.fraser.neil.plaintext — der exakte Paketname aus der Originalbibliothek

Algorithmen-Überblick

Die Bibliothek implementiert drei verwandte Algorithmen, die alle auf Klartext operieren:

1. Diff — Myers' O(ND)-Differenzalgorithmus

Berechnet die minimale Menge an Änderungen, um Text1 in Text2 zu überführen. Der Kernalgorithmus ist Myers' Diff-Algorithmus (1986), der das kürzeste Bearbeitungsskript mit einem O(ND)-Zeit-/Platzansatz findet, wobei N die Summe der Zeichenkettenlängen und D die Anzahl der Unterschiede ist.

• Operation-Enum: DELETE, INSERT, EQUAL — jedes Diff ist eine verkettete Liste von Operationen
• Optimierungen: Entfernung gemeinsamer Präfixe/Suffixe, Vorvergleich auf Zeilenebene (checklines-Flag), deadline-basierte vorzeitige Beendigung
• Nachbearbeitung: diff_cleanupSemantic() macht Diffs menschenlesbar; diff_cleanupEfficiency() optimiert für die maschinelle Verarbeitung; diff_cleanupMerge() führt benachbarte Gleich-/Löschoperationen zusammen
• Semantische Bereinigung: Erkennt Satz-/Absatzgrenzen, kurze isolierte Gleichheiten und Leerzeichenänderungen für eine intuitivere Ausgabe

2. Match — Bitap-Algorithmus (Shift-Or)

Lokalisiert die beste ungefähre Übereinstimmung für ein Muster innerhalb eines größeren Textes. Verwendet den Bitap-Algorithmus (auch bekannt als Shift-Or oder Baeza-Yates–Gonnet-Algorithmus), der:

• Das Muster als Bitmaske von Zeichenpositionen kodiert
• Bitweise Operationen für O(n) approximatives Zeichenketten-Matching verwendet
• Unscharfe Suche mit konfigurierbarer Fehlerschwelle unterstützt (Match_Threshold)
• Ein lokalitätssensitives Bewertungssystem verwendet (Match_Distance), um Übereinstimmungen in der Nähe der erwarteten Position zu bevorzugen

3. Patch — Unified-Diff-Format + unscharfe Anwendung

Erstellt Patches (Textdarstellungen von Diffs), die serialisiert, übertragen und auf andere Texte angewendet werden können:

• Verwendet ein Unified-Diff-ähnliches Format: @@ -start,length +start,length @@ context
• Patches können mit Toleranz für Zeilennummernverschiebungen angewendet werden (Patch_Margin-Kontext für das Matching)
• patch_apply() versucht unscharfes Matching, wenn der exakte Kontext nicht übereinstimmt — verwendet intern den Match-Algorithmus
• Unterstützt teilweise Patch-Anwendung mit Ergebnissen, die anzeigen, welche Patches erfolgreich waren

Wichtige Konfigurationsparameter

Feld	Standard	Zweck
Diff_Timeout	1,0 Sekunden	Maximale Sekunden für eine Diff-Berechnung, bevor ein Teilergebnis zurückgegeben wird (0 = unendlich)
Diff_EditCost	4	Kosten einer leeren Bearbeitungsoperation — höhere Werte erzeugen sauberere, weniger fragmentierte Diffs
Match_Threshold	0,5	Schwelle für unscharfe Übereinstimmungen (0,0 = exakt, 1,0 = sehr locker)
Match_Distance	1000	Lokalitätsbonus — Entfernung in Zeichen von der erwarteten Übereinstimmungsposition
Patch_DeleteThreshold	0,5	Wie genau Löschblöcke mit dem erwarteten Inhalt übereinstimmen müssen, um akzeptiert zu werden
Patch_Margin	4	Kontextzeichenanzahl um Patch-Hunks herum
Match_MaxBits	32	Bitbreite für den Bitap-Algorithmus (entspricht der Java-int-Größe)

Datenstruktur: Diff (Innere Klasse)

Diffs werden als LinkedList<Diff> dargestellt, wobei jedes Diff eine innere statische Klasse ist mit:

• Operation operation — DELETE, INSERT oder EQUAL
• String text — das Textsegment für diese Operation

Internes Hilfsmittel: LinesToCharsResult

Eine Optimierung für große Texte: Konvertiert Zeilen in eindeutige Unicode-Zeichen, führt das Diff auf der komprimierten Darstellung durch und rekonstruiert dann die Ausgabe auf Zeilenebene. Dies reduziert den Vergleichsraum für zeilenorientierten Text (z. B. Quellcode) drastisch.

Importe

• java.io.UnsupportedEncodingException
• java.net.URLDecoder / URLEncoder — Zum Kodieren der Diff-Ausgabe für URL-sichere Übertragung
• java.util.* — Listen, Maps, ArrayLists, LinkedLists, Regex-Muster

ProjectForge-Verwendung

ProjectForge bettet diese Bibliothek ein, anstatt sie als externes JAR zu verwenden. Dies wurde wahrscheinlich aus folgenden Gründen getan:

1. Die Bibliothek ist stabil und ändert sich selten (die letzte bedeutende Aktualisierung war der Java-Port um 2010)
2. Das Einbetten vermeidet Abhängigkeitsmanagement-Probleme
3. Der Paketname (name.fraser.neil.plaintext) ist eindeutig und konfliktfrei
4. Es könnte kundenspezifische Änderungen für ProjectForge-spezifische Anforderungen geben (obwohl der Code dem Standard-Port zu entsprechen scheint)

DiffMatchPatch wird verwendet, um Änderungen an Textfeldern in ProjectForge-Datenobjekten zu verfolgen — anzuzeigen, was sich zwischen Versionen einer Adresse, Projektbeschreibung oder anderem Textinhalt geändert hat.

48a93dedb Farbige Konsolenausgabe. UserGroupCache-Export zum Debuggen und Vergleichen von Arbeiten jetzt möglich. CollectionUtil verbessert. KotlinStringExtension.shortenMiddle() hinzugefügt.