Etäisyys Damerausta Loewensteiniin

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 31.7.2020 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Damerau-Levenshteinin etäisyys (nimetty tutkijoiden Frederic Dameraun ja Vladimir Levenshteinin mukaan) on kahden merkkijonon välisen eron mitta, joka määritellään kääntämiseen vaadittavien lisäysten, poistojen, korvausten ja transponointien (kahden vierekkäisen merkin permutaatioiden) vähimmäismääräksi. yksi merkkijono toiseen. Se on muunnos Levenshtein-etäisyydestä : merkkien transponointi (permutaatio) on lisätty Levenshtein-etäisyydellä määritettyjen merkkien lisäys-, poisto- ja korvaustoimintoihin.

Algoritmi

Kahden merkkijonon välinen Damerau-Levenshtein-etäisyys määritellään funktiolla seuraavasti: $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{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{ muuten,}}\end{cases}}$

missä indikaattorifunktio on yhtä suuri kuin nolla ja 1 muuten. $1_{{(a_{i}\neq b_{j})}}$ $a_{i}=b_{j}$

Jokainen rekursiivinen puhelu vastaa yhtä seuraavista tapauksista:

$d_{{a,b}}(i-1,j)+1$ vastaa merkin poistamista ( a :sta b :hen ),
$d_{{a,b}}(i,j-1)+1$ vastaa lisäystä ( a :sta b :hen ),
$d_{{a,b}}(i-1,j-1)+1_{{(a_{i}\neq b_{j})}}$ vastaavuus tai ristiriita, riippuen hahmojen yhteensopivuudesta,
$d_{{a,b}}(i-2,j-2)+1$ kahden peräkkäisen merkin permutaatiossa.

Toteutukset

pythonissadef damerau_levenshtein_distance ( s1 , s2 ): d = {} lenstr1 = len ( s1 ) lenstr2 = len ( s2 ) i : lle alueella ( -1 , lenstr1 + 1 ) : d [( i , - 1 )] = i + 1 j :lle alueella ( - 1 , lenstr2 + 1 ) : d [( - 1 , j )] = j + 1 i alueella ( lenstr1 ) : _ j :lle alueella ( lenstr2 ) : jos s1 [ i ] == s2 [ j ]: hinta = 0 muuta : hinta = 1 d [( i , j )] = min ( d [( i - 1 , j )] + 1 , # poisto d [( i , j - 1 )] + 1 , # lisäys d [( i - 1 , j - 1 )] + kustannus , # korvaus ) jos i ja j ja s1 [ i ] == s2 [ j - 1 ] ja s1 [ i - 1 ] == s2 [ j ]: d [( i , j )] = min ( d [( i , j )], d [ i - 2 , j - 2 ] + 1 ) # transponointi paluu d [ lenstr1 - 1 , lenstr2 - 1 ]

Adalla funktio Damerau_Levenshtein_Distance ( L , R : String ) return Natural on D : array ( L' Ensimmäinen - 1..L'Viimeinen , R'Ensimmäinen - 1..R'Viimeinen ) Natural ; _ _ _ _ _ _ _ _ _ _ _ _ alkaa I : lle D ' Range ( 1 ) -silmukassa D ( I , D ' Ensimmäinen ( 2 )) := I ; end - silmukka ; I : lle D ' Range ( 2 ) -silmukassa D ( D ' Ensimmäinen ( 1 ), I ) := I ; end - silmukka ; J : lle R ' Range -silmukassa I L ' Range -silmukassa _ _ D ( I , J ) := Luonnollinen Min _ ( Luonnollinen ' min ( D ( I - 1 , J ), D ( I , J - 1 )) + 1 , D ( I - 1 , J - 1 ) + ( jos L ( I ) = R ( J ) niin 0 muuten 1 )); jos J > R ' Ensin ja sitten I > L ' Ensin ja sitten R ( J ) = L ( I - 1 ) ja sitten R ( J - 1 ) = L ( I ) sitten D ( I , J ) : = Luonnollinen ' Min ( D ( I , J ), D ( I - 2 , J - 2 ) + 1 ); loppu jos ; end - silmukka ; end - silmukka ; return D ( L ' Last , R ' Last ); end Damerau_Levenshtein_Distance ;

Visual Basic for Applications (VBA)Public Function WeightedDL ( lähde As String , kohde As String ) As Double Dim deleteCost As Double Dim insertCost As Double Himmeä vaihtohinta kuin kaksinkertainen Dim swapCost As Double deleteCost = 1 insertCost = 1 korvauskustannukset = 1 vaihtohinta = 1 Dim i Kokonaislukuna _ Himmeä j Kokonaislukuna _ Himmeä k Kokonaislukuna _ Jos Len ( lähde ) = 0 Sitten WeightedDL = Len ( tavoite ) * insertCost poistumistoiminto _ Lopeta jos Jos Len ( kohde ) = 0 Sitten WeightedDL = Len ( lähde ) * deleteCost poistumistoiminto _ Lopeta jos Himmeä pöytä ( ) AsDouble Redim- taulukko ( Len ( lähde ), Len ( kohde )) Himmeä sourceIndexByCharacter ( ) Varianttina ReDim sourceIndexByCharacter ( 0 - 1 , 0 - Len ( lähde ) - 1 ) Varianttina _ Jos Vasen ( lähde , 1 ) <> Vasen ( kohde , 1 ) Sitten taulukko ( 0 , 0 ) = Sovellus . Min ( korvauskustannukset , ( deleteCost + insertCost )) Lopeta jos sourceIndexByCharacter ( 0 , 0 ) = Vasen ( lähde , 1 ) sourceIndexByCharacter ( 1 , 0 ) = 0 Dim deleteDistance As Double Dim insertDistance As Double Dim matchDistance As Double Jos i = 1 - Len ( lähde ) - 1 deleteDistance = taulukko ( i - 1 , 0 ) + deleteCost insertDistance = (( i + 1 ) * deleteCost ) + insertCost Jos Keski ( lähde , i + 1 , 1 ) = vasen ( kohde , 1 ) _ matchDistance = ( i * deleteCost ) + 0 Muu matchDistance = ( i * deleteCost ) + korvaaCost Lopeta jos taulukko ( i , 0 ) = Sovellus . Min ( Application . Min ( deleteDistance , insertDistance ), matchDistance ) Seuraava Jos j = 1 Len ( kohde ) - 1 _ deleteDistance = taulukko ( 0 , j - 1 ) + insertCost insertDistance = (( j + 1 ) * insertCost ) + deleteCost Jos Vasen ( lähde , 1 ) = Keski ( kohde , j + 1 , 1 ) Sitten matchDistance = ( j * insertCost ) + 0 Muu matchDistance = ( j * insertCost ) + korvaaCost Lopeta jos taulukko ( 0 , j ) = Sovellus . Min ( Application . Min ( deleteDistance , insertDistance ), matchDistance ) Seuraava Jos i = 1 - Len ( lähde ) - 1 Dim maxSourceLetterMatchIndex Kokonaislukuna _ Jos Keski ( lähde , i + 1 , 1 ) = vasen ( kohde , 1 ) _ maxSourceLetterMatchIndex = 0 Muu maxSourceLetterMatchIndex = - 1 Lopeta jos Jos j = 1 Len ( kohde ) - 1 _ Himmeä ehdokasSwapIndex Kokonaislukuna _ Kandidaattivaihtoindeksi = - 1 k = 0 - UBound ( sourceIndexByCharacter , 2 ) _ Jos sourceIndexByCharacter ( 0 , k ) = Mid ( kohde , j + 1 , 1 ) Sitten KandidaattiSwapIndex = sourceIndexByCharacter ( 1 , k ) Seuraava Himmeä jSwap kokonaislukuna _ jSwap = maxSourceLetterMatchIndex deleteDistance = taulukko ( i - 1 , j ) + deleteCost insertDistance = taulukko ( i , j - 1 ) + insertCost matchDistance = taulukko ( i - 1 , j - 1 ) Jos Keski ( lähde , i + 1 , 1 ) < > Keski ( kohde , j + 1 , 1 ) Sitten matchDistance = matchDistance + korvauskustannukset Muu maxSourceLetterMatchIndex = j Lopeta jos Dim swapDistance As Double Jos KandidaattiSwapIndex <> - 1 Ja jSwap <> - 1 Sitten Himmeä iSwap kokonaislukuna _ iSwap = ehdokasSwapIndex Himmeä preSwapCost Jos iSwap = 0 ja jSwap = 0 Sitten PreSwapCost = 0 Muu preSwapCost = taulukko ( Sovellus . Max ( 0 , iSwap - 1 ), Sovellus . Max ( 0 , jSwap - 1 )) Lopeta jos swapDistance = preSwapCost + (( i - iSwap - 1 ) * deleteCost ) + ( ( j - jSwap - 1 ) * insertCost ) + swapCost Muu vaihtoetäisyys = 500 Lopeta jos taulukko ( i , j ) = Sovellus . Min ( Application . Min ( Application . Min ( deleteDistance , insertDistance ), _ matchDistance ), swapDistance ) Seuraava sourceIndexByCharacter ( 0 , i ) = Keski ( lähde , i + 1 , 1 ) sourceIndexByCharacter ( 1 , i ) = i Seuraava PainotettuDL = taulukko ( Len ( lähde ) - 1 , Len ( kohde ) - 1 ) lopputoiminto _
Perl-ohjelmointikielessä moduulina Text::Levenshtein::Damerau
PlPgSQL-ohjelmointikielellä
Lisämoduuli MySQL:lle

Katso myös

Levenshtein etäisyys

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
Muut	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono