Recientemente implementé el algoritmo de distancia Damerau-Levenshtein del pseudocódigo en Wikipedia. No pude encontrar ninguna explicación de cómo funciona exactamente el pseudocódigo y utiliza los nombres de variables completamente poco informativos como DA
, DB
, i1
, y j1
que me dejó rascándome la cabeza.
Aquí está mi implementación en Python: https://gist.github.com/badocelot/5327337
La implementación de Python me ayudó a recorrer el programa y descubrir qué estaba sucediendo, renombrando las variables a nombres más útiles. Estaba suficientemente familiarizado con el enfoque de Wagner-Fischer para calcular la distancia de Levenshtein que tenía un marco de referencia.
A riesgo de ser demasiado largo, así es como entiendo Damerau-Levenshtein:
Las variables misteriosas:
DA
(last_row
en mi código) es un tipo de mapa que contiene la última fila en la que se vio cada elemento; en mi código es un diccionario real de PythonDB
(last_match_col
) contiene la última columna donde la letrab
coincide con la letraa
de la fila actuali1
(last_matching_row
) es el número de fila deDA
la letra actual enb
j1
es solo una copia del valor deDB
/last_match_col
antes de que se actualice potencialmente; en mi código me acabo de mover dondelast_match_col
se actualiza y eliminé esta variable
El costo de transposición:
H[i1][j1] + (i-i1-1) + 1 + (j-j1-1)
está calculando el costo de intercambiar el carácter actual b
con el último carácter b
conocido a
(la última coincidencia), tratando todos los caracteres intermedios como adiciones o eliminaciones.
Componentes del costo:
H[i1][j1]
revierte el costo base al punto en los cálculos antes de la transposición, ya que encontrar una transposición invalida el trabajo previo(i-i1-1)
es la distancia entre la fila actual y la última fila que coincide con el carácter actual, que es el número de eliminaciones que serían necesarias(j-j1-1)
es la distancia entre la columna actual y la última columna con una coincidencia, que es el número de adiciones- El extra
+ 1
es solo el costo de la transposición en sí
Si este análisis es incorrecto, me encantaría saber dónde me equivoqué. Como dije, no pude encontrar ninguna explicación detallada de cómo funciona el algoritmo en línea.
¿Versión mejorada?
Sin embargo, habiendo descubierto eso, me sorprendió que al calcular el costo de las adiciones y eliminaciones entre letras transpuestas parecía defectuoso: una adición y una eliminación es equivalente a una sustitución, lo que esto no está comprobando.
Si todo es correcto, la solución debería ser trivial: el costo de las letras entre las letras transpuestas debería ser la mayor de las adiciones y eliminaciones: convierta tantas sustituciones como sea posible y agregue las adiciones o eliminaciones sobrantes.
Entonces el costo sería:
H[i1][j1] + max((i-i1-1), (j-j1-1)) + 1
Aquí está mi código para esta versión: https://gist.github.com/badocelot/5327427
De algunas pruebas simples, esto parece correcto. Por ejemplo, "abcdef" -> "abcfad" proporciona una distancia de edición de 2 (transponer "d" y "f", cambiar "e" a "a"), mientras que el algoritmo original proporciona una distancia de 3 (las tres últimas las letras son sustituciones, o 1 transposición + 1 adición + 1 eliminación).
Ahora, no puedo ser la primera persona en pensar en esto. Entonces, ¿por qué no lo encontré? ¿No busqué lo suficiente? ¿O hay algún defecto sutil que impide que esto realmente funcione?
fuente
Respuestas:
Tuve que buscar la distancia Damerau-Levenshtein en wikipedia, así que perdóname si esto está mal. Pero parece que solo permite transponer letras adyacentes y no arbitrarias. Entonces su ejemplo "abcdef" -> "abcfad" con transposición de d y f no funciona. Me parece que has modificado la definición del algoritmo y ya no estás calculando la distancia Damerau-Levenshtein.
fuente