Algoritmo de distancia de Levenshtein

La distancia de Levenshtein mide cuántas operaciones básicas (inserción, eliminación o sustitución) son necesarias para transformar una cadena en otra. Es la base de muchas aplicaciones: corrección ortográfica, búsqueda difusa, detección de plagio y sistemas de recomendación.

1. Fundamentos teóricos

• Operaciones permitidas: inserción, eliminación y sustitución (costo 1 cada una).
• Recurrencia clásica:

  lev(i, j) = min(
      lev(i‑1, j)   + 1,      // eliminación
      lev(i,   j‑1) + 1,      // inserción
      lev(i‑1, j‑1) + cost   // sustitución
  )

  donde cost = 0 si s[i‑1] == t[j‑1] y 1 en caso contrario.
• Complejidad: O(m·n) tiempo y O(m·n) espacio (m y n longitudes de las cadenas).

2. Implementación básica en Python

def levenshtein(s: str, t: str) -> int:
    """Calcula la distancia de Levenshtein usando programación dinámica tradicional."""
    m, n = len(s), len(t)
    # Matriz (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # costo de eliminar i caracteres
    for j in range(n + 1):
        dp[0][j] = j  # costo de insertar j caracteres
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s[i - 1] == t[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,      # eliminación
                dp[i][j - 1] + 1,      # inserción
                dp[i - 1][j - 1] + cost  # sustitución
            )
    return dp[m][n]
# Ejemplo de uso
print(levenshtein('kitten', 'sitting'))  # → 3

3. Optimización de espacio (O(min(m,n)))

Al observar que solo se necesita la fila anterior, podemos reducir el consumo de memoria a dos vectores.

def levenshtein_optimized(s: str, t: str) -> int:
    if len(s) < len(t):
        s, t = t, s  # aseguramos que s sea la cadena más larga
    previous = list(range(len(t) + 1))
    for i, sc in enumerate(s, 1):
        current = [i]
        for j, tc in enumerate(t, 1):
            cost = 0 if sc == tc else 1
            current.append(min(
                previous[j] + 1,      # eliminación
                current[-1] + 1,       # inserción
                previous[j - 1] + cost # sustitución
            ))
        previous = current
    return previous[-1]

4. Bibliotecas de alto rendimiento

Para aplicaciones que procesan millones de comparaciones, la implementación escrita en C de la librería python-Levenshtein ofrece mejoras de 10‑30×.

pip install python-Levenshtein

import Levenshtein as lv
print(lv.distance('kitten', 'sitting'))   # → 3
print(lv.ratio('kitten', 'sitting'))      # Similaridad normalizada (0‑1)

5. Comparativa con algoritmos de distancia de cadena

6. Casos de uso reales

1. Autocompletado y búsqueda difusa: Implementar un filtro que sugiere resultados mientras el usuario escribe, tolerando errores tipográficos.
2. Detección de duplicados en bases de datos: Comparar campos de nombre/contacto para consolidar registros.
3. Control de versiones de texto: Calcular la diferencia entre versiones de documentos para generar métricas de similitud.
4. Procesamiento de lenguaje natural (NLP): Normalizar tokens antes de aplicar algoritmos de clustering.

7. Buenas prácticas y optimizaciones avanzadas

• Umbral de corte: Cuando sólo se necesitan coincidencias "cercanas", interrumpir el cálculo si la distancia supera un límite predefinido.
• Indexado de n‑gramas: Pre‑filtrar pares de cadenas usando n‑gramas para reducir comparaciones O(N²) en grandes colecciones.
• Paralelismo: Utilizar multiprocessing.Pool o librerías como joblib para distribuir cálculos en múltiples núcleos.
• Compatibilidad: Las implementaciones mostradas funcionan en Python 3.8+ y son compatibles con PyPy.

8. Depuración y troubleshooting

Algunos problemas comunes y cómo abordarlos:

• Resultados inesperados por espacios o mayúsculas: Normalizar cadenas (.strip().lower()) antes de calcular la distancia.
• Rendimiento bajo con grandes textos: Cambiar a la versión optimizada de python-Levenshtein o emplear la variante de espacio O(min(m,n)).
• Errores de memoria en matrices gigantes: Utilizar la implementación de dos vectores o procesar textos en bloques.

9. Escalabilidad y rendimiento (benchmarks)

En una máquina con 8 vCPU y 16 GB RAM, se midieron 1 000 000 de comparaciones entre cadenas de 20 caracteres:

10. Conclusiones

La distancia de Levenshtein sigue siendo la métrica de referencia para medir la similitud de cadenas por su sencillez y versatilidad. Con las optimizaciones presentadas y el uso de librerías nativas, es posible escalarla a entornos de producción que manejan grandes volúmenes de datos.