Afstand fra Damerau til Loewenstein

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 31. juli 2020; checks kræver 5 redigeringer .

Damerau-Levenshtein afstand (opkaldt efter videnskabsmændene Frederic Damerau og Vladimir Levenshtein ) er et mål for forskellen mellem to strenge af tegn, defineret som det mindste antal indsættelser, sletninger, erstatninger og transpositioner (permutationer af to tilstødende tegn), der kræves for at oversætte en streng ind i en anden. Det er en modifikation af Levenshtein-afstanden : operationen med transponering (permutation) af tegn er blevet tilføjet til operationerne med at indsætte, slette og erstatte tegn defineret i Levenshtein-afstanden.

Algoritme

Damerau-Levenshtein afstanden mellem to strenge og er defineret af funktionen som: $-en$ $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{ og }}a_{i}=b_{j-1}{\text{ og }}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{ ellers,}}\end{cases}}$

hvor er indikatorfunktionen lig med nul ved og 1 ellers. $1_{{(a_{i}\neq b_{j})}}$ $a_{i}=b_{j}$

Hvert rekursivt opkald svarer til et af tilfældene:

$d_{{a,b}}(i-1,j)+1$ svarer til at slette et tegn (fra a til b ),
$d_{{a,b}}(i,j-1)+1$ matcher indsættelse (fra a til b ),
$d_{{a,b}}(i-1,j-1)+1_{{(a_{i}\neq b_{j})}}$ match eller mismatch, afhængigt af matchningen af karaktererne,
$d_{{a,b}}(i-2,j-2)+1$ i tilfælde af permutation af to på hinanden følgende tegn.

Implementeringer

i pythondef damerau_levenshtein_distance ( s1 , s2 ): d = {} lenstr1 = len ( s1 ) lenstr2 = len ( s2 ) for i i området ( -1 , lensstr1 + 1 ) : d [( i , -1 ) ] = i + 1 for j i området ( -1 , lensstr2 + 1 ) : d [( -1 , j ) ] = j + 1 for i inden for rækkevidde ( lenstr1 ): for j i rækkevidde ( lenstr2 ): hvis s1 [ i ] == s2 [ j ]: pris = 0 andet : pris = 1 d [( i , j )] = min ( d [( i - 1 , j )] + 1 , # sletning d [( i , j - 1 )] + 1 , # indsættelse d [( i - 1 , j - 1 )] + omkostninger , # substitution ) hvis i og j og s1 [ i ] == s2 [ j - 1 ] og s1 [ i - 1 ] == s2 [ j ]: d [( i , j )] = min ( d [( i , j )], d [ i - 2 , j - 2 ] + 1 ) # transposition return d [ lenstr1 - 1 , lenstr2 - 1 ]

På Ada funktion Damerau_Levenshtein_Distance ( L , R : String ) returner Naturlig er D : array ( L ' First - 1 .. L ' Last , R ' First - 1 .. R ' Last ) of Natural ; begynde for I in D ' Range ( 1 ) loop D ( I , D ' First ( 2 )) := I ; ende -løkke ; for I in D ' Range ( 2 ) loop D ( D ' First ( 1 ), I ) := I ; ende -løkke ; for J in R ' Range loop for I i L ' Range loop D ( I , J ) := Naturlig ' Min ( Naturlig ' Min ( D ( I - 1 , J ), D ( I , J - 1 )) + 1 , D ( I - 1 , J - 1 ) + ( hvis L ( I ) = R ( J ) så 0 ellers 1 )); hvis J > R ' Først og derefter I > L ' Først og derefter R ( J ) = L ( I - 1 ) og derefter R ( J - 1 ) = L ( I ) derefter D ( I , J ) := Naturlig ' Min ( D ( I , J ), D ( I - 2 , J - 2 ) + 1 ); ende hvis ; ende -løkke ; ende -løkke ; return D ( L ' Sidste , R ' Sidste ); ende Damerau_Levenshtein_Afstand ;

Om Visual Basic for Applications (VBA)Public Function WeightedDL ( kilde som streng , mål som streng ) som dobbelt Dim deleteCost As Double Dim indsætKost som dobbelt Dim replaceCost As Double Dim swapCost As Double sletPris = 1 indsætCost = 1 erstatningsomkostning = 1 byttepris = 1 Dim i As Integer Dim j Som heltal Dim k Som heltal Hvis Len ( kilde ) = 0 Så VægtetDL = Len ( mål ) * insertCost udgangsfunktion _ Afslut hvis Hvis Len ( mål ) = 0 Så WeightedDL = Len ( kilde ) * deleteCost udgangsfunktion _ Afslut hvis Dim bord ( ) AsDouble ReDim tabel ( Len ( kilde ), Len ( mål )) Dim sourceIndexByCharacter () Som variant ReDim sourceIndexByCharacter ( 0 Til 1 , 0 Til Len ( kilde ) - 1 ) Som Variant Hvis Venstre ( kilde , 1 ) <> Venstre ( mål , 1 ) Så tabel ( 0 , 0 ) = Anvendelse . Min ( replaceCost , ( deleteCost + insertCost )) Afslut hvis sourceIndexByCharacter ( 0 , 0 ) = Venstre ( kilde , 1 ) sourceIndexByCharacter ( 1 , 0 ) = 0 Dim deleteDistance As Double Dæmp indsatsafstand som dobbelt Dim matchDistance As Double For i = 1 til Len ( kilde ) - 1 deleteDistance = tabel ( i - 1 , 0 ) + deleteCost insertDistance = (( i + 1 ) * deleteCost ) + insertCost Hvis Mid ( kilde , i + 1 , 1 ) = Venstre ( mål , 1 ) _ matchDistance = ( i * deleteCost ) + 0 Andet matchDistance = ( i * deleteCost ) + replace Cost Afslut hvis tabel ( i , 0 ) = Anvendelse . Min ( Application . Min ( deleteDistance , insertDistance ), matchDistance ) Næste For j = 1 til Len ( mål ) - 1 deleteDistance = tabel ( 0 , j - 1 ) + insertCost insertDistance = (( j + 1 ) * insertCost ) + deleteCost Hvis Venstre ( kilde , 1 ) = Midt ( mål , j + 1 , 1 ) _ matchDistance = ( j * insertCost ) + 0 Andet matchDistance = ( j * insertCost ) + replaceCost Afslut hvis tabel ( 0 , j ) = Anvendelse . Min ( Application . Min ( deleteDistance , insertDistance ), matchDistance ) Næste For i = 1 til Len ( kilde ) - 1 Dim maxSourceLetterMatchIndex As Integer Hvis Mid ( kilde , i + 1 , 1 ) = Venstre ( mål , 1 ) _ maxSourceLetterMatchIndex = 0 Andet maxSourceLetterMatchIndex = - 1 Afslut hvis For j = 1 til Len ( mål ) - 1 Dim candidateSwapIndex As Integer candidateSwapIndex = - 1 For k = 0 til UBound ( sourceIndexByCharacter , 2 ) Hvis sourceIndexByCharacter ( 0 , k ) = Mid ( target , j + 1 , 1 ) Så candidateSwapIndex = sourceIndexByCharacter ( 1 , k ) Næste Dim jSwap Som heltal jSwap = maxSourceLetterMatchIndex deleteDistance = tabel ( i - 1 , j ) + deleteCost insertDistance = tabel ( i , j - 1 ) + indsætCost matchDistance = tabel ( i - 1 , j - 1 ) Hvis Mid ( kilde , i + 1 , 1 ) < > Mid ( mål , j + 1 , 1 ) matchDistance = matchDistance + erstatningsomkostninger Andet maxSourceLetterMatchIndex = j Afslut hvis Dim swapDistance As Double Hvis candidateSwapIndex <> - 1 Og jSwap <> - 1 Så Dæmp iSwap som heltal iSwap = candidateSwapIndex Dim preSwapCost Hvis iSwap = 0 Og jSwap = 0 Så preSwapCost = 0 Andet preSwapCost = tabel ( Application . Max ( 0 , iSwap - 1 ), Application . Max ( 0 , jSwap - 1 )) Afslut hvis swapDistance = preSwapCost + (( i - iSwap - 1 ) * deleteCost ) + (( j - jSwap - 1 ) * insertCost ) + swapCost Andet swapDistance = 500 Afslut hvis tabel ( i , j ) = Anvendelse . Min ( Application . Min ( Application . Min ( deleteDistance , insertDistance ), _ matchDistance ), swapDistance ) Næste sourceIndexByCharacter ( 0 , i ) = Midt ( kilde , i + 1 , 1 ) sourceIndexByCharacter ( 1 , i ) = i Næste VægtetDL = tabel ( Len ( kilde ) - 1 , Len ( mål ) - 1 ) afslutte funktion
I programmeringssproget Perl som et modul Tekst::Levenshtein::Damerau
I programmeringssproget PlPgSQL
Ekstra modul til MySQL

Se også

Levenshtein afstand

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng