Damerau-Levenštejnova razdalja

Damerau-Levenštejnova razdalja
Osnovni podatki
Vrsta:	metrika za podobnost znakovnih nizov

Damerau-Levenštejnova razdalja je v teoriji informacij, jezikoslovju računalništvu metrika znakovnih nizov (stringov) za merjenje razlike (razdalje) med dvema zaporedjema. Neformalno je Damerau-Levenštejnova razdalja med dvema besedama najmanjše število urejanj enega znaka (vstavljanj, brisanj, zamenjevanj ali prenašanj (transpozicij), potrebnih za spremembo ene besede v drugo. Imenuje se po ameriškem računalnikarju Fredericku J. Damerauu in ruskem matematiku Vladimirju Josifoviču Levenštejnu.

Damerau-Levenshteinova razdalja se od klasične Levenštejnove razdalje razlikuje po tem, da poleg treh klasičnih enoznakovnih urejevalnih operacij (vstavljanje, brisanje in zamenjevanje) med svoje dovoljene operacije vključuje prenašanja.

V svojem temeljnem prispevku iz leta 1964 je Damerau izjavil, da je bilo v preiskavi črkovalnih napak za sistem za iskanje informacij več kot 80 % posledica ene same napake ene od štirih vrst. Dameraujev prispevek je upošteval samo črkovalne napake, ki jih je bilo mogoče popraviti z največ enim urejanjem. Medtem ko je bila prvotna motivacija merjenje razdalje med človeškimi napačno črkovanimi besedami za izboljšanje aplikacij, kot je preverjanje črkovanja, se Damerau-Levenštejnova razdalja uporablja tudi v biologiji za merjenje variacije med proteinskimi zaporedji.

Definicija

Za izražanje Damerau-Levenštejnove razdalje med dvema znakovnima nizoma $a\!\,$ in $b\!\,$ je definirana funkcija $d_{a,b}(i,j)\!\,$, katere vrednost je razdalja med $i\!\,$-ta simbolno predpono (začetni podniz) znakovnega niza $a\!\,$ in $j\!\,$-to simbolno predpono znakovnega niza $b\!\,$.

Funkcija omejene razdalje je definirana rekurzivno kot: $$d_{a,b}(i,j)=\min {\begin{cases}0&{\text{pri }}i=j=0,\\d_{a,b}(i-1,j)+1&{\text{pri }}i>0,\\d_{a,b}(i,j-1)+1&{\text{pri }}j>0,\\d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}&{\text{pri }}i,j>0,\\d_{a,b}(i-2,j-2)+1_{(a_{i}\neq b_{j})}&{\text{pri }}i,j>1{\text{ in }}a_{i}=b_{j-1}{\text{ in }}a_{i-1}=b_{j}\!\,,\end{cases}}$$

kjer je $1_{(a_{i}\neq b_{j})}\!\,$ indikatorska funkcija, enaka 0 pri $a_{i}=b_{j}\!\,$ in enaka 1 drugače.

Vsak rekurzivni klic se ujema z enim od primerov, ki jih pokriva Damerau-Leveštejnova razdalja:

• $d_{a,b}(i-1,j)+1\!\,$ ustreza brisanju (iz $a\!\,$ v $b\!\,$),
• $d_{a,b}(i,j-1)+1\!\,$ ustreza vstavljanju (iz $a\!\,$ v $b\!\,$),
• $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\!\,$ ustreza ujemanju ali neujemanju, odvisno od tega, ali sta simbola enaka,
• $d_{a,b}(i-2,j-2)+1_{(a_{i}\neq b_{j})}$ ustreza prenašanju med dvema zaporednima simboloma.

Damerau-Levenštejnova razdalja med znakovnima nizoma $a\!\,$ in $b\!\,$ je potem podana z vrednostjo funkcije za polna znakovna niza: $d_{a,b}{\big (}|a|,|b|{\big )}\!\,$, kjer $i=|a|\!\,$ označuje dolžino znakovnega niza $a\!\,$, $j=|b|\!\,$ pa dolžino znakovnega niza $b\!\,$.

Algoritem

Predstavljena sta dva algoritma. Prvi, enostavnejši, izračuna tisto, kar je znano kot razdalja optimalnega poravnavanja znakovnega niza (OSA) ali omejena urejevalna razdalja, drugi pa izračuna Damerau-Levenštejnovo razdaljo s sosednjimi prenašanji. Dodajanje prenašanj znatno zaplete algoritem. Razlika med obema algoritmoma je v tem, da algoritem optimalnega poravnavanja znakovnih nizov izračuna število operacij urejanja, ki so potrebne, da so znakovni nizi enaki pod pogojem, da se noben podniz ne ureja več kot enkrat, medtem ko drugi algoritem ne predstavlja takšne omejitve.

Naj se za primer vzame urejevalno razdaljo med $\mathbf {CA} \!\,$ in $\mathbf {ABC} \!\,$. Damerau-Leveštejnova razdalja $\operatorname {DL} (\mathbf {CA} ,\mathbf {ABC} )=2\!\,$, ker je $\mathbf {CA} \to \mathbf {AC} \to \mathbf {ABC} \!\,$, vendar je razdalja optimalnega poravnavanja znakovnega niza $\operatorname {OSA} (\mathbf {CA} ,\mathbf {ABC} )=3\!\,$, ker če je uporabljena operacija $\mathbf {CA} \to \mathbf {AC} \!\,$, ni mogoče uporabiti $\mathbf {AC} \to \mathbf {ABC} \!\,$, ker bi to zahtevalo, da se podniz ureja več kot enkrat, kar v $\operatorname {OSA} \!\,$ ni dovoljeno, zato je najkrajše zaporedje operacij $\mathbf {CA} \to \mathbf {A} \to \mathbf {AB} \to \mathbf {ABC} \!\,$. Upoštevati je treba, da za razdaljo optimalnega poravnavanja znakovnega niza trikotniška neenakost ne velja:

$\operatorname {OSA} (\mathbf {CA} ,\mathbf {AC} )+\operatorname {OSA} (\mathbf {AC} ,\mathbf {ABC} )<\operatorname {OSA} (\mathbf {CA} ,\mathbf {ABC} )\!\,,$

zato to ni prava metrika.

Razdalja optimalnega poravnavanja znakovnega niza

Razdalja optimalnega poravnavanja znakovnega niza se lahko izračuna z uporabo neposredne razširitve Wagner-Fischerjevega algoritma iz dinamičnega programiranja, ki izračuna Levenštejnovo razdaljo. V psevdokodi:

algorithm OSA-distance is
   input: strings a[1..length(a)], b[1..length(b)]
   output: distance, integer
     
   let d[0..length(a), 0..length(b)] be a 2-d array of integers, dimensions length(a)+1, length(b)+1
   // d ima indekse, ki se začnejo pri 0, pri a, b in da pa pri 1.

   for i := 0 to length(a) inclusive do
      d[i, 0] := i
   for j := 0 to length(b) inclusive do
      d[0, j] := j

   for i := 1 to length(a) inclusive do
      for j := 1 to length(b) inclusive do
         if a[i] = b[j] then
            cost := 0
         else
            cost := 1
         d[i, j] := minimum(d[i - 1, j] + 1,                                 // brisanje
                            d[i,     j - 1] + 1,                             // vstavljanje
                            d[i - 1, j - 1] + cost)                          // zamenjevanje
         if i > 1 and j > 1 and a[i] = b[j - 1] and a[i - 1] = b[j] then
                d[i, j] := minimum(d[i, j], d[i - 2, j - 2] + 1)             // prenašanje
   return d[length(a), length(b)]

Razlika od algoritma za Levenštejnovo razdaljo je dodajanje zadnje ponovitve za prenašanje.

Razdalja s sosednjimi prenašanji

Naslednji algoritem izračuna Damerau-Levenštejnovo razdaljo s sosednjimi prenašanji. Kot dodatni parameter zahteva velikost abecede $\Sigma \!\,$ tako, da so vsi vnosi polj v $[0,\left\vert \Sigma \right\vert )\!\,$:

algorithm DL-distance is
   input: strings a[1..length(a)], b[1..length(b)]
   output: distance, integer

   da := new array of |Σ| integers
   for i := 1 to |Σ| inclusive do
      da[i] := 0

   let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
   // d ima indekse, ki se začnejo pri −1, pri a, b in da pa pri 1.

   maxdist := length(a) + length(b)
   d[−1, −1] := maxdist
   for i := 0 to length(a) inclusive do
      d[i, −1] := maxdist
      d[i, 0] := i
   for j := 0 to length(b) inclusive do
      d[−1, j] := maxdist
      d[0, j] := j
     
   for i := 1 to length(a) inclusive do
      db := 0
      for j := 1 to length(b) inclusive do
         k := da[b[j]]
         ℓ := db
         if a[i] = b[j] then
            cost := 0
            db := j
         else
            cost := 1
         d[i, j] := minimum(d[i − 1, j − 1] + cost,                          // zamenjevanje
                            d[i,     j − 1] + 1,                             // vstavljenje
                            d[i − 1, j  ] + 1,                               // brisanje
                            d[k − 1, ℓ − 1] + (i − k − 1) + 1 + (j - ℓ − 1)) // prenašanje
      da[a[i]] := i
   return d[length(a), length(b)]

Da se oblikuje ustrezni algoritem za izračun neomejene Damerau-Levenštejnove razdalje, je treba upoštevati, da vedno obstaja optimalno zaporedje urejevalnih operacij, kjer se enkrat prenesene črke pozneje nikoli ne spremenijo. (To velja tako dolgo dokler so stroški prenašanja $W_{T}\!\,$ vsaj povprečje stroškov vstavljanja in brisanja $2W_{T}\geq W_{I}+W_{D}\!\,$.) Tako je treba upoštevati le dva simetrična načina spreminjanja podniza več kot enkrat: (1) prestavljanje črk in vstavljenje mednje poljubnega števila znakov ali (2) brisanje zaporedje znakov in prenašanje črk, ki po brisanju postanejo sosednje. Preprosta izvedba te zamisli daje algoritem kubične zahtevnosti: $O{\big (}M\cdot N\cdot \max(M,N){\big )}\!\,$, kjer sta $M\!\,$ in $N\!\,$ dolžini znakovnih nizov. Z uporabo zamisli Lowrancea in Wagnerja je mogoče ta naivni algoritem izboljšati tako, da bo $O(M\cdot N)\!\,$ v najslabšem primeru, kar počne zgornja psevdokoda.

Zanimivo je, da je algoritem bitap mogoče spremeniti za proces prenašanja. Za primer takšne prilagoditve glej razdelek za iskanje informacij.

Uporabe

Damerau-Levenštejnova razdalja ima pomembno vlogo pri obdelavi naravnega jezika. V naravnih jezikih so znakovni nizi kratki in število napak (napačno črkovanih) redko presega 2. V takih okoliščinah se omejena in prava urejevalna razdalja zelo redko razlikujeta. Oommen in Loke sta celo ublažila omejitev omejene urejevalne razdalje z uvedbo posplošenih prenašanj. Kljub temu je treba poudariti, da omejena urejevalna razdalja običajno ne zadosti trikotniški neenakosti in je zato ni mogoče uporabiti z metričnimi drevesi.

DNK

Ker je DNK pogosto podvržena vstavljanjem, brisanjem, zamenjevanjem in prenašanjem in se vsaka od teh operacij zgodi v približno enakem časovnem razponu, je Damerau-Levenštejnova razdalja ustrezna metrika variacije med dvema verigama DNK. Pogostejša pri nalogah usklajevanja z DNK, beljakovinami in drugimi bioinformatiki je uporaba tesno povezanih algoritmov, kot sta algoritem Needleman-Wunschev algoritem ali Smith-Watermanov algoritem.

Odkrivanje goljufij

Algoritem je mogoče uporabiti s poljubno množico besed, kot so imena prodajalcev. Ker je vnos po naravi ročni, obstaja nevarnost vnosa lažnega prodajalca. Zaposleni, ki je goljuf, lahko vnese enega pravega prodajalca, kot je »Rich Heir Estate Services«, v primerjavi z lažnim prodajalcem »Rich Hier State Services«. Goljuf bi nato ustvaril lažni bančni račun in zahteval, da bi podjetje čeke usmerilo k pravemu prodajalcu in lažnemu prodajalcu. Damerau-Levenštejnov algoritem bo zaznal prestavljeno in izpuščeno črko ter na elemente opozoril preiskovalcu goljufij.

Nadzor izvoza

Vlada ZDA uporablja Damerau-Levenštejnovo razdaljo s svojim API-jem Consolidated Screening List.

Glej tudi

• Ispell – črkovalnik, ki predlaga popravke temelječe na Damerau-Levenštejnovi razdalji enaki 1
• skvoterstvo preko napake – oblika domenskega skvoterstva, ki se opira na napake pri vnosu naslova spletne strani

Viri

• Bard, Gregory V. (2007), »Spelling-error tolerant, order-independent pass-phrases via the Damerau–Levenshtein string-edit distance metric«, Proceedings of the Fifth Australasian Symposium on ACSW Frontiers : 2007, Ballarat, Australia, January 30 - February 2, 2007, (Conferences in Research and Practice in Information Technology), vol. 68, Darlinghurst, Avstralija: Australian Computer Society, Inc., str. 117–124, ISBN 978-1-920682-49-1
• Boytsov, Leonid (maj 2011), »Indexing methods for approximate dictionary searching«, Journal of Experimental Algorithmics, 16: 1, doi:10.1145/1963190.1963191, S2CID 15635688
• Brill, Eric; Moore, Robert C. (2000). An Improved Error Model for Noisy Channel Spelling Correction (PDF). Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. str. 286–293. doi:10.3115/1075218.1075255. Arhivirano iz prvotnega spletišča (PDF) dne 21. decembra 2012.
• Damerau, Fred J. (marec 1964), »A technique for computer detection and correction of spelling errors«, Communications of the ACM, 7 (3): 171–176, doi:10.1145/363958.363994, ISSN 0001-0782, S2CID 7713345
• Levenštejn, Vladimir Josifovič (1965), Двоичные коды с исправлением выпадений, вставок и замещений символов [Dvojiške kode s popravki izbrisanj, vstavljanj in zamenjevanj simbolov], Dokladi Akademii Nauk SSSR (v ruščini), 163 (4): 845–848
  • izdano v angleščini: Levenštejn, Vladimir Josifovič (februar 1966), »Binary codes capable of correcting deletions, insertions, and reversals«, Soviet Physics Doklady, 10 (8): 707–710, Bibcode:1966SPhD...10..707L
• Li, Mu; Zhang, Yang; Zhu, Muhua; Zhou, Ming (17. julij 2006). Exploring distributional similarity based models for query spelling correction (PDF). Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. str. 1025–. doi:10.3115/1220175.1220304. Arhivirano iz prvotnega spletišča (PDF) dne 1. aprila 2010.{{navedi konferenco}}: Vzdrževanje CS1: dodatno ločilo (povezava)
• Lowrance, Roy; Wagner, Robert A. (april 1975), »An Extension of the String-to-String Correction Problem«, Journal of the ACM, 22 (2): 177–183, doi:10.1145/321879.321880, ISSN 0004-5411, S2CID 18892193
• Majorek, Karolina A.; Dunin-Horkawicz, Stanisław; Steczkiewicz, Kamil; Muszewska, Anna; Nowotny, Marcin; Ginalski, Krzysztof; Bujnicki, Janusz M. (2013), »The RNase H-like superfamily: new members, comparative structural analysis and evolutionary classification«, Nucleic Acids Research, 42 (7): 4160–4179, doi:10.1093/nar/gkt1414, ISSN 0305-1048, PMC 3985635, PMID 24464998
• Navarro, Gonzalo (2001), »A guided tour to approximate string matching« (PDF), ACM Computing Surveys, 33 (1): 31–88, CiteSeerX 10.1.1.452.6317, doi:10.1145/375360.375365, S2CID 207551224
• Oommen, B. J.; Loke, R. K. S. (1997), »Pattern recognition of strings with substitutions, insertions, deletions and generalized transpositions«, Pattern Recognition, 30 (5): 789–800, Bibcode:1997PatRe..30..789O, CiteSeerX 10.1.1.50.1459, doi:10.1016/S0031-3203(96)00101-X, ISSN 0031-3203