Ir al contenido
wannacode

La subsecuencia común más larga y diff

En resumen: La subsecuencia común más larga (LCS) de dos secuencias se encuentra con una tabla en O(n · m) y está debajo de diff: las líneas que quedan fuera de ella son las borradas y las añadidas.

Problema

¿Qué cambió en la configuración?

La tienda guarda su configuración en un archivo de texto. Un cliente escribe que el envío de pronto es más barato. El sistema tiene dos versiones del archivo, la de ayer y la de hoy, y necesitas ver exactamente qué cambió, línea por línea, como lo muestra git diff.

La primera idea es comparar la línea 1 con la línea 1, la línea 2 con la línea 2, y así sucesivamente:

const was = [
  "shop=Bookstore", "currency=EUR", "shipping=4.99",
  "free_from=50", "pay=card", "pay=cash",
];
const now = [
  "shop=Bookstore", "currency=EUR", "vat=20",
  "shipping=3.99", "free_from=50", "pay=card",
];
for (let i = 0; i < was.length; i++) {
  if (was[i] === now[i]) {
    console.log("  " + was[i]);
  } else {
    console.log("- " + was[i]);
    console.log("+ " + now[i]);
  }
}
Salida
  shop=Bookstore
  currency=EUR
- shipping=4.99
+ vat=20
- free_from=50
+ shipping=3.99
- pay=card
+ free_from=50
- pay=cash
+ pay=card

El programa dice que cuatro de seis líneas cambiaron. En realidad alguien añadió una línea (vat=20), cambió una (el precio del envío) y quitó una (el pago en efectivo). La línea añadida empujó un lugar hacia abajo todas las líneas que le siguen, y la comparación por número ya no las reconoce.

La idea

Las líneas que se quedaron

Da la vuelta a la pregunta. En lugar de buscar lo que cambió, encuentra lo que se quedó: cuantas más líneas posibles que están en las dos versiones, en el mismo orden. Todo lo demás se quitó («-») o se añadió («+»).

Estas líneas no están necesariamente juntas: las nuevas y las quitadas están entre ellas. Por eso se llama subsecuencia: mantiene el orden pero puede saltarse elementos. El mayor número de esas líneas es la subsecuencia común más larga (LCS).

Encontrarlas probando cada subsecuencia es inútil: un archivo con n líneas tiene 2ⁿ subsecuencias. Pero la tarea tiene lo que viste en el cambio y en la mochila: la respuesta para dos archivos se construye con las respuestas para partes más cortas de ellos. Sea dp[i][j] la longitud de la LCS de las primeras i líneas de la versión vieja y las primeras j de la nueva. Entonces:

  • si la línea i y la línea j son iguales, es común: dp[i][j] = dp[i − 1][j − 1] + 1;
  • si son distintas, al menos una de las dos no está en la subsecuencia común. Descarta una o la otra y quédate con lo mejor: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]);
  • la fila 0 y la columna 0 son ceros: un archivo vacío no tiene nada en común con nada.

Míralo

La tabla

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}
Array.from con una función crea una fila nueva para cada índice. La trampa es new Array(n + 1).fill(new Array(m + 1).fill(0)): fill pone una misma fila en cada lugar, y escribir en dp[1] las cambia todas.

Las dos versiones del archivo y la tabla que el programa calcula para ellas:

const was = [
  "shop=Bookstore", "currency=EUR", "shipping=4.99",
  "free_from=50", "pay=card", "pay=cash",
];
const now = [
  "shop=Bookstore", "currency=EUR", "vat=20",
  "shipping=3.99", "free_from=50", "pay=card",
];
for (const row of lcsTable(was, now)) {
  console.log(row.join(" "));
}
Salida
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 2 2 2 2 2
0 1 2 2 2 2 2
0 1 2 2 2 3 3
0 1 2 2 2 3 4
0 1 2 2 2 3 4

function diff(was, now) {
  const dp = lcsTable(was, now);
  const result = [];
  let i = was.length;
  let j = now.length;
  while (i > 0 && j > 0) {
    if (was[i - 1] === now[j - 1]) {
      result.push("  " + was[i - 1]);
      i--;
      j--;
    } else if (dp[i][j - 1] >= dp[i - 1][j]) {
      result.push("+ " + now[j - 1]);
      j--;
    } else {
      result.push("- " + was[i - 1]);
      i--;
    }
  }
  for (; j > 0; j--) result.push("+ " + now[j - 1]);
  for (; i > 0; i--) result.push("- " + was[i - 1]);
  return result.reverse();
}
Paso a paso, en palabras
  1. Versión vieja a la izquierda (was), nueva arriba (now). La fila 0 y la columna 0 son ceros: un archivo vacío no tiene líneas en común con nada.
  2. Fila 1: shop=Bookstore es igual a la primera línea de now. Líneas iguales: la diagonal + 1. La celda se pone verde.
  3. Líneas distintas: la mayor entre la celda de arriba y la de la izquierda. No hay una línea común nueva, solo lo mejor hasta ahora.
  4. currency=EUR también coincide: 1 + 1 = 2. shipping=4.99 en la fila 3 no coincide con nada, así que la fila solo traslada los 2.
  5. Más abajo coinciden free_from=50 y pay=card, y los números crecen hasta 3 y 4.
  6. La esquina dp[6][6] = 4: las dos versiones tienen 4 líneas en común. Cuáles, lo dice el camino de vuelta.
  7. El camino de vuelta empieza en la esquina. pay=cash ≠ pay=card, arriba hay 4 y a la izquierda 3: hacia arriba. pay=cash se quitó: «- pay=cash».
  8. pay=card = pay=card: una línea común, por la diagonal. Lo mismo para free_from=50.
  9. shipping=4.99 ≠ shipping=3.99, y los números de arriba y de la izquierda son iguales: a la izquierda, «+ shipping=3.99». Luego «+ vat=20».
  10. Arriba hay 2, a la izquierda 1: hacia arriba, «- shipping=4.99». Luego las dos líneas comunes por la diagonal, hasta el 0 de la esquina.
  11. El camino fue del final al principio, por eso result.reverse() da la vuelta a las líneas. El diff: vat=20 es nueva, shipping cambió, pay=cash ya no está.

El número de la esquina inferior derecha es 4: se quedaron cuatro líneas. Cuáles, lo dice el camino de vuelta.

Pruébalo

Predice la salida

La ruta del mensajero el martes y el miércoles. ¿Cuántas paradas están en el mismo orden los dos días?

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}


const tuesday = [
  "Almacén", "Ribera", "Centro", "Colina", "Casco Antiguo",
];
const wednesday = [
  "Almacén", "Centro", "Ribera", "Casco Antiguo",
];
const dp = lcsTable(tuesday, wednesday);
console.log(dp[tuesday.length][wednesday.length]);
Respuesta

La idea

El camino de vuelta: diff

La tabla recuerda cómo se obtuvo cada número. Empieza en la esquina dp[n][m] y vuelve atrás:

  • las líneas son iguales: una línea común, escríbela con un espacio y avanza por la diagonal;
  • la celda de la izquierda no es menor que la de arriba: la línea j de la versión nueva no está en la subsecuencia común, escríbela con «+» y ve a la izquierda;
  • si no, la línea i de la versión vieja no está en la nueva: escríbela con «-» y ve hacia arriba.

Cuando llegas al final de una versión, todo lo que queda de la otra es solo «+» o solo «-». El camino va de las últimas líneas a las primeras, así que al final se le da la vuelta a la lista.

function diff(was, now) {
  const dp = lcsTable(was, now);
  const result = [];
  let i = was.length;
  let j = now.length;
  while (i > 0 && j > 0) {
    if (was[i - 1] === now[j - 1]) {
      result.push("  " + was[i - 1]);
      i--;
      j--;
    } else if (dp[i][j - 1] >= dp[i - 1][j]) {
      result.push("+ " + now[j - 1]);
      j--;
    } else {
      result.push("- " + was[i - 1]);
      i--;
    }
  }
  for (; j > 0; j--) result.push("+ " + now[j - 1]);
  for (; i > 0; i--) result.push("- " + was[i - 1]);
  return result.reverse();
}
for (const line of diff(was, now)) {
  console.log(line);
}
Salida
  shop=Bookstore
  currency=EUR
- shipping=4.99
+ vat=20
+ shipping=3.99
  free_from=50
  pay=card
- pay=cash

Ahora se ve la verdad: vat=20 es nueva, shipping cambió (se quitó una línea vieja y se añadió una nueva), pay=cash ya no está. La elección «a la izquierda cuando los números son iguales» pone «-» antes que «+» en el mismo lugar, como hace git.

Pruébalo

Encuentra el error

Un compañero escribió la tabla. El programa ejecuta el mismo diff, pero con su tabla:

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left) + 1;
      }
    }
  }
  return dp;
}
for (const line of diff(was, now)) {
  console.log(line);
}
Salida
  shop=Bookstore
- currency=EUR
- shipping=4.99
- free_from=50
- pay=card
- pay=cash
+ currency=EUR
+ vat=20
+ shipping=3.99
+ free_from=50
+ pay=card

currency=EUR se quita y también se añade, aunque nadie lo tocó. ¿En qué línea está el error?

Elige la línea con el error.

La idea

Cuánto cuesta

La tabla tiene (n + 1) · (m + 1) celdas y cada una necesita una comparación de dos líneas. El tiempo es O(n · m), y la memoria también (ver complejidad en espacio). Ejecuta los dos caminos: cada subsecuencia de la versión vieja, una por una, y la tabla. Contamos las subsecuencias comprobadas y las celdas de la tabla. Las dos versiones tienen n líneas:

  • Cada subsecuencia O(2ⁿ)
  • La tabla dp[i][j] O(n²)
Algoritmon = 10n = 20n = 1000n = 3000n = 100.000
Cada subsecuencia10241.048.576≈ 10³⁰¹≈ 10⁹⁰³≈ 10³⁰¹⁰²
La tabla dp[i][j]1004001.000.0009.000.000≈ 10.000.000.000
El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.
function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}

Con 20 líneas ya hay 1 048 576 subsecuencias, y la tabla tiene 400 celdas. Con 1000 líneas la tabla tiene 1 000 000 de celdas, con 3000 líneas 9 000 000. Un archivo de 100 000 líneas, en cambio, necesita 10 000 000 000 de celdas, y a 4 bytes por celda son 40 GB de memoria. Por eso las herramientas de diff reales no llenan toda la tabla.

Más precisamente, para curiosos

El algoritmo de Myers (Eugene Myers, 1986) encuentra el mismo diff más corto, pero parte de la pregunta «cuántas líneas como mínimo necesito quitar y añadir». Si ese número es D, el tiempo es O((n + m) · D). Dos versiones de un archivo suelen diferir en pocas líneas, así que D es pequeño y el algoritmo es casi lineal. Es el predeterminado en git diff y en diff de GNU. Git tiene otros: --patience e --histogram dan diffs más legibles cuando se mueven bloques de código, y --minimal se esfuerza más por el más corto.

Si solo necesitas la longitud de la LCS, bastan dos filas de la tabla: la fila i solo usa la fila i − 1. La memoria pasa a ser O(m). El algoritmo de Hirschberg (1975) conserva también el camino, con memoria O(n + m), partiendo la tarea por la mitad.

Cómo es en los lenguajes:

  • Python tiene difflib en la biblioteca estándar: difflib.unified_diff(was, now) imprime un diff como el de git. Busca el bloque común más largo de líneas consecutivas y repite a la izquierda y a la derecha, así que su diff no siempre es el más corto;
  • Java y C# no tienen diff en la biblioteca estándar. Se usan bibliotecas: java-diff-utils en Java, DiffPlex en C#, ambas con el algoritmo de Myers;
  • JavaScript tampoco lo tiene. El paquete diff de npm (jsdiff) usa Myers.

La idea

La misma tabla, otra pregunta: «¿Querías decir…?»

Un cliente busca «lapto» y no encuentra nada. El buscador de la tienda debería sugerir «laptop»: la palabra del catálogo más cercana a lo que se escribió.

La cercanía se mide con la distancia de Levenshtein: cuántas letras como mínimo tienes que insertar, borrar o cambiar para convertir una palabra en la otra. «lapto» → «laptop» es 1: insertas «p».

La tabla es la misma que para la LCS, solo cambia la pregunta. d[i][j] es la distancia entre las primeras i letras de la consulta y las primeras j de la palabra:

  • la fila 0 y la columna 0 ya no son ceros: d[i][0] = i (borras las i letras), d[0][j] = j;
  • en los demás casos, d[i][j] es el menor de tres pasos: borrar (d[i − 1][j] + 1), insertar (d[i][j − 1] + 1) y cambiar (d[i − 1][j − 1], más 1 si las letras son distintas).

Esto lo escribirás en el ejercicio.

Más precisamente, para curiosos

Los buscadores reales no se detienen aquí. Cuentan con qué frecuencia se busca cada palabra («laptop» es más probable que «lámpara», incluso a la misma distancia), lo cerca que están las letras en el teclado y si dos letras solo están intercambiadas. Las letras vecinas intercambiadas son el error de escritura más común, y Levenshtein las cuenta como 2. La variante de Damerau cuenta un intercambio como 1.

LCS y Levenshtein son parientes: si permites solo insertar y borrar, sin cambiar, la distancia es n + m − 2 · LCS. Cada letra fuera de la subsecuencia común se borra de una palabra o se inserta en la otra.

Ejercicio

«¿Querías decir…?»

Resuelve la tarea en tu editor.

Sugerencias. El catálogo es «laptop», «lámpara», «tableta», «teléfono», «audífonos» y «monitor», y los clientes buscaron «lapto», «telefno», «tabelta» y «monito». Escribe distance(query, word) con la tabla de Levenshtein y, para cada consulta, imprime la palabra del catálogo más cercana y la distancia (en caso de empate, la primera del catálogo):

Salida
lapto → laptop (1)
telefno → teléfono (2)
tabelta → tableta (2)
monito → monitor (1)

Más tareas

  • Un intercambio por 1. Añade el paso «intercambiar dos letras vecinas» (Damerau–Levenshtein). ¿En qué se convierte «tabelta» → «tableta»?
  • Solo si está cerca. No sugieras nada si la palabra más cercana está a más de un tercio de la longitud de la consulta.
  • Un diff de palabras. Ejecuta el diff de la lección no sobre líneas, sino sobre las palabras de dos descripciones de producto, separadas por espacios.

Test

Ponte a prueba

1. ¿Por qué comparar «la línea i de la versión vieja con la línea i de la nueva» muestra casi todo como cambiado?
2. ¿Qué va en dp[i][j] cuando la línea i de la versión vieja y la línea j de la nueva son iguales?
3. Dos archivos tienen 10 000 líneas cada uno. ¿Cuántas celdas llena la tabla?
4. El camino de vuelta empieza en dp[n][m]. ¿Por qué se le da la vuelta a la lista al final?
5. ¿Es [shop=Bookstore, free_from=50, pay=card] una subsecuencia de la versión nueva, aunque entre ellas haya otras líneas?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·