Vzdálenost Damerau - Loewenstein

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 31. července 2020; kontroly vyžadují 5 úprav .

Vzdálenost Damerau-Levenshtein (pojmenovaná po vědcích Fredericu Damerauovi a Vladimiru Levenshteinovi ) je mírou rozdílu mezi dvěma řetězci znaků, která je definována jako minimální počet vložení, odstranění, nahrazení a transpozice (permutace dvou sousedních znaků) potřebných k překladu. jeden řetězec do druhého. Jde o modifikaci Levenshteinovy vzdálenosti : k operacím vkládání, mazání a nahrazování znaků definovaných v Levenshteinově vzdálenosti byla přidána operace transpozice (permutace) znaků.

Algoritmus

Vzdálenost Damerau-Levenshtein mezi dvěma strunami a je definována funkcí jako: $A$ $b$ $d_{{a,b}}(|a|,|b|)$

$\qquad d_{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if}}\min(i,j)=0,\\ \min {\begin{cases}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{cases}}&{ \text{ if }}i,j>1{\text{ a }}a_{i}=b_{j-1}{\text{ a }}a_{i-1}=b_{j}\\\ min {\begin{cases}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{cases}}&{\text{ jinak,}}\end{cases}}$

kde je funkce indikátoru rovna nule at a 1 jinak. $1_{{(a_{i}\neq b_{j})}}$ $a_{i}=b_{j}$

Každé rekurzivní volání odpovídá jednomu z případů:

$d_{{a,b}}(i-1,j)+1$ odpovídá smazání znaku (od a do b ),
$d_{{a,b}}(i,j-1)+1$ odpovídá vkládání (od a do b ),
$d_{{a,b}}(i-1,j-1)+1_{{(a_{i}\neq b_{j})}}$ shoda nebo neshoda v závislosti na shodě postav,
$d_{{a,b}}(i-2,j-2)+1$ v případě permutace dvou po sobě jdoucích znaků.

Implementace

v pythonudef damerau_levenshtein_distance ( s1 , s2 ): d = {} lenstr1 = len ( s1 ) lenstr2 = len ( s2 ) pro i v rozsahu ( - 1 , lenstr1 + 1 ): d [( i , -1 ) ] = i + 1 pro j v rozsahu ( - 1 , lenstr2 + 1 ): d [( -1 , j ) ] = j + 1 pro i v dosahu ( lenstr1 ): pro j v rozsahu ( lenstr2 ): pokud s1 [ i ] == s2 [ j ]: cena = 0 jinak : cena = 1 d [( i , j )] = min ( d [( i - 1 , j )] + 1 , # smazání d [( i , j - 1 )] + 1 , # vložení d [( i - 1 , j - 1 )] + náklady , # substituce ) jestliže i a j a s1 [ i ] == s2 [ j - 1 ] a s1 [ i - 1 ] == s2 [ j ]: d [( i , j )] = min ( d [ ( i , j )], d [ i - 2 , j - 2 ] + 1 ) # transpozice návrat d [ lenstr1 - 1 , lenstr2 - 1 ]

Na Adu funkce Damerau_Levenshtein_Distance ( L , R : String ) return Natural je D : pole ( L' První - 1..L'Poslední , R'První - 1..R'Poslední ) z Natural ; _ _ _ _ _ _ _ _ _ _ _ začít pro I ve smyčce D ' Range ( 1 ) . D ( I , D ' První ( 2 )) := I ; konec -smyčka ; pro I ve smyčce D ' Range ( 2 ) . D ( D ' První ( 1 ), I ) := I ; konec -smyčka ; pro J ve smyčce R ' Range pro I ve smyčce L ' Range D ( já , J ) := Přírodní ' Min ( Přirozené ' Min ( D ( I - 1 , J ), D ( I , J - 1 )) + 1 , D ( I - i , J - i ) + ( pokud L ( I ) = R ( J ) pak 0 jinak 1 )); jestliže J > R ' First a pak I > L ' First a pak R ( J ) = L ( I - 1 ) a pak R ( J - 1 ) = L ( I ) pak D ( I , J ) := Přirozený ' Min ( D ( I , J ), D ( I - 2 , J - 2 ) + 1 ); konec if ; konec -smyčka ; konec -smyčka ; return D ( L' Poslední , R'Poslední ) ; _ _ end Damerau_Levenshtein_Distance ;

Ve Visual Basic for Applications (VBA)Veřejná funkce WeightedDL ( zdroj jako řetězec , cíl jako řetězec ) jako dvojitý Dim deleteCost As Double Dim insertCost As Double Dim nahradit Cost As Double Dim swapCost jako dvojnásobek deleteCost = 1 insertCost = 1 nahradit náklady = 1 swapCost = 1 Dim i As Integer Dim j As Integer Dim k As Integer Pokud Len ( zdroj ) = 0 Pak VáženýDL = Délka ( cíl ) * vložitCena výstupní funkce End If Pokud Len ( cíl ) = 0 Pak WeightedDL = Délka ( zdroj ) * deleteCost výstupní funkce End If Stmívací stůl ( ) AsDouble Tabulka ReDim ( Len ( zdroj ), Len ( cíl )) Dim sourceIndexByCharacter () Jako varianta ReDim sourceIndexByCharacter ( 0 až 1 , 0 až Len ( zdroj ) - 1 ) jako varianta If Left ( source , 1 ) <> Left ( target , 1 ) Then tabulka ( 0 , 0 ) = Aplikace . Min ( nahraditCost , ( deleteCost + insertCost )) End If sourceIndexByCharacter ( 0 , 0 ) = vlevo ( zdroj , 1 ) sourceIndexByCharacter ( 1 , 0 ) = 0 Dim deleteDistance As Double Dim insertDistance As Double Dim matchDistance As Double Pro i = 1 To Len ( zdroj ) - 1 deleteDistance = tabulka ( i - 1 , 0 ) + deleteCost insertDistance = (( i + 1 ) * deleteCost ) + insertCost Pokud Střed ( zdroj , i + 1 , 1 ) = vlevo ( cíl , 1 ) Pak matchDistance = ( i * deleteCost ) + 0 Jiný matchDistance = ( i * deleteCost ) + nahraditCost End If tabulka ( i , 0 ) = Aplikace . Min ( Aplikace . Min ( deleteDistance , insertDistance ), matchDistance ) další Pro j = 1 To Len ( cíl ) - 1 deleteDistance = tabulka ( 0 , j - 1 ) + insertCost insertDistance = (( j + 1 ) * insertCost ) + deleteCost Pokud vlevo ( zdroj , 1 ) = střed ( cíl , j + 1 , 1 ) Potom matchDistance = ( j * insertCost ) + 0 Jiný matchDistance = ( j * insertCost ) + nahraditCost End If tabulka ( 0 , j ) = Aplikace . Min ( Aplikace . Min ( deleteDistance , insertDistance ), matchDistance ) další Pro i = 1 To Len ( zdroj ) - 1 Dim maxSourceLetterMatchIndex jako celé číslo Pokud Střed ( zdroj , i + 1 , 1 ) = vlevo ( cíl , 1 ) Pak maxSourceLetterMatchIndex = 0 Jiný maxSourceLetterMatchIndex = - 1 End If Pro j = 1 To Len ( cíl ) - 1 Ztlumit kandidátSwapIndex jako celé číslo kandidátSwapIndex = - 1 Pro k = 0 až UBound ( sourceIndexByCharacter , 2 ) If sourceIndexByCharacter ( 0 , k ) = Mid ( target , j + 1 , 1 ) Then kandidátSwapIndex = sourceIndexByCharacter ( 1 , k ) další Dim jSwap As Integer jSwap = maxSourceLetterMatchIndex deleteDistance = tabulka ( i - 1 , j ) + deleteCost insertDistance = tabulka ( i , j - 1 ) + insertCost matchDistance = tabulka ( i - 1 , j - 1 ) If Mid ( source , i + 1 , 1 ) <> Mid ( target , j + 1 , 1 ) Then matchDistance = matchDistance + nahraditCost Jiný maxSourceLetterMatchIndex = j End If Dim swapDistance As Double Pokud kandidátSwapIndex <> - 1 A jSwap <> - 1 Pak Dim iSwap jako celé číslo iSwap = kandidátSwapIndex Ztlumit cenu před výměnou Pokud iSwap = 0 a jSwap = 0 Pak cena před výměnou = 0 Jiný preSwapCost = tabulka ( Aplikace . Max ( 0 , iSwap - 1 ), Aplikace . Max ( 0 , jSwap - 1 )) End If swapDistance = preswapCost + (( i - iSwap - 1 ) * deleteCost ) + (( j - jSwap - 1 ) * insertCost ) + swapCost Jiný swapDistance = 500 End If tabulka ( i , j ) = Aplikace . Min ( Aplikace . Min ( Aplikace . Min . ( smazatVzdálenost , vložitVzdálenost ), _ matchDistance ), swapDistance ) další sourceIndexByCharacter ( 0 , i ) = Mid ( zdroj , i + 1 , 1 ) sourceIndexByCharacter ( 1 , i ) = i další VáženýDL = tabulka ( délka ( zdroj ) - 1 , délka ( cíl ) - 1 ) koncová funkce
V programovacím jazyce Perl jako modul Text::Levenshtein::Damerau
V programovacím jazyce PlPgSQL
Přídavný modul pro MySQL

Viz také

Levenshteinská vzdálenost

Struny
Míry podobnosti řetězců	Vzdálenost Damerau - Loewenstein Levenshteinská vzdálenost Hammingova vzdálenost Podobnost Jaro-Winkler
Hledání podřetězců	Boyer-Mooreův algoritmus Algoritmus Boyer-Moore-Horspool Knuth-Morris-Prattův algoritmus Rabin-Karpův algoritmus funkce předpony Z-funkce Algoritmus Aho - Korasik
palindromy	palindromový strom Manažerův algoritmus
Sekvenční zarovnání	Algoritmus Needleman-Wunsha Smith-Watermanův algoritmus
Struktury přípon	Pole přípon Přípona automat příponový strom předponový strom
jiný	rozebrat Shoda vzorů Největší společná podsekvence Největší společný podřetězec