Distancia de Damerau a Loewenstein

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 31 de julio de 2020; las comprobaciones requieren 5 ediciones .

La distancia Damerau-Levenshtein (llamada así por los científicos Frederic Damerau y Vladimir Levenshtein ) es una medida de la diferencia entre dos cadenas de caracteres, definida como el número mínimo de inserciones, eliminaciones, reemplazos y transposiciones (permutaciones de dos caracteres adyacentes) necesarios para traducir una cuerda en otra. Se trata de una modificación de la distancia de Levenshtein : a las operaciones de inserción, borrado y sustitución de caracteres definidas en la distancia de Levenshtein se ha añadido la operación de transposición (permutación) de caracteres.

Algoritmo

La distancia Damerau-Levenshtein entre dos cuerdas y está definida por la función como: $a$ $b$ $d_{{a,b}}(|a|,|b|)$

$\qquad d_{a,b}(i,j)={\begin{casos}\max(i,j)&{\text{si}}\min(i,j)=0,\\ \min {\begin{casos}d_{a,b}(i-1,j)+1\\d_{a,b}(i,j-1)+1\\d_{a,b}(i -1,j-1)+1_{(a_{i}\neq b_{j})}\\d_{a,b}(i-2,j-2)+1\end{casos}}&{ \text{ si }}i,j>1{\text{ y }}a_{i}=b_{j-1}{\text{ y }}a_{i-1}=b_{j}\\\ min {\begin{casos}d_{a,b}(i-1,j)+1\\d_{a,b}(i,j-1)+1\\d_{a,b}(i- 1,j-1)+1_{(a_{i}\neq b_{j})}\end{casos}}&{\text{ de lo contrario,}}\end{casos}}$

donde la función indicadora es igual a cero en y 1 en caso contrario. $1_{{(a_{i}\neq b_{j})}}$ $a_{i}=b_{j}$

Cada llamada recursiva corresponde a uno de los casos:

$d_{{a,b}}(i-1,j)+1$ corresponde a borrar un caracter (de a a b ),
$d_{{a,b}}(i,j-1)+1$ coincide con la inserción (de a a b ),
$d_{{a,b}}(i-1,j-1)+1_{{(a_{i}\neq b_{j})}}$ coincidencia o no coincidencia, dependiendo de la coincidencia de los caracteres,
$d_{{a,b}}(i-2,j-2)+1$ en caso de permutación de dos caracteres consecutivos.

Implementaciones

en pitóndef damerau_levenshtein_distance ( s1 , s2 ): re = {} lenstr1 = len ( s1 ) lenstr2 = len ( s2 ) para i en rango ( - 1 , lenstr1 + 1 ): re [( yo , - 1 )] = yo + 1 para j en rango ( - 1 , lenstr2 + 1 ): re [( - 1 , j )] = j + 1 para i en rango ( lenstr1 ): para j en rango ( lenstr2 ): si s1 [ yo ] == s2 [ j ]: costo = 0 más : costo = 1 re [( yo , j )] = min ( d [( i - 1 , j )] + 1 , # eliminación d [( i , j - 1 )] + 1 , # inserción d [( i - 1 , j - 1 )] + costo , # sustitución ) si i y j y s1 [ i ] == s2 [ j - 1 ] y s1 [ i - 1 ] == s2 [ j ]: d [( i , j )] = min ( d [( i , j )], d [ i - 2 , j - 2 ] + 1 ) # transposición volver d [ lenstr1 - 1 , lenstr2 - 1 ]

en ada función Damerau_Levenshtein_Distance ( L , R : String ) return Natural es D : array ( L ' Primero - 1 .. L ' Último , R ' Primero - 1 .. R ' Último ) de Natural ; empezar for I in D ' Range ( 1 ) bucle D ( I , D ' Primero ( 2 )) := I ; bucle final ; for I in D ' Range ( 2 ) bucle D ( D ' Primero ( 1 ), I ) := I ; bucle final ; para J en R ' Bucle de rango para I en bucle de rango L ' D ( yo , j ) := Mínimo natural _ ( Natural ' Min ( D ( I - 1 , J ), D ( I , J - 1 )) + 1 , D ( I - 1 , J - 1 ) + ( si L ( I ) = R ( J ) entonces 0 sino 1 )); si J > R ' Primero y luego I > L ' Primero y luego R ( J ) = L ( I - 1 ) y luego R ( J - 1 ) = L ( I ) después D ( I , J ) := Natural ' Min ( D ( I , J ), D ( I - 2 , J - 2 ) + 1 ); terminar si ; bucle final ; bucle final ; return D ( L ' Último , R'Último ) ; _ final Damerau_Levenshtein_Distance ;

En Visual Basic para Aplicaciones (VBA) Función pública WeightedDL ( origen como cadena , destino como cadena ) como doble Dim deleteCost As Double Dim insertCost As Double Dim replaceCost As Double Dim swapCoste como el doble eliminarCoste = 1 insertarCoste = 1 reemplazarCoste = 1 costo de intercambio = 1 Dim i como entero Dim j como entero Dim k como entero Si Len ( fuente ) = 0 Entonces WeightedDL = Len ( objetivo ) * insertCost función de salida terminar si Si Len ( objetivo ) = 0 Entonces WeightedDL = Len ( fuente ) * deleteCost función de salida terminar si Dim table ( ) AsDouble Tabla ReDim ( Len ( fuente ), Len ( destino )) Dim sourceIndexByCharacter () como variante ReDim sourceIndexByCharacter ( 0 a 1 , 0 a Len ( fuente ) - 1 ) como variante Si Izquierda ( fuente , 1 ) <> Izquierda ( destino , 1 ) Entonces tabla ( 0 , 0 ) = Aplicación . Min ( reemplazarCoste , ( eliminarCoste + insertarCoste )) terminar si sourceIndexByCharacter ( 0 , 0 ) = Izquierda ( fuente , 1 ) sourceIndexByCharacter ( 1 , 0 ) = 0 Dim deleteDistance como doble Dim insertDistance As Double Dim MatchDistance As Double Para i = 1 Para Len ( fuente ) - 1 eliminarDistancia = tabla ( i - 1 , 0 ) + eliminarCoste insertarDistancia = (( i + 1 ) * eliminarCoste ) + insertarCoste Si Medio ( fuente , i + 1 , 1 ) = Izquierda ( objetivo , 1 ) Entonces MatchDistance = ( i * deleteCost ) + 0 Más MatchDistance = ( i * deleteCost ) + replaceCost terminar si tabla ( i , 0 ) = Aplicación . Min ( Aplicación . Min ( eliminar Distancia , insertar Distancia ), igualar Distancia ) próximo Para j = 1 Para Len ( objetivo ) - 1 eliminarDistancia = tabla ( 0 , j - 1 ) + insertarCoste insertarDistancia = (( j + 1 ) * insertarCoste ) + eliminarCoste Si Izquierda ( fuente , 1 ) = Medio ( destino , j + 1 , 1 ) Entonces MatchDistance = ( j * insertCost ) + 0 Más MatchDistance = ( j * insertCost ) + replaceCost terminar si tabla ( 0 , j ) = Aplicación . Min ( Aplicación . Min ( eliminar Distancia , insertar Distancia ), igualar Distancia ) próximo Para i = 1 Para Len ( fuente ) - 1 Dim maxSourceLetterMatchIndex como entero Si Medio ( fuente , i + 1 , 1 ) = Izquierda ( objetivo , 1 ) Entonces maxSourceLetterMatchIndex = 0 Más maxSourceLetterMatchIndex = - 1 terminar si Para j = 1 Para Len ( objetivo ) - 1 Dim candidatoSwapIndex como entero CandidatoSwapIndex = - 1 Para k = 0 a UBound ( sourceIndexByCharacter , 2 ) Si sourceIndexByCharacter ( 0 , k ) = Mid ( target , j + 1 , 1 ) Entonces candidatoSwapIndex = sourceIndexByCharacter ( 1 , k ) próximo Dim jSwap como entero jSwap = maxSourceLetterMatchIndex eliminarDistancia = tabla ( i - 1 , j ) + eliminarCoste insertarDistancia = tabla ( i , j - 1 ) + insertarCoste MatchDistance = tabla ( i - 1 , j - 1 ) Si Mid ( fuente , i + 1 , 1 ) <> Mid ( objetivo , j + 1 , 1 ) Entonces igualarDistancia = igualarDistancia + reemplazarCoste Más maxSourceLetterMatchIndex = j terminar si Dim swapDistance como doble Si candidatoSwapIndex <> - 1 y jSwap <> - 1 Entonces Dim iSwap como entero iSwap = índice de intercambio de candidatos Dim preSwapCost Si iSwap = 0 y jSwap = 0 Entonces costo preintercambio = 0 Más preSwapCost = tabla ( Aplicación . Max ( 0 , iSwap - 1 ), Aplicación . Max ( 0 , jSwap - 1 )) terminar si swapDistance = preSwapCost + (( i - iSwap - 1 ) * deleteCost ) + (( j - jSwap - 1 ) * insertCost ) + swapCost Más distancia de intercambio = 500 terminar si tabla ( i , j ) = Aplicación . Min ( Aplicación . Min ( Aplicación . Min ( eliminarDistancia , insertarDistancia ), _ distancia de coincidencia ), distancia de intercambio ) próximo sourceIndexByCharacter ( 0 , i ) = Mid ( fuente , i + 1 , 1 ) sourceIndexByCharacter ( 1 , i ) = i próximo DL ponderado = tabla ( Long ( origen ) - 1 , Len ( destino ) - 1 ) función final
En el lenguaje de programación Perl como módulo Text::Levenshtein::Damerau
En el lenguaje de programación PlPgSQL
Módulo adicional para MySQL

Véase también

distancia Levenstein

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitud de Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común