Távolság Damerau és Loewenstein között

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. július 31-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Damerau-Levenshtein távolság (Frederic Damerau és Vladimir Levenshtein tudósokról kapta a nevét ) a két karaktersorozat közötti különbség mértéke, amely a fordításhoz szükséges beillesztések, törlések, cserék és transzponálások (két szomszédos karakter permutációi) minimális száma. egyik húr a másikba. Ez a Levenshtein távolság módosítása : a karakterek transzponálása (permutációja) hozzáadásra került a Levenshtein távolságban meghatározott karakterek beszúrási, törlési és cseréjéhez.

Algoritmus

A két karakterlánc közötti Damerau-Levenshtein távolságot a következő függvény határozza meg : $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{ and }}a_{i}=b_{j-1}{\text{ and }}a_{i-1}=b_{j}\\\ min {\begin{esetek}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{ egyébként,}}\end{cases}}$

ahol az indikátorfüggvény egyenlő nullával at és 1 ellenkező esetben. $1_{{(a_{i}\neq b_{j})}}$ $a_{i}=b_{j}$

Minden rekurzív hívás a következő esetek egyikének felel meg:

$d_{{a,b}}(i-1,j)+1$ egy karakter törlésének felel meg (a - ból b -be ),
$d_{{a,b}}(i,j-1)+1$ megfelel a beszúrásnak (a - tól b -ig ),
$d_{{a,b}}(i-1,j-1)+1_{{(a_{i}\neq b_{j})}}$ egyezés vagy eltérés a karakterek egyezésétől függően,
$d_{{a,b}}(i-2,j-2)+1$ két egymást követő karakter permutációja esetén.

Megvalósítások

pythonbandef damerau_levenshtein_distance ( s1 , s2 ): d = {} lenstr1 = len ( s1 ) lenstr2 = len ( s2 ) i tartományban ( -1 , lenstr1 + 1 ) : _ _ d [( i , - 1 )] = i + 1 j tartományban ( -1 , lenstr2 + 1 ) : _ _ d [( - 1 , j )] = j + 1 i tartományban ( lenstr1 ) : _ j esetén a tartományban ( lenstr2 ): ha s1 [ i ] == s2 [ j ]: költség = 0 mást : költség = 1 d [( i , j )] = min ( d [( i - 1 , j )] + 1 , # törlés d [( i , j - 1 )] + 1 , # beillesztés d [( i - 1 , j - 1 )] + költség , # helyettesítés ) ha i és j és s1 [ i ] == s2 [ j - 1 ] és s1 [ i - 1 ] == s2 [ j ]: d [( i , j )] = min ( d [( i , j )], d [ i - 2 , j - 2 ] + 1 ) # transzponálás d visszatérés [ lenstr1 - 1 , lenstr2 - 1 ]

Adán függvény Damerau_Levenshtein_Distance ( L , R : String ) return Natural is D : array ( L ' First - 1 .. L ' Last , R ' First - 1 .. R ' Last ) of Natural ; kezdődik for I a D ' Range ( 1 ) hurokban D ( I , D ' Első ( 2 )) := I ; end - loop ; az I a D ' Range ( 2 ) hurokban D ( D ' Első ( 1 ), I ) := I ; end - loop ; J esetén az R ' Range ciklusban for I in L ' Range hurok D ( I , J ) := Természetes min _ ( Természetes ' min ( D ( I - 1 , J ), D ( I , J - 1 )) + 1 , D ( I - 1 , J - 1 ) + ( ha L ( I ) = R ( J ) , akkor 0 különben 1 )); ha J > R ' Először , majd I > L ' Először majd R ( J ) = L ( I - 1 ) , majd R ( J - 1 ) = L ( I ) akkor D ( I , J ) := Természetes ' Min ( D ( I , J ), D ( I - 2 , J - 2 ) + 1 ); vége if ; end - loop ; end - loop ; return D ( L ' Last , R ' Last ); end Damerau_Levenshtein_Distance ;

Visual Basic for Applications (VBA) rendszerenPublic Function WeightedDL ( forrás As String , cél As String ) As Double Dim deleteCost As Double Dim insertCost As Double Dim csereköltség Duplán _ Dim swapCost Dupla _ törlésköltség = 1 insertCost = 1 csereköltség = 1 csereköltség = 1 Dim i As Integer Dim j Egész számként Dim k As Integer Ha Len ( forrás ) = 0 Akkor WeightedDL = Len ( cél ) * insertCost kilépési funkció Vége Ha Ha Len ( cél ) = 0 Akkor WeightedDL = Len ( forrás ) * deleteCost kilépési funkció Vége Ha Dim asztal ( ) AsDouble ReDim táblázat ( Len ( forrás ), Len ( cél )) Dim sourceIndexByCharacter ( ) Változatként ReDim sourceIndexByCharacter ( 0 - 1 , 0 - Len ( forrás ) - 1 ) Változatként _ Ha Bal ( forrás , 1 ) <> Bal ( cél , 1 ) Akkor táblázat ( 0 , 0 ) = Alkalmazás . Min ( csereköltség , ( deleteCost + insertCost )) Vége Ha sourceIndexByCharacter ( 0 , 0 ) = Bal ( forrás , 1 ) sourceIndexByCharacter ( 1 , 0 ) = 0 Dim deleteDistance As Double Dim insertDistance As Double Dim matchDistance As Double Ha i = 1 - Len ( forrás ) - 1 deleteDistance = táblázat ( i - 1 , 0 ) + deleteCost insertDistance = (( i + 1 ) * deleteCost ) + insertCost Ha Közép ( forrás , i + 1 , 1 ) = bal ( cél , 1 ) akkor matchDistance = ( i * deleteCost ) + 0 Más matchDistance = ( i * deleteCost ) + csereCost Vége Ha táblázat ( i , 0 ) = Alkalmazás . Min ( Alkalmazás . Min ( deleteDistance , insertDistance ), matchDistance ) Következő j = 1 esetén Lenhez ( cél ) - 1 _ deleteDistance = táblázat ( 0 , j - 1 ) + insertCost insertDistance = (( j + 1 ) * insertCost ) + deleteCost Ha Bal ( forrás , 1 ) = Közép ( cél , j + 1 , 1 ) Akkor matchDistance = ( j * insertCost ) + 0 Más matchDistance = ( j * insertCost ) + csereköltség Vége Ha táblázat ( 0 , j ) = Alkalmazás . Min ( Alkalmazás . Min ( deleteDistance , insertDistance ), matchDistance ) Következő Ha i = 1 - Len ( forrás ) - 1 Dim maxSourceLetterMatchIndex egész számként Ha Közép ( forrás , i + 1 , 1 ) = bal ( cél , 1 ) akkor maxSourceLetterMatchIndex = 0 Más maxSourceLetterMatchIndex = - 1 Vége Ha j = 1 esetén Lenhez ( cél ) - 1 _ Dim kandidātSwapIndex As Integer kandidaatSwapIndex = - 1 Ha k = 0 - UBound ( sourceIndexByCharacter , 2 ) Ha sourceIndexByCharacter ( 0 , k ) = közép ( cél , j + 1 , 1 ) , akkor kandidātSwapIndex = sourceIndexByCharacter ( 1 , k ) Következő Dim jSwap As Integer jSwap = maxSourceLetterMatchIndex deleteDistance = táblázat ( i - 1 , j ) + deleteCost insertDistance = táblázat ( i , j - 1 ) + insertCost matchDistance = táblázat ( i - 1 , j - 1 ) Ha Közép ( forrás , i + 1 , 1 ) <> Közép ( cél , j + 1 , 1 ) Akkor matchDistance = matchDistance + helyettesítési költség Más maxSourceLetterMatchIndex = j Vége Ha Dim swapDistance As Double Ha kandidātSwapIndex < > - 1 És jSwap <> - 1 Akkor Dim iSwap egész számként iSwap = jelöltSwapIndex Dim preSwapCost Ha iSwap = 0 és jSwap = 0 , akkor preSwapCost = 0 Más preSwapCost = táblázat ( Alkalmazás . Max ( 0 , iSwap - 1 ), Alkalmazás . Max ( 0 , jSwap - 1 )) Vége Ha swapDistance = preSwapCost + (( i - iSwap - 1 ) * deleteCost ) + ( ( j - jSwap - 1 ) * insertCost ) + swapCost Más swapDistance = 500 Vége Ha táblázat ( i , j ) = Alkalmazás . Min ( Alkalmazás . Min ( Alkalmazás . Min ( deleteDistance , insertDistance ), _ matchDistance ), swapDistance ) Következő sourceIndexByCharacter ( 0 , i ) = Közép ( forrás , i + 1 , 1 ) sourceIndexByCharacter ( 1 , i ) = i Következő SúlyozottDL = táblázat ( Len ( forrás ) - 1 , Len ( cél ) - 1 ) végfunkció _
A Perl programozási nyelvben modulként Text::Levenshtein::Damerau
A PlPgSQL programozási nyelvben
Kiegészítő modul a MySQL-hez

Lásd még

Levenshtein távolság

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc