#1873: DiffMatchPatch.java

La biblioteca de algoritmos diff-match-patch de Google, de Neil Fraser, incrustada directamente en ProjectForge bajo el paquete original name.fraser.neil.plaintext. Licenciada bajo Apache License 2.0. Proporciona comparación de texto síncrona (diff), coincidencia difusa (match) y aplicación de parches (patch) — los mismos algoritmos que impulsan Google Docs, Etherpad y la comparación de revisiones de Wikipedia. Utilizada por ProjectForge para el seguimiento de cambios de texto y comparación de versiones.

Origen y Licencia

• Autor: Neil Fraser (fraser@google.com), Google Inc.
• Copyright: 2006 Google Inc.
• Licencia: Apache License 2.0
• Proyecto original: google-diff-match-patch en GitHub
• Sitio web: http://code.google.com/p/google-diff-match-patch/ (Google Code original, ahora archivado)
• Paquete preservado: name.fraser.neil.plaintext — el nombre exacto del paquete de la biblioteca original

Resumen del Algoritmo

La biblioteca implementa tres algoritmos relacionados, todos operando sobre texto plano:

1. Diff — Algoritmo de Diferencias O(ND) de Myers

Calcula el conjunto mínimo de ediciones para transformar texto1 en texto2. El algoritmo central es el algoritmo diff de Myers (1986), que encuentra el script de edición más corto utilizando un enfoque O(ND) en tiempo/espacio, donde N es la suma de las longitudes de las cadenas y D es el número de diferencias.

• Enum de operación: DELETE, INSERT, EQUAL — cada diff es una lista enlazada de operaciones
• Optimizaciones: eliminación de prefijos/sufijos comunes, precomparación a nivel de línea (bandera checklines), terminación anticipada basada en plazo
• Post-procesamiento: diff_cleanupSemantic() hace los diffs legibles para humanos; diff_cleanupEfficiency() optimiza para procesamiento automático; diff_cleanupMerge() fusiona operaciones adyacentes de igualdad/eliminación
• Limpieza semántica: reconoce límites de oraciones/párrafos, igualdades aisladas cortas y cambios de espacios en blanco para una salida más intuitiva

2. Match — Algoritmo Bitap (Shift-Or)

Localiza la mejor coincidencia aproximada para un patrón dentro de un texto más grande. Utiliza el algoritmo Bitap (también conocido como shift-or o algoritmo Baeza-Yates–Gonnet) que:

• Codifica el patrón como una máscara de bits de posiciones de caracteres
• Utiliza operaciones bit a bit para la coincidencia aproximada de cadenas en O(n)
• Soporta coincidencia difusa con un umbral de error configurable (Match_Threshold)
• Utiliza un sistema de puntuación sensible a la localidad (Match_Distance) para preferir coincidencias cercanas a la ubicación esperada

3. Patch — Formato Diff Unificado + Aplicación Difusa

Crea parches (representaciones textuales de diffs) que pueden ser serializados, transmitidos y aplicados a otros textos:

• Utiliza un formato similar a diff unificado: @@ -inicio,longitud +inicio,longitud @@ contexto
• Los parches se pueden aplicar con tolerancia a la desviación del número de línea (contexto Patch_Margin para la coincidencia)
• patch_apply() intenta la coincidencia difusa cuando el contexto exacto no coincide — utiliza internamente el algoritmo Match
• Soporta la aplicación parcial de parches con resultados que indican qué parches tuvieron éxito

Parámetros Clave de Configuración

Campo	Valor por defecto	Propósito
Diff_Timeout	1.0 segundos	Segundos máximos para un cálculo diff antes de devolver un resultado parcial (0 = infinito)
Diff_EditCost	4	Costo de una operación de edición vacía — valores más altos producen diffs más limpios y menos fragmentados
Match_Threshold	0.5	Umbral de coincidencia difusa (0.0 = exacto, 1.0 = muy flexible)
Match_Distance	1000	Bonificación de localidad — distancia en caracteres desde la ubicación de coincidencia esperada
Patch_DeleteThreshold	0.5	Qué tan cerca deben coincidir los bloques eliminados con el contenido esperado para ser aceptados
Patch_Margin	4	Número de caracteres de contexto alrededor de los fragmentos del parche
Match_MaxBits	32	Ancho de bits para el algoritmo Bitap (coincide con el tamaño de int en Java)

Estructura de Datos: Diff (Clase Interna)

Los diffs se representan como un LinkedList<Diff> donde cada Diff es una clase interna estática con:

• Operation operation — DELETE, INSERT o EQUAL
• String text — el segmento de texto para esta operación

Ayudante Interno: LinesToCharsResult

Una optimización para textos grandes: convierte líneas en caracteres Unicode únicos, realiza el diff en la representación comprimida y luego reconstruye la salida a nivel de línea. Esto reduce drásticamente el espacio de comparación para texto orientado a líneas (por ejemplo, código fuente).

Importaciones

• java.io.UnsupportedEncodingException
• java.net.URLDecoder / URLEncoder — Para codificar la salida diff para transmisión segura en URL
• java.util.* — Listas, Mapas, ArrayLists, LinkedLists, patrones regex

Uso en ProjectForge

ProjectForge incrusta esta biblioteca en lugar de depender de ella como un JAR externo. Esto probablemente se hizo porque:

1. La biblioteca es estable y rara vez cambia (la última actualización significativa fue el puerto a Java alrededor de 2010)
2. La incrustación evita problemas de gestión de dependencias
3. El nombre del paquete (name.fraser.neil.plaintext) es distintivo y no entra en conflicto
4. Puede tener modificaciones personalizadas para necesidades específicas de ProjectForge (aunque el código parece ser el puerto estándar)

DiffMatchPatch se utiliza para rastrear cambios en campos de texto en los objetos de datos de ProjectForge — mostrando qué cambió entre versiones de una dirección, descripción de proyecto u otro contenido de texto.

48a93dedb Registro de consola coloreado. UserGroupCache exportado para depuración y comparación de trabajo ahora. CollectionUtil mejorado. KotlinStringExtension.shortenMiddle() añadido.