#1873: DiffMatchPatch.java

Библиотека алгоритмов diff-match-patch от Google, автор Нил Фрейзер, встроена непосредственно в ProjectForge в оригинальном пакете name.fraser.neil.plaintext. Лицензия Apache License 2.0. Предоставляет синхронное сравнение текста (diff), нечёткое сопоставление (match) и применение патчей (patch) — те же алгоритмы, которые используются в Google Docs, Etherpad и сравнении версий Wikipedia. Используется ProjectForge для отслеживания изменений текста и сравнения версий.

Происхождение и лицензия

• Автор: Нил Фрейзер (fraser@google.com), Google Inc.
• Авторские права: 2006 Google Inc.
• Лицензия: Apache License 2.0
• Оригинальный проект: google-diff-match-patch на GitHub
• Домашняя страница: http://code.google.com/p/google-diff-match-patch/ (оригинальный Google Code, ныне архивный)
• Сохранённый пакет: name.fraser.neil.plaintext — точное имя пакета из оригинальной библиотеки

Обзор алгоритмов

Библиотека реализует три связанных алгоритма, все работают с обычным текстом:

1. Diff — алгоритм различий Майерса O(ND)

Вычисляет минимальный набор правок для преобразования text1 в text2. Основной алгоритм — алгоритм различий Майерса (1986), который находит кратчайший сценарий редактирования, используя подход O(ND) по времени/памяти, где N — сумма длин строк, а D — количество различий.

• Перечисление операций: DELETE, INSERT, EQUAL — каждое различие представляет собой связанный список операций
• Оптимизации: удаление общего префикса/суффикса, предварительное сравнение на уровне строк (флаг checklines), досрочное завершение по дедлайну
• Постобработка: diff_cleanupSemantic() делает различия удобочитаемыми; diff_cleanupEfficiency() оптимизирует для машинной обработки; diff_cleanupMerge() объединяет соседние операции равенства/удаления
• Семантическая очистка: распознаёт границы предложений/абзацев, короткие изолированные равенства и изменения пробелов для более интуитивного вывода

2. Match — алгоритм Bitap (Shift-Or)

Находит наилучшее приблизительное совпадение шаблона в большом тексте. Использует алгоритм Bitap (также известный как shift-or или алгоритм Баэзы-Йейтса–Гонне), который:

• Кодирует шаблон как битовую маску позиций символов
• Использует побитовые операции для приблизительного поиска строки за O(n)
• Поддерживает нечёткое сопоставление с настраиваемым порогом ошибки (Match_Threshold)
• Использует систему оценки, чувствительную к расположению (Match_Distance), чтобы предпочитать совпадения рядом с ожидаемой позицией

3. Patch — унифицированный формат diff + нечёткое применение

Создаёт патчи (текстовые представления различий), которые можно сериализовать, передавать и применять к другим текстам:

• Использует формат, похожий на унифицированный diff: @@ -start,length +start,length @@ контекст
• Патчи можно применять с допуском на смещение номеров строк (контекст Patch_Margin для сопоставления)
• patch_apply() пытается выполнить нечёткое сопоставление, когда точный контекст не совпадает — внутренне использует алгоритм Match
• Поддерживает частичное применение патчей с результатами, указывающими, какие патчи успешно применились

Ключевые параметры конфигурации

Поле	По умолчанию	Назначение
Diff_Timeout	1.0 секунда	Максимальное время для вычисления diff перед возвратом частичного результата (0 = бесконечно)
Diff_EditCost	4	Стоимость пустой операции редактирования — более высокие значения дают более чистые, менее фрагментированные различия
Match_Threshold	0.5	Порог нечёткого сопоставления (0.0 = точное, 1.0 = очень неточное)
Match_Distance	1000	Бонус за расположение — расстояние в символах от ожидаемой позиции совпадения
Patch_DeleteThreshold	0.5	Насколько точно блоки удаления должны соответствовать ожидаемому содержимому для принятия
Patch_Margin	4	Количество символов контекста вокруг фрагментов патча
Match_MaxBits	32	Разрядность для алгоритма Bitap (соответствует размеру int в Java)

Структура данных: Diff (внутренний класс)

Различия представлены как LinkedList<Diff>, где каждый Diff — это внутренний статический класс с:

• Operation operation — DELETE, INSERT или EQUAL
• String text — текстовый сегмент для этой операции

Внутренний помощник: LinesToCharsResult

Оптимизация для больших текстов: преобразует строки в уникальные символы Unicode, выполняет diff над сжатым представлением, затем восстанавливает вывод на уровне строк. Это значительно сокращает пространство сравнения для текстов, ориентированных на строки (например, исходный код).

Импорты

• java.io.UnsupportedEncodingException
• java.net.URLDecoder / URLEncoder — для кодирования вывода diff для безопасной передачи через URL
• java.util.* — Lists, Maps, ArrayLists, LinkedLists, regex Patterns

Использование в ProjectForge

ProjectForge встраивает эту библиотеку, а не использует её как внешний JAR. Вероятно, это сделано потому, что:

1. Библиотека стабильна и редко меняется (последнее значительное обновление — порт на Java около 2010 года)
2. Встраивание позволяет избежать проблем управления зависимостями
3. Имя пакета (name.fraser.neil.plaintext) уникально и не вызывает конфликтов
4. Возможно, в неё внесены пользовательские изменения для нужд ProjectForge (хотя код выглядит как стандартный порт)

DiffMatchPatch используется для отслеживания изменений в текстовых полях объектов данных ProjectForge — показывает, что изменилось между версиями адреса, описания проекта или другого текстового содержимого.

48a93dedb Цветной лог консоли. Экспорт UserGroupCache для отладки и сравнения работы теперь доступен. CollectionUtil улучшен. Добавлен KotlinStringExtension.shortenMiddle().