domingo 22 septiembre 2024

Cómo Implementar la Distancia de Levenshtein en Python

La distancia de Levenshtein es una métrica de similitud que indica cuántas modificaciones (inserciones, eliminaciones o sustituciones) se requieren para convertir una cadena de caracteres en otra.

La Distancia de Levenshtein es una medida que determina cuántas operaciones mínimas son necesarias para transformar una cadena de caracteres en otra. Las operaciones permitidas incluyen:

1. Inserciones (agregar un carácter),

2. Eliminaciones (eliminar un carácter),

3. Sustituciones (reemplazar un carácter por otro).

Este concepto es crucial en áreas como la corrección ortográfica, reconocimiento de patrones, bioinformática y análisis de ADN, así como en aplicaciones de búsqueda avanzada de texto.

En este artículo, vamos a explorar cómo implementar este algoritmo desde cero en Python, así como su uso en bibliotecas populares como difflib y python-Levenshtein.

¿Qué es la Distancia de Levenshtein?

La distancia de Levenshtein es una métrica de similitud que indica cuántas modificaciones (inserciones, eliminaciones o sustituciones) se requieren para convertir una cadena de caracteres en otra. Por ejemplo, para convertir la palabra "gato" en "pato", se requiere solo una operación: la sustitución de "g" por "p", por lo que la distancia de Levenshtein entre "gato" y "pato" es 1.

Matemáticamente, si tenemos dos cadenas $a$ y $b$, la distancia de Levenshtein entre ellas, denotada como $D(a, b)$, se define como el número mínimo de operaciones necesarias para transformar $a$ en $b$.

Fórmula Matemática de la Distancia de Levenshtein

La distancia de Levenshtein entre dos cadenas $ a $ y $ b $ de longitudes $ m $ y $ n $, respectivamente, se define recursivamente como:

$$D(i, j) = \begin{cases} \max(i, j) & \text{si } \min(i, j) = 0, \\ \min \begin{cases} D(i-1, j) + 1 \\ D(i, j-1) + 1 \\ D(i-1, j-1) + \text{cost}(a_i, b_j) \end{cases} & \text{si } i, j > 0 \end{cases}$$

Donde:

$ D(i, j) $ es la distancia de Levenshtein entre los primeros $ i $ caracteres de la cadena $ a $ y los primeros $ j $ caracteres de la cadena $ b $.
$ \text{cost}(a_i, b_j) = 0 $ si los caracteres $ a_i $ y $ b_j $ son iguales, y 1 si son diferentes.
Las operaciones permitidas son:
Inserción: $ D(i, j-1) + 1 $, que añade un carácter a la cadena.
Eliminación: $ D(i-1, j) + 1 $, que elimina un carácter de la cadena.
Sustitución: $ D(i-1, j-1) + \text{cost}(a_i, b_j) $, que cambia un carácter por otro.

Explicación de la Fórmula:

1. Caso Base: Cuando $ i = 0 $ o $ j = 0 $, es decir, cuando una de las dos cadenas es vacía, la distancia es igual a la longitud de la otra cadena (el número de inserciones o eliminaciones necesarias para vaciar o completar la cadena).

$$D(i, 0) = i \quad \text{y} \quad D(0, j) = j$$

2. Caso Recursivo: Cuando $ i > 0 $ y $ j > 0 $, se elige el valor mínimo entre:

El costo de eliminar un carácter de $ a $ (o añadirlo a $ b $).
El costo de insertar un carácter en $ a $ (o eliminarlo de $ b $).
El costo de sustituir un carácter (solo si son diferentes).

De esta manera, el algoritmo llena una matriz de tamaño $ (m + 1) \times (n + 1) $, donde la última celda $ D(m, n) $ contiene el valor final de la distancia de Levenshtein.

Ejemplo Visual:

Si queremos convertir "gato" en "pato", la matriz de distancia de Levenshtein se verá así:

|   |   | p | a | t | o |
|---|---|---|---|---|---|
|   | 0 | 1 | 2 | 3 | 4 |
| g | 1 | 1 | 2 | 3 | 4 |
| a | 2 | 2 | 1 | 2 | 3 |
| t | 3 | 3 | 2 | 1 | 2 |
| o | 4 | 4 | 3 | 2 | 1 |

El valor final $ D(4, 4) = 1 $ nos indica que solo se requiere una operación (la sustitución de "g" por "p") para convertir "gato" en "pato".

Algoritmo de Distancia de Levenshtein

El algoritmo de Levenshtein se basa en la construcción de una tabla o matriz de tamaño $(m + 1) \times (n + 1)$, donde $m$ y $n$ son las longitudes de las cadenas $a$ y $b$, respectivamente. La idea es llenar esta matriz para calcular la distancia paso a paso, considerando las operaciones posibles en cada carácter.

Pasos para Implementar la Distancia de Levenshtein

1. Crear una matriz de tamaño $(m+1) \times (n+1)$.

2. Inicializar la primera fila y la primera columna, que representan las transformaciones entre una cadena vacía y una cadena completa.

3. Recorrer la matriz, llenando cada celda con el valor mínimo posible basado en las operaciones permitidas: inserción, eliminación o sustitución.

4. El valor en la última celda de la matriz es la distancia de Levenshtein.

Código de Ejemplo en Python

A continuación, se muestra una implementación en Python del algoritmo de distancia de Levenshtein.

def distancia_levenshtein(a, b):
    # Longitud de las cadenas
    m, n = len(a), len(b)

    # Crear una matriz de tamaño (m+1) x (n+1)
    matriz = [[0] * (n + 1) for _ in range(m + 1)]

    # Inicializar la primera fila y la primera columna
    for i in range(m + 1):
        matriz[i][0] = i
    for j in range(n + 1):
        matriz[0][j] = j

    # Llenar la matriz
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            costo = 0 if a[i - 1] == b[j - 1] else 1
            matriz[i][j] = min(
                matriz[i - 1][j] + 1,    # Eliminación
                matriz[i][j - 1] + 1,    # Inserción
                matriz[i - 1][j - 1] + costo  # Sustitución
            )

    # El valor en la última celda es la distancia de Levenshtein
    return matriz[m][n]

# Ejemplo de uso
cadena1 = "gato"
cadena2 = "pato"
print(f"La distancia de Levenshtein entre '{cadena1}' y '{cadena2}' es: {distancia_levenshtein(cadena1, cadena2)}")

Explicación del Código

1. Inicialización de la matriz: Creamos una matriz de tamaño $(m+1) \times (n+1)$, donde m y n son las longitudes de las dos cadenas.

2. Inicialización de la primera fila y columna: Se llena la primera fila y columna con los valores del 0 a m y del 0 a n, respectivamente, que representan las operaciones necesarias para convertir una cadena vacía en otra.

3. Cálculo de distancias: Para cada celda de la matriz, se calcula el valor mínimo entre las operaciones posibles: inserción, eliminación o sustitución.

4. Resultado final: El valor de la última celda de la matriz contiene la distancia de Levenshtein.

Optimización de Espacio

El algoritmo que hemos implementado tiene una complejidad de tiempo de $O(m \times n)$ y una complejidad de espacio de $O(m \times n)$. Sin embargo, como solo necesitamos las dos últimas filas de la matriz en cualquier momento, es posible reducir el uso de espacio a $O(\min(m, n))$.

Aquí está la versión optimizada en cuanto a espacio:

def distancia_levenshtein_optimizada(a, b):
    if len(a) < len(b):
        a, b = b, a  # Intercambiar para reducir el uso de espacio

    # Inicializar las filas
    fila_anterior = range(len(b) + 1)
    
    for i, char_a in enumerate(a, 1):
        fila_actual = [i]
        for j, char_b in enumerate(b, 1):
            costo = 0 if char_a == char_b else 1
            fila_actual.append(min(
                fila_actual[j - 1] + 1,  # Inserción
                fila_anterior[j] + 1,    # Eliminación
                fila_anterior[j - 1] + costo  # Sustitución
            ))
        fila_anterior = fila_actual
    
    return fila_anterior[-1]

# Ejemplo de uso
cadena1 = "gato"
cadena2 = "pato"
print(f"La distancia de Levenshtein optimizada entre '{cadena1}' y '{cadena2}' es: {distancia_levenshtein_optimizada(cadena1, cadena2)}")

Usando Bibliotecas Externas para la Distancia de Levenshtein

Usando `difflib` en Python

El módulo difflib de Python es útil para encontrar similitudes entre secuencias, aunque no implementa directamente la distancia de Levenshtein, puede ser útil para casos más generales de comparación de secuencias.

import difflib

def similitud_difflib(a, b):
    secuencia = difflib.SequenceMatcher(None, a, b)
    return secuencia.ratio()

# Ejemplo de uso
cadena1 = "gato"
cadena2 = "pato"
print(f"Similitud entre '{cadena1}' y '{cadena2}' usando difflib: {similitud_difflib(cadena1, cadena2)}")

Usando `python-Levenshtein`

Si prefieres una solución optimizada y con mejor rendimiento, puedes utilizar la biblioteca python-Levenshtein, que está escrita en C y es significativamente más rápida que la implementación en Python puro.

Primero, instala la biblioteca usando:

pip install python-Levenshtein

Y luego, puedes calcular la distancia de Levenshtein de manera simple:

import Levenshtein

cadena1 = "gato"
cadena2 = "pato"
distancia = Levenshtein.distance(cadena1, cadena2)
print(f"La distancia de Levenshtein entre '{cadena1}' y '{cadena2}' usando python-Levenshtein es: {distancia}")

Conclusión

La Distancia de Levenshtein es una herramienta poderosa para medir la similitud entre cadenas de caracteres. Hemos visto cómo implementarla en Python, tanto de forma básica como optimizada. Además, exploramos alternativas en bibliotecas como difflib y python-Levenshtein para mejorar el rendimiento en casos de uso más exigentes.

Este algoritmo tiene aplicaciones en una amplia variedad de campos, desde la corrección automática de textos hasta la comparación de secuencias en bioinformática. Implementarlo en Python te permite personalizarlo según tus necesidades específicas. ¡Atrévete a probarlo en tus propios proyectos!

Etiquetas:

matematicas python

Creado por:

Jorge García

Fullstack developer