El Algoritmo Myers Diff: Cómo Funciona Realmente la Comparación de Textos

Si alguna vez ha ejecutado `git diff`, usado una herramienta de revisión de código o comparado dos documentos en cualquier software moderno, ha usado el algoritmo Myers diff — casi con certeza sin saberlo. Publicado por Eugene W. Myers en 1986 en la revista Algorithmica, el artículo "An O(ND) Difference Algorithm and Its Variations" (Un Algoritmo de Diferencias O(ND) y sus Variaciones) introdujo el algoritmo que se convirtió en el estándar para la comparación de texto en todas partes, desde Unix diff hasta GitHub y LineDiff.

Entender cómo funciona el algoritmo Myers no solo satisfará la curiosidad intelectual — también le ayudará a entender por qué las herramientas de comparación producen el resultado que producen, y qué compensaciones se hacen en el proceso.

**¿Qué Es una Diferencia?**

En su forma más básica, una diferencia es la respuesta a esta pregunta: dadas dos secuencias A y B, ¿cuál es el conjunto mínimo de cambios necesarios para transformar A en B? Un "cambio" puede ser una inserción (agregar algo que está en B pero no en A) o una eliminación (quitar algo que está en A pero no en B). Los elementos sin cambios — líneas que aparecen tanto en A como en B en el mismo orden relativo — se llaman la subsecuencia común.

El objetivo de cualquier algoritmo de diferencias es encontrar la Subsecuencia Común Más Larga (LCS) de A y B, porque una vez que conoce la LCS, todo lo que está en A que no está en la LCS debe haber sido eliminado, y todo lo que está en B que no está en la LCS debe haber sido insertado.

**El Grafo de Edición**

Myers representa el problema de la diferencia visualmente como una cuadrícula, a menudo llamada grafo de edición. Imagine una cuadrícula donde el eje x representa posiciones en la secuencia A (el documento original) y el eje y representa posiciones en la secuencia B (el documento revisado). Comienza en la esquina superior izquierda (0, 0) y quiere llegar a la esquina inferior derecha (|A|, |B|).

Mover un paso a la derecha significa eliminar un elemento de A. Mover un paso hacia abajo significa insertar un elemento de B. Moverse diagonalmente — a la derecha y hacia abajo simultáneamente — significa mantener un elemento que es el mismo en A y B. Este movimiento diagonal es gratuito, en el sentido de que no cuenta como una edición.

Encontrar la distancia mínima de edición entre A y B equivale a encontrar el camino más corto desde la esquina superior izquierda hasta la esquina inferior derecha de esta cuadrícula, donde los movimientos diagonales son gratuitos y los movimientos horizontales o verticales cuestan una edición cada uno.

**El Script de Edición Más Corto**

La secuencia de movimientos a lo largo de este camino más corto se llama el Script de Edición Más Corto (SES). El algoritmo Myers encuentra el SES de manera eficiente sin explorar todos los caminos posibles a través de la cuadrícula — lo cual sería computacionalmente intratable para cualquier documento del mundo real.

La intuición clave del artículo de Myers es buscar en el grafo de edición de manera codiciosa, priorizando las diagonales. En lugar de explorar en amplitud desde la esquina de inicio, el algoritmo rastrea los caminos que alcanzan más lejos para cada distancia de edición d, comenzando desde d=0 y aumentando. Para cada d, encuentra el punto más lejano alcanzable en cada diagonal k (donde k = x - y) usando como máximo d ediciones. Los caminos diagonales se extienden lo más lejos posible de forma gratuita antes de contar la siguiente edición.

**Complejidad O(ND)**

El algoritmo se ejecuta en tiempo O(ND), donde N es la suma de las longitudes de A y B, y D es el número de ediciones en el SES. Esto es casi óptimo: cuando D es pequeño (cuando los dos documentos son mayormente iguales), el algoritmo es extremadamente rápido. Cuando D es grande (cuando los dos documentos son muy diferentes), tarda más — pero en este caso, fundamentalmente hay más trabajo por hacer, y ningún algoritmo puede evitarlo.

En la práctica, para comparaciones típicas de documentos — dos versiones de un documento de política, dos borradores de un contrato, dos archivos de configuración — D es pequeño en relación a N, y el algoritmo Myers es extremadamente rápido. Por eso incluso los documentos grandes (100+ páginas) producen resultados en milisegundos en LineDiff.

**Limpieza Semántica**

El resultado bruto del algoritmo Myers es sintácticamente óptimo — produce el script de edición más corto — pero no siempre es semánticamente óptimo para los lectores humanos. Considere una diferencia que muestra la mitad de una oración eliminada y la nueva mitad de una oración insertada, cuando un lector humano describiría naturalmente esto como "la oración fue reescrita". El algoritmo de Myers no sabe qué es una oración; solo conoce la secuencia de caracteres o líneas que se le da.

La mayoría de las herramientas de comparación aplican un paso de limpieza semántica después de ejecutar el algoritmo principal. Este paso reorganiza las inserciones y eliminaciones en bruto para alinearse con los límites del lenguaje natural — límites de palabras, límites de oraciones, límites de párrafos — produciendo una diferencia que es más fácil de interpretar para los humanos sin cambiar el conjunto subyacente de ediciones.

**Cómo LineDiff Implementa Myers en Web Workers**

LineDiff ejecuta su cálculo de diferencias en un hilo Web Worker dedicado. Esto es crítico para la experiencia del usuario: el algoritmo Myers, aunque es rápido, puede tardar decenas de milisegundos para documentos grandes. Ejecutarlo en el hilo principal del navegador bloquearía la interfaz de usuario — la página se congelaría mientras se calculaba la diferencia. Al descargar el cálculo a un worker, LineDiff mantiene la interfaz responsiva e incluso puede mostrar resultados progresivos a medida que se completa la diferencia.

El worker recibe los dos documentos como cadenas, los tokeniza en líneas (para diferencias a nivel de línea) o palabras (para diferencias en línea), ejecuta el algoritmo Myers, aplica la limpieza semántica y devuelve el resultado de diferencia anotado al hilo principal. El pipeline completo normalmente se completa en menos de 100 milisegundos para documentos de hasta 10.000 líneas.

**La Capa de IA Encima**

Myers le da la verdad sintáctica: exactamente qué caracteres cambiaron. No le da el significado semántico: qué significan esos cambios en contexto. Aquí es donde la capa de análisis de IA de LineDiff agrega valor.

Después de calcular la diferencia Myers, LineDiff opcionalmente envía el conjunto de cambios a un LLM (GPT-4o por defecto, o su propia clave de OpenAI a través de BYOK). La IA recibe la diferencia estructurada — no los documentos en bruto — y produce un análisis con conocimiento del dominio: qué cambios son sustantivamente importantes, cuáles son cosméticos y cuál es el efecto general de la revisión.

Para un documento legal, la IA distingue entre una coma insertada para claridad gramatical y una cláusula que cambia materialmente las obligaciones de una parte. Para un informe financiero, señala los cambios en valores numéricos versus los cambios en el comentario narrativo. Para un protocolo clínico, resalta los cambios de dosificación y elegibilidad versus las tareas administrativas de mantenimiento.

El algoritmo Myers le dice qué cambió. La IA le dice por qué importa. Juntos, hacen de LineDiff más que una herramienta de comparación — lo convierten en una plataforma de inteligencia documental construida sobre un algoritmo de 40 años que fue, y sigue siendo, la mejor solución a uno de los problemas más fundamentales de la informática.