Saltar a contenido

Levenshtein Distance

Problema

Sean dos strings \(s\), \(m\). Queremos tener una métrica que mida que tan similares son las dos cadenas de texto entre sí. Se definen 3 transformaciones posibles que se pueden hacer carácter a carácter:

  • Delete(\(s\), \(i\)): Se borra el carácter \(i\) del string \(s\).
  • Insert(\(s\), \(i\), \(a\)): Se añade el carácter \(a\) en la posición \(i\) del string \(s\).
  • Replace(\(s\), \(i\), \(a\)): Se reemplaza el carácter \(a\) en la posición \(i\) del string \(s\).

Desde ahora en adelante vamos a entender como que cada una de estas operaciones cuenta como una operación dentro de los string. Vamos a entender entonces como distancia de Levenshtein como la distancia \(D(s, m)\) tal que se minimicen las cantidades de estas operaciones que tienen que ser realizadas para transformar el string \(s\) al string \(m\). Notemos que \(D(s, m) = D(m, s)\) ya que siempre por cada operación de adición se puede reemplazar por una operación de sustracción para realizar el proceso inverso y la operación de replace solo tendría que cambiar el carácter por el que se reemplaza en el string. O sea:

  • Insert puede verse como la operación inversa de delete
  • replace seria su propia operación inversa.

En síntesis la simetría se cumple porque el conjunto de operaciones es reversible con costo unitario.

Ejemplo

Sea \(s= "banana"\) y m = \("rana"\)

Podemos aplicar las siguientes operaciones:

  • Delete(\(s\), \(0\)): \(s= anana\)
  • Delete(\(s\), \(0\)): \(s= nana\)
  • Replace(\(s\), \(0\), 'r'): \(s= rana\)

Se requirieron 3 operaciones. Se puede verificar con lo que se va a ver en las diferentes secciones que esta es la minima cantidad de operaciones por lo tanto la Distancia de Levenshtein es de \(D(s, m) = 3\).

Ahora también podemos notar que \(D(s, m) = D(m, s)\). Si aplicamos:

  • Replace(\(m\), \(0\), 'n'): \(m= nana\)
  • Insert(\(m\), \(0\), 'a'): \(m= anana\)
  • Insert(\(m\), \(0\), 'b'): \(m= banana\)

Solución propuesta

La solución aquí propuesta utiliza programación dinámica. Primero definamos unos casos base.

Notemos que en este problema tenemos 4 situaciones posibles a las que nos podemos enfrentar:

  • Digamos que en rana y banana, ambos tienen en su último indice el mismo carácter, 'a'. En ese caso no es necesario aplicar ninguna operación. Y la respuesta seria la misma que \(D(s, m) = D(s[:n_1-1], m[:n_2-1])\) con \(n_1\) y \(n_2\) los largos de los strings de \(s\) y \(m\).

  • Si los 2 últimos caracteres son distintos, se puede aplicar Replace en el último y sumar la distancia de \(D(s[:n_1-1], m[:n_2-1])\) haciendo la respuesta \(1 + D(s[:n_1-1], m[:n_2-1])\)

  • Podemos añadir con Insert un carácter. Por ejemplo si tenemos los strings \(s=lunar\) y \(m=luna\) podemos añadir un carácter al final haciendo que la respuesta sea \(1 + D(s[:], m[:n_2-1])\)

  • Podemos eliminar con Delete un carácter. Por ejemplo si tenemos los strings \(s=lunar\) y \(m=luna\) podemos eliminar un carácter al final de \(s\) y así la distancia va a ser \(1 + D(s[:n_1-1], m[:])\).

Con estos 4 casos de las acciones que tenemos disponibles queda evidente la estructura recursiva que va a seguir el problema

Si los caracteres son iguales entonces la distancia es igual a la distancia del substring que no incluye dichos caracteres. Si no hay que ver el mínimo de las 3 operaciones y aplicar esa. Después se repite esto de manera recursiva

Si \(s=""\) y \(m=""\), o sea que los 2 strings estén vacíos, entonces \(D(s,m) = 0\). Otro caso que es interesante a revisar es si uno de los 2 strings esta vacío y el otro tiene un solo carácter, por ejemplo \(s="b"\) y \(m=""\). Para pasar de \(s\) a \(m\) simplemente hay que realizar una operación de \(Delete(s,0)\) por lo que en estos casos \(D(s,m) = 1\). Si hay que insertar o borrar \(n\) caracteres entonces la distancia va a ser \(n\) si el otro string esta vacío.

Así comenzamos a completar la siguiente tabla:

r a n a
0 1 2 3 4
b 1
a 2
n 3
a 4
n 5
a 6

Vamos a denominar de ahora en adelante esta matriz como \(tab[i][j]\) con i, j indices arbitrarios dentro de esta matriz. Cada celda representa un subproblema de nuestro problema original.

Por ejemplo \(tab[2][3]\) representaría el substring de \(s="ba"\) y en \(m="ran"\) al que vamos a querer resolver la distancia de Levenshtein.

Comencemos rellenando la primera celda que no es un caso base, o sea \(tab[1][1]\). Los substring correspondientes son \(s="b"\) y en \(m="r"\). Los 2 caracteres no coinciden. Tenemos entonces 3 opciones:

  • Aplicar Delete y borrar el último carácter. Lo que seria equivalente a un costo de \(tab[0][1] + 1 = 1 + 1 = 2\)

  • Aplicar Insert e insertar el último carácter. Lo que seria equivalente a un costo de \(tab[1][0] + 1 = 1 + 1 = 2\)

  • Aplicar Replace y reemplazar el último carácter. Lo que seria equivalente a un costo de \(tab[0][0] + 1 = 0 + 1 = 1\)

Así aplicamos la operación que minimiza la distancia, o sea Replace y la tabla queda así:

r a n a
0 1 2 3 4
b 1 1
a 2
n 3
a 4
n 5
a 6

De aquí podemos extrapolar la siguiente relación recursiva:

\[ \text{tab}[i][j] = \min\big( \text{tab}[i-1][j] + 1,\; \text{tab}[i][j-1] + 1,\; \text{tab}[i-1][j-1] + (0 \text{ si } s[i-1] = m[j-1],\; 1 \text{ si } s[i-1] \neq m[j-1]) \big) \]

A partir de esto podemos obtener la siguiente tabla:

r a n a
0 1 2 3 4
b 1 1 2 3 4
a 2 2 1 2 3
n 3 3 2 1 2
a 4 4 3 2 1
n 5 5 4 3 2
a 6 6 5 4 3

Se puede obtener la respuesta en la esquina inferior derecha. En el ejemplo la respuesta es \(tab[6][4]=3\).

Análisis de complejidad temporal

Hay que iterar una sola vez por cada celda de la matriz. Dentro de las mismas se compara con 3 celdas adyacentes de la misma lo que serian operaciones \(O(1)\). Sea \(a =|s|\) y \(b =|m|\) la complejidad temporal de este algoritmo seria:

\[O(ab)\]

Análisis de complejidad espacial

Si mantuviéramos la tabla completa se requerirían: \(\(O(ab)\)\)

Pero no es necesario mantener un registro de toda esta tabla. Si nos damos cuenta para ejecutar este algoritmo solo requerimos mantener registro de la fila actual y la anterior a esta, por lo que solo hay que mantener estas en memoria. Además de esto podemos hacer que el string que represente a las filas en nuestra matriz sea el mas corto entre los 2. Así la complejidad espacial bajaría a:

\[O(\min(a,b))\]

Prueba de correctitud del algoritmo

1. Correctitud por inducción doble

Afirmación: para todo \((0\le i\le |s|)\) y \((0\le j\le |m|)\), el valor que computa el algoritmo satisface la definición inductiva de distancia de edición; en particular, el valor final \(D(|s|,|m|)\) es \(\operatorname{ED}(s,m)\).

Base:

  • \(D(0,j)=j\): si \(s\) es vacío, debemos insertar \(j\) caracteres para obtener \(m[1..j]\).
  • \(D(i,0)=i\): si \(m\) es vacío, debemos eliminar \(i\) caracteres de \(s[1..i]\).

Estas condiciones iniciales coinciden con la definición de costo mínimo.

Hipótesis inductiva: supongamos correctos todos los valores \(D(a,b)\) para \(0\le a<i\) y \(0\le b<j\).

Paso inductivo:

  • Si \(s_i=m_j\), cualquier alineación óptima puede hacer coincidir estos caracteres al final sin costo, por lo que el costo es \(D(i-1,j-1)\), correcto por hipótesis.
  • Si \(s_i\ne m_j\), toda secuencia óptima debe terminar en una de las tres operaciones (del., ins., repl.). El costo resultante es \(1+\min{D(i-1,j),D(i,j-1),D(i-1,j-1)}\). Cada término es correcto por hipótesis y tomar el mínimo produce el costo óptimo.

Por inducción doble, la tabla completa es correcta y, en particular, \(D(|s|,|m|)\) es la distancia de edición.

2. Minimalidad (no existen soluciones más baratas)

La demostración anterior garantiza que existe una secuencia de costo \(D(i,j)\) (suficiencia). Para la necesidad, obsérvese que cualquier secuencia de edición que transforme \(s[1..i]\) en \(m[1..j]\) induce, al cortar en su último paso, induce una de las tres descomposiciones (del/ins/rep); por tanto su costo es \(\ge\) que el mínimo de los tres costos parciales (o igual a \(D(i-1,j-1)\) si coincide el último carácter). De aquí se sigue que ninguna secuencia puede ser más barata que el valor de la recurrencia.

3. Invariante de bucle (implementación tabular)

Al llenar la tabla en orden por filas/columnas (por ejemplo, \(i\) externo, \(j\) interno), se mantiene el invariante:

Antes de computar \(D(i,j)\), todos los subproblemas necesarios \(D(i-1,j)\), \(D(i,j-1)\), \(D(i-1,j-1)\) ya están correctamente calculados.

Este invariante garantiza que cada celda se calcula sobre valores correctos, preservando la correctitud global.

Implementación de ejemplo

int minDistance(string word1, string word2) {
    //Se inicializa con el menor de los strings para manejo más eficiente de la memoria
    if (word2.size() > word1.size())
        swap(word1, word2);
    //Inicializamos los vectores que guardaran las partes de la tabla que nos interesan
    vector<int> previous_row(word2.size() + 1);
    vector<int> current_row;

    //Casos base de la primera fila
    for (int j = 0; j <= word2.size(); j++)
        previous_row[j] = j;

    int replace_cost, delete_cost, insert_cost;

    for (int i = 1; i <= word1.size(); i++){
        current_row = vector<int>(word2.size() + 1);
        current_row[0] = i;
        for (int j = 1; j <= word2.size(); j++){
        //Costo de hacer un replace
        if (word1[i - 1] == word2[j - 1])
                replace_cost = previous_row[j - 1];
            else
                replace_cost = previous_row[j - 1] + 1;

            delete_cost = previous_row[j] + 1;
            insert_cost = current_row[j - 1] + 1;

            current_row[j] = min(min(replace_cost, delete_cost), insert_cost);
        }
        previous_row = move(current_row);
    }
        return previous_row[word2.size()];
}

Referencias

  • Back To Back SWE (YouTube) — Edit Distance Between 2 Strings - The Levenshtein Distance ("Edit Distance" on LeetCode)
    https://www.youtube.com/watch?v=MiqoA-yF-0M

  • NeetCode Solutions — Edit Distance (Leetcode 72) - Explanation and Code
    https://neetcode.io/solutions/edit-distance

  • V. I. Levenshtein (1966) — Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8), 707–710.

  • Robert A. Wagner & Michael J. Fischer (1974) — The string-to-string correction problem.
    Journal of the ACM (JACM), 21(1), 168–173.