Calculadora de Similitud de Cadenas

La distancia de Levenshtein (distancia de edición) es el número mínimo de ediciones de un solo carácter necesarias para transformar una cadena en otra. Las tres operaciones permitidas son: inserción (agregar un carácter), eliminación (quitar un carácter) y sustitución (reemplazar un carácter por otro). Ejemplo: «kitten» → «sitting» requiere 3 operaciones: k→s, e→i, +g. Recibe su nombre de Vladimir Levenshtein, quien describió este algoritmo en 1965. Aplicaciones: corrección ortográfica, alineación de secuencias de ADN, procesamiento de lenguaje natural, coincidencia difusa de cadenas.

Similitud % = (1 − distanciaEdición / max(largo1, largo2)) × 100. Esto normaliza la distancia en relación con la cadena más larga. Ejemplo: distancia = 2, longitud máxima = 8 → similitud = (1 − 2/8) × 100 = 75%. Una distancia de 0 significa cadenas idénticas (100% similares). Una distancia igual a la longitud máxima significa cadenas completamente diferentes (0% similares). Otras métricas de similitud incluyen Jaro-Winkler (pondera más la coincidencia de caracteres iniciales) y la similitud coseno (para comparación basada en tokens).

Damerau-Levenshtein extiende Levenshtein agregando una cuarta operación: transposición (intercambiar dos caracteres adyacentes). Ejemplo: «ab» → «ba» tiene distancia Levenshtein 2 (eliminar + insertar), pero distancia Damerau-Levenshtein 1 (una transposición). Esto es importante para la corrección ortográfica, ya que muchos errores tipográficos son transposiciones («teh» → «the»). Existen dos variantes: restringida (solo transposiciones adyacentes) y no restringida (cualquier transposición). Esta herramienta usa Levenshtein estándar (sin transposiciones).

Correctores ortográficos: sugieren palabras con baja distancia de edición respecto a la palabra mal escrita. Secuenciación de ADN: alinea secuencias de nucleótidos para encontrar mutaciones e inserciones. Control de versiones: git diff usa algoritmos de distancia de edición para mostrar cambios a nivel de línea. Procesamiento de lenguaje natural: desambiguación de entidades nombradas, resolución de correferencia. Detección de fraude: detecta variaciones de nombres (typosquatting, fraude de identidad). Vinculación de registros: hace coincidir registros entre bases de datos cuando los nombres o direcciones varían ligeramente. Corrección de OCR: corrige errores de reconocimiento óptico de caracteres.

El algoritmo Wagner-Fischer calcula la distancia de Levenshtein usando programación dinámica con tiempo O(m×n) y espacio O(m×n), donde m y n son las longitudes de las cadenas. Construye una matriz donde la celda [i][j] = distancia de edición entre los primeros i caracteres de la cadena 1 y los primeros j caracteres de la cadena 2. Casos base: fila 0 = 0..n (eliminar todos los caracteres de s1), columna 0 = 0..m (insertar todos los caracteres de s2). Recurrencia: si s1[i] == s2[j], la celda = diagonal anterior; de lo contrario, celda = 1 + min(izquierda, arriba, diagonal). El espacio puede optimizarse a O(min(m,n)) usando dos filas.