Avstånd från Damerau till Loewenstein

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 juli 2020; kontroller kräver 5 redigeringar .

Avståndet Damerau-Levenshtein (uppkallat efter forskarna Frederic Damerau och Vladimir Levenshtein ) är ett mått på skillnaden mellan två teckensträngar, definierat som det minsta antalet infogningar, raderingar, ersättningar och transpositioner (permutationer av två intilliggande tecken) som krävs för att översätta en sträng i en annan. Det är en modifiering av Levenshtein-avståndet : operationen för transponering (permutation) av tecken har lagts till operationerna för att infoga, ta bort och ersätta tecken definierade i Levenshtein-avståndet.

Algoritm

Damerau-Levenshtein-avståndet mellan två strängar och definieras av funktionen som: $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{fall}}&{ \text{ if }}i,j>1{\text{ och }}a_{i}=b_{j-1}{\text{ och }}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{ annars,}}\end{cases}}$

där är indikatorfunktionen lika med noll vid och 1 annars. $1_{{(a_{i}\neq b_{j})}}$ $a_{i}=b_{j}$

Varje rekursivt anrop motsvarar ett av fallen:

$d_{{a,b}}(i-1,j)+1$ motsvarar att radera ett tecken (från a till b ),
$d_{{a,b}}(i,j-1)+1$ matchar infogning (från a till b ),
$d_{{a,b}}(i-1,j-1)+1_{{(a_{i}\neq b_{j})}}$ matchar eller inte matchar, beroende på matchningen av karaktärerna,
$d_{{a,b}}(i-2,j-2)+1$ vid permutation av två på varandra följande tecken.

Implementeringar

i pythondef damerau_levenshtein_distance ( s1 , s2 ): d = {} lenstr1 = len ( s1 ) lenstr2 = len ( s2 ) för i inom intervallet ( - 1 , lensstr1 + 1 ): d [( i , -1 ) ] = i + 1 för j inom intervallet ( - 1 , lensstr2 + 1 ): d [( -1 , j ) ] = j + 1 för i inom räckvidd ( lenstr1 ): för j i intervallet ( lenstr2 ): om s1 [ i ] == s2 [ j ]: kostnad = 0 annat : kostnad = 1 d [( i , j )] = min ( d [( i - 1 , j )] + 1 , # radering d [( i , j - 1 )] + 1 , # insättning d [( i - 1 , j - 1 )] + kostnad , # substitution ) om i och j och s1 [ i ] == s2 [ j - 1 ] och s1 [ i - 1 ] == s2 [ j ]: d [( i , j )] = min ( d [( i , j )], d [ i - 2 , j - 2 ] + 1 ) # transponering return d [ lenstr1 - 1 , lenstr2 - 1 ]

På Ada funktion Damerau_Levenshtein_Distance ( L , R : String ) retur Naturlig är D : array ( L ' First - 1 .. L ' Last , R ' First - 1 .. R ' Last ) av Natural ; Börja för I in D ' Range ( 1 ) loop D ( I , D ' First ( 2 )) := I ; end -loop ; för I in D ' Range ( 2 ) loop D ( D ' First ( 1 ), I ) := I ; end -loop ; för J in R ' Range loop för I i L ' Range loop D ( I , J ) := Naturlig ' Min ( Natural ' Min ( D ( I - 1 , J ), D ( I , J - 1 )) + 1 , D ( I - 1 , J - 1 ) + ( om L ( I ) = R ( J ) så är O annars 1 )); om J > R ' Först och sedan I > L ' Först och sedan R ( J ) = L ( I - 1 ) och sedan R ( J - 1 ) = L ( I ) sedan D ( I , J ) := Naturligt ' Min ( D ( I , J ), D ( I - 2 , J - 2 ) + 1 ); sluta om ; end -loop ; end -loop ; return D ( L ' Last , R ' Last ); slut Damerau_Levenshtein_Distance ;

Om Visual Basic for Applications (VBA)Public Function WeightedDL ( källa som sträng , mål som sträng ) som dubbel Dimma deleteCost As Double Dim insertCost As Double Dim replaceCost As Double Dim swapCost As Double raderaKostnad = 1 infoga Kostnad = 1 utbyteskostnad = 1 byteskostnad = 1 Dim i As Integer Dim j Som heltal Dim k Som heltal Om Len ( källa ) = 0 Då WeightedDL = Len ( target ) * insertCost utgångsfunktion _ Sluta om Om Len ( mål ) = 0 Då WeightedDL = Len ( källa ) * deleteCost utgångsfunktion _ Sluta om Dim bord ( ) AsDouble ReDim- tabell ( Len ( källa ), Len ( mål )) Dim sourceIndexByCharacter () Som variant ReDim sourceIndexByCharacter ( 0 Till 1 , 0 Till Len ( källa ) - 1 ) Som variant Om vänster ( källa , 1 ) <> Vänster ( mål , 1 ) Då tabell ( 0 , 0 ) = Tillämpning . Min ( replaceCost , ( deleteCost + insertCost )) Sluta om sourceIndexByCharacter ( 0 , 0 ) = Vänster ( källa , 1 ) sourceIndexByCharacter ( 1 , 0 ) = 0 Dimma deleteDistance As Double Dim insertDistance As Double Dim matchDistance As Double För i = 1 Till Len ( källa ) - 1 deleteDistance = tabell ( i - 1 , 0 ) + deleteCost insertDistance = (( i + 1 ) * deleteCost ) + insertCost Om Mid ( källa , i + 1 , 1 ) = Vänster ( mål , 1 ) Då matchDistance = ( i * deleteCost ) + 0 Annan matchDistance = ( i * deleteCost ) + replaceCost Sluta om tabell ( i , 0 ) = Tillämpning . Min ( Application . Min ( deleteDistance , insertDistance ), matchDistance ) Nästa För j = 1 Till Len ( mål ) - 1 deleteDistance = tabell ( 0 , j - 1 ) + insertCost insertDistance = (( j + 1 ) * insertCost ) + deleteCost Om vänster ( källa , 1 ) = Mitt ( mål , j + 1 , 1 ) Då matchDistance = ( j * insertCost ) + 0 Annan matchDistance = ( j * insertCost ) + replaceCost Sluta om tabell ( 0 , j ) = Tillämpning . Min ( Application . Min ( deleteDistance , insertDistance ), matchDistance ) Nästa För i = 1 Till Len ( källa ) - 1 Dim maxSourceLetterMatchIndex As Integer Om Mid ( källa , i + 1 , 1 ) = Vänster ( mål , 1 ) Då maxSourceLetterMatchIndex = 0 Annan maxSourceLetterMatchIndex = - 1 Sluta om För j = 1 Till Len ( mål ) - 1 Dim candidateSwapIndex Som heltal candidateSwapIndex = - 1 För k = 0 Till UBound ( sourceIndexByCharacter , 2 ) Om sourceIndexByCharacter ( 0 , k ) = Mid ( target , j + 1 , 1 ) Då candidateSwapIndex = sourceIndexByCharacter ( 1 , k ) Nästa Dim jSwap Som heltal jSwap = maxSourceLetterMatchIndex deleteDistance = tabell ( i - 1 , j ) + deleteCost insertDistance = tabell ( i , j - 1 ) + insertCost matchDistance = tabell ( i - 1 , j - 1 ) Om Mid ( källa , i + 1 , 1 ) <> Mid ( mål , j + 1 , 1 ) Då matchDistance = matchDistance + replaceCost Annan maxSourceLetterMatchIndex = j Sluta om Dim swapDistance As Double Om candidateSwapIndex <> - 1 Och jSwap <> - 1 Då Dim iSwap Som heltal iSwap = candidateSwapIndex Dim preSwapCost Om iSwap = 0 Och jSwap = 0 Då preSwapCost = 0 Annan preSwapCost = tabell ( Application . Max ( 0 , iSwap - 1 ), Application . Max ( 0 , jSwap - 1 )) Sluta om swapDistance = preSwapCost + (( i - iSwap - 1 ) * deleteCost ) + (( j - jSwap - 1 ) * insertCost ) + swapCost Annan swapDistance = 500 Sluta om tabell ( i , j ) = Tillämpning . Min ( Application . Min ( Application . Min ( deleteDistance , insertDistance ), _ matchDistance ), swapDistance ) Nästa sourceIndexByCharacter ( 0 , i ) = Mid ( källa , i + 1 , 1 ) sourceIndexByCharacter ( 1 , i ) = i Nästa WeightedDL = tabell ( Len ( källa ) - 1 , Len ( mål ) - 1 ) slutfunktion _
I programmeringsspråket Perl som en modul Text::Levenshtein::Damerau
I programmeringsspråket PlPgSQL
Ytterligare modul för MySQL

Se även

Levenshtein avstånd

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likheter
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen