Distancia Damerau–Levenshtein

La distancia de Damerau–Levenshtein es una métrica clásica de edición que cuenta cuántas operaciones de un solo carácter transforman una cadena en otra cuando las operaciones permitidas son inserción, borrado, sustitución y transposición de dos caracteres adyacentes. Esa última operación es lo que la distingue de la distancia de Levenshtein simple y la hace especialmente útil ante typos reales: las personas suelen intercambiar dos teclas vecinas (form frente a from, teh frente a the) y eso debe costar un paso, no dos sustituciones. Esta capacidad implementa la forma Optimal String Alignment de la distancia con una tabla pura de programación dinámica, de modo que cada par de entradas produce el mismo entero en cualquier runtime. Usted envía dos textos y un indicador opcional de sensibilidad a mayúsculas; recibe la distancia, ambas longitudes, una similitud normalizada entre cero y uno, y un booleano identical.

Qué mide Damerau–Levenshtein y cómo difiere de Levenshtein simple

La distancia de edición pregunta cuántos cambios unitarios hacen falta para reescribir una cadena origen como una cadena destino. La Levenshtein clásica permite tres operaciones unitarias: insertar un carácter, borrar un carácter o sustituir un carácter por otro. Cada una cuesta uno.

La extensión de Damerau añade una cuarta operación: intercambiar dos caracteres adyacentes por un solo coste unitario. Esa extensión encaja con cómo se escriben mal las palabras en un teclado. Por ejemplo, las cadenas ab y ba difieren en una transposición adyacente bajo Damerau–Levenshtein y en dos sustituciones bajo Levenshtein simple.

Kitten frente a sitting sigue costando tres (como en el ejemplo de libro de texto de Levenshtein) porque el camino más barato usa sustituciones y una inserción, no un solo intercambio. OSA es la forma que la mayoría de bibliotecas etiquetan como Damerau–Levenshtein para corrección de typos; prohíbe aplicar dos transposiciones solapadas sobre la misma subcadena, lo que mantiene la métrica simple y O(n·m) en tiempo y espacio.

Las cadenas vacías son válidas: la distancia desde la cadena vacía a cualquier cadena es la longitud de esa cadena, y la distancia entre dos vacías es cero. Las cadenas idénticas siempre dan distancia cero y similitud uno, también tras el plegado opcional de mayúsculas.

Dónde resulta útil esta distancia

Las herramientas de búsqueda de producto e inventario usan la distancia de edición con transposiciones para ordenar SKU y marcas casi coincidentes antes de recurrir a modelos semánticos más lentos. Las tuberías de CRM y deduplicación marcan filas candidatas a duplicado cuando la distancia es como máximo uno o dos y la similitud supera un umbral fijo, captando letras intercambiadas que la igualdad simple o incluso Levenshtein pura infravalorarían.

Las demos de corrector ortográfico y los ejercicios de aula necesitan un oráculo determinista que marque form frente a from como distancia uno y cobre una tarifa fija transparente en lugar de coste por tokens. La entrada inválida no consume saldo.

Combine la distancia entera con su propia política de umbral—acepte distancia cero solo para claves exactas, distancia uno para corrección agresiva de typos, similitud por encima de 0.8 para pistas de fusión suave—y obtendrá un bloque auditable de coincidencia difusa sin montar un motor de búsqueda completo ni un stack de PLN propio.