Levenštejnova razdalja

Levenštejnova razdalja
Matrika urejevalne razdalje za dve besedi (Levenshtein, Levenshtien) z uporabo stroškov zamenjave kot 1 in stroškov izbrisa ali vstavljanja kot 0,5
Osnovni podatki
Vrsta:	metrika za podobnost znakovnih nizov

Levenštejnova razdálja [levenštéjnova ~] je v teoriji informacij, jezikoslovju in računalništvu metrika znakovnih nizov (stringov) za merjenje razlike (razdalje) med dvema zaporedjema. Levenštejnova razdalja med dvema besedama je najmanjše število urejanj enega znaka (vstavljanj, brisanj ali zamenjevanj), potrebnih za spremembo ene besede v drugo. Ime je dobila po ruskem matematiku Vladimirju Josifoviču Levenštejnu, ki je leta 1965 definiral metriko.

Levenštejnova razdalja se lahko imenuje tudi urejevalna razdalja (razdalja urejanja), čeprav lahko ta izraz označuje tudi večjo družino metrik razdalje, znanih skupaj kot urejevalna razdalja.  Tesno je povezana s poravnavanji znakovnih nizov po parih.

Definicija

Levenštejnova razdalja med dvema znakovnima nizoma $a,b\!\,$ (z dolžinama $|a|\!\,$ in $|b|\!\,$) se označi kot $\operatorname {lev} (a,b)\!\,$ in je podana kot:

$\operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ pri }}|b|=0,\\|b|&{\text{ pri }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ pri }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\\\end{cases}}&{\text{ drugače}}\end{cases}}\!\,$

$a\!\,$ je izvorni znankovni niz, $b\!\,$ pa ciljni znakovni niz. Tu $\operatorname {tail}$ poljubnega znakovnega niza $x\!\,$ označuje niz vseh znakov razen prvega znaka $x\!\,$ – $\operatorname {tail} (x_{0}x_{1}\dots x_{n})=x_{1}x_{2}\dots x_{n}\!\,$), in $\operatorname {head} (x)\!\,$ prvi znak niza $x\!\,$ – $\operatorname {head} (x_{0}x_{1}\dots x_{n})=x_{0}$. Za sklicevanje na $n\!\,$-ti znak niza $x\!\,$ se rabita zapisa $x[n]\!\,$ ali $x_{n}\!\,$, šteto (številčeno) od 0, in tako velja $\operatorname {head} (x)=x_{0}=x[0]\!\,$. $\operatorname {lev} (a,b)\!\,$ se označuje tudi kot $\operatorname {LD(a,b)} \!\,$.

Prvi element v minimumu ustreza brisanju (od $a\!\,$ do $b\!\,$), drugi vstavljanju in tretji zamenjevanju.

Ta definicija neposredno ustreza naivni rekurzivni izvedbi.

Zgled

Matrika urejevalne razdalje za dve besedi (Levenshtein, Levenshtien) z uporabo stroškov zamenjevanja kot 1 in stroškov brisanja ali vstavljanja kot 0,5

Levenštejnova razdalja med besedama »kitten« in »sitting« je na primer enaka 3, ker naslednja 3 urejanja pretvorijo eno besedo v drugo, in pri tem to ni moč narediti z manj kot tremi urejanji:

1. kitten → sitten (zamenjevanje črke »s« za »k«),
2. sitten → sittin (zamenjevanje črke »i« za »e«),
3. sittin → sitting (vstavljanje črke »g« na koncu).

Preprosti zgled brisanja se lahko vidi pri besedah »uninformed« in »uniformed«, ki imata razdaljo 1:

1. uninformed → uniformed (brisanje črke »n«).

Zgornje in spodnje meje

Levenštejnova razdalja ima več preprostih zgornjih in spodnjih mej. Te vključujejo:

• to je vsaj absolutna vrednost razlike velikosti obeh znakovnih nizov.
• to je največ dolžina daljšega znakovnega niza.
• nič je, če in samo če sta znakovna niza enaka.
• če sta znakovna niza enake velikosti, je Hammingova razdalja zgornja meja Levenštejnove razdalje. Hammingova razdalja je število položajev, na katerih so ustrezni simboli v dveh znakovnih nizih različni.
• Levenštejnova razdalja med dvema znakovnima nizoma ni večja od vsote njunih Levenštejnovih razdalj od tretjega znakovnega niza (trikotniška neenakost).

Zgled, ko je Levenštejnova razdalja med dvema znakovnima nizoma enake dolžine strogo manjša od Hammingove razdalje, je podana s parom »flaw« in »lawn«. Tukaj je Leveštejnova razdalja enaka 2 (spredaj se izbriše »f« in vstavi »n« na koncu). Hammingova razdalja je enaka 4.

Uporabe

Pri približnem ujemanju znakovnih nizov je cilj najti ujemanja za kratke nize v mnogih daljših besedilih v primerih, kjer je pričakovati majhno število razlik. Kratki znakovni nizi lahko izvirajo na primer iz slovarja. Pri tem je en od znakovnih nizov običajno kratek, drug pa poljubno dolg. To ima široko paleto uporab, na primer črkovalnike, sisteme popravkov za optično prepoznavanje znakov in programsko opremo za pomoč pri prevajanju v naravnem jeziku na podlagi prevodnega pomnilnika.

Levenštejnovo razdaljo je mogoče izračunati tudi med dvema daljšima znakovnima nizoma, vendar je zaradi stroškov izračuna, ki je približno sorazmeren zmnožku obeh dolžin znakovnih nizov, to nepraktično. Ko se torej uporabljajo za pomoč pri iskanju mehkega znakovnega niza v uporabah, kot je povezovanje zapisov, so primerjani znakovni nizi običajno kratki, da pomagajo izboljšati hitrost primerjav.

V jezikoslovju se Levenštejnova razdalja uporablja kot metrika za količinsko opredelitev jezikoslovne razdalje ali tega, kako različna sta si dva jezika drug od drugega. Povezana je z vzajemno razumljivostjo: večja kot je jezikovna razdalja, manjša je medsebojna razumljivost, in obratno, manjša kot je jezikovna razdalja, večja je medsebojna razumljivost.

Povezava z drugimi metrikami urejevalne razdalje

Obstajajo tudi druge priljubljene mere urejevalne razdalje, ki se izračunajo z uporabo drugačnega nabora dovoljenih urejevalnih operacij. Na primer:

• Damerau-Levenštejnova razdalja omogoča prenašanje (transpozicijo) dveh sosednjih znakov poleg vstavljanja, brisanja in zamenjevanja,
• razdalja najdaljšega skupnega podzaporedja (LCS) omogoča samo vstavljanje in brisanje, ne pa zamenjevanja,
• Hammingova razdalja dovoljuje samo zamenjevanje, zato velja samo za znakovne nize enake dolžine,
• Jarova razdalja omogoča samo prenašanje.

Urejevalna razdalja je običajno definirana kot parametrabilna metrika, izračunana z določenim naborom dovoljenih urejevalnih operacij, vsaki operaciji pa je dodeljen strošek (po možnosti neskončen). To je nadalje posplošeno z algoritmi za poravnavanje zaporedij DNK, kot je Smith-Watermanov algoritem, zaradi česar so stroški operacije odvisni od tega, kje se izvaja.

Računanje

Rekurzivno

To je preprosta, a neučinkovita, rekurzivna implementacija v jeziku Haskell funkcije lRazdalja, ki vzame dva znakovna niza, s in t, skupaj z njunima dolžinama, in vrne Levenštejnovo razdaljo med njima:

lRazdalja :: Eq a => [a] -> [a] -> Int
lRazdalja [] t = length t -- Če je prazen s, je razdalja število znakov v t
lRazdalja s [] = length s -- Če je prazen t, je razdalja število znakov v s
lRazdalja (a : s') (b : t')
  | a == b = lRazdalja s' t' -- Če sta prva znaka enaka, se lahko zanemarita
  | otherwise = 1 + minimum -- Drugače se poskusi vsa mogoča dejanja in izbere najboljšega
      [ lRazdalja (a : s') t' -- Znak je vstavljen (b vstavljen)
      , lRazdalja s' (b : t') -- Znak je brisan (a brisan)
      , lRazdalja s' t' -- Znak je zamenjan (a je zamenjan z b)
      ]

Ta izvedba je zelo neučinkovita, ker večkrat znova izračuna Levenštejnovo razdaljo istih znakovnih podnizov.

Učinkovitejša metoda ne bi nikoli ponovila istega izračuna razdalje. Na primer, Leveštejnova razdalja vseh možnih pripon je lahko shranjena v nizu $M\!\,$, kjer je $M[i][j]\!\,$ razdalja med zadnjimi $i\!\,$-timi znaki niza s in zadnjimi $j\!\,$-timi znaki niza t. Razpredelnico je enostavno sestaviti po eno vrstico naenkrat, začenši z vrstico 0. Ko je celotna razpredelnica sestavljena, je želena razdalja v njej v zadnji vrstici in stolpcu, ki predstavlja razdaljo med vsemi znaki v nizu s in vsemi znaki v t.

Iterativno s polno matriko

Ta razdelek uporablja nize, ki temeljijo na 1, namesto nizov, ki temeljijo na 0. Če je $m\!\,$ matrika, $m[i,j]\!\,$ sta $i\!\,$-ta vrstica in $j\!\,$-ti stolpec matrike, pri čemer ima prva vrstica indeks 0, prvi stolpec pa indeks 0.

Izračun Levenštejnove razdalje temelji na ugotovitvi, da če se rezervira matriko za hrambo Levenštejnove razdalje med vsemi predponami prvega znakovnega niza in vsemi predponami drugega, potem se lahko izračuna vrednosti v matriki na način dinamičnega programiranja in se tako najde razdaljo med dvema polnima znakovnima nizoma kot zadnjo izračunano vrednost.

Ta algoritem, primer dinamičnega programiranja od spodaj navzgor, je z različicami obravnavan v članku Problem popravljanja od znakovnega niza do znakovnega niza (The String-to-string correction problem) iz leta 1974 Roberta A. Wagnerja in Michaela Johna Fischerja.

To je preprosta izvedba v psevdokodi za funkcijo LevenstejnovaRazdalja, ki vzame dva znakovna niza, s dolžine m in t dolžine n, ter vrne Levenštejnovo razdaljo med njima:

function LevenstejnovaRazdalja(char s[1..m], char t[1..n]):
  // za vse i in j, bo d[i,j] vseboval Levenštejnovo razdaljo med
  // prvimi i znaki niza s in prvimi j znaki niza t
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // izvorne predpone se lahko pretvorijo v prazen znakovni niz
  // z opustitvijo vseh znakov
  for i from 1 to m:
    d[i, 0] := i
 
  // ciljne predpone se lahko dosežejo iz prazne izvorne predpone
  // z vstavljanjem vsakega znaka
  for j from 1 to n:
    d[0, j] := j
 
  for j from 1 to n:
    for i from 1 to m:
      if s[i] = t[j]:
        substitutionCost := 0
      else:
        substitutionCost := 1

      d[i, j] := minimum(d[i-1, j] + 1,                   // brisanje
                         d[i, j-1] + 1,                   // vstavljanje
                         d[i-1, j-1] + substitutionCost)  // zamenjevanje
 
  return d[m, n]

Dva zgleda dobljene matrike, $\operatorname {lev} ({\text{kitten}},{\text{sitting}})\!\,$ in $\operatorname {lev} ({\text{Saturday}},{\text{Sunday}})\!\,$ (lebdenje nad označeno številko razkrije operacijo, izvedeno za pridobitev te številke):

k i t t e n 0 1 2 3 4 5 6 s 1 1 2 3 4 5 6 i 2 2 1 2 3 4 5 t 3 3 2 1 2 3 4 t 4 4 3 2 1 2 3 i 5 5 4 3 2 2 3 n 6 6 5 4 3 3 2 g 7 7 6 5 4 4 3

S a t u r d a y 0 1 2 3 4 5 6 7 8 S 1 0 1 2 3 4 5 6 7 u 2 1 1 2 2 3 4 5 6 n 3 2 2 2 3 3 4 5 6 d 4 3 3 3 3 4 3 4 5 a 5 4 3 4 4 4 4 3 4 y 6 5 4 4 5 5 5 4 3

Invarianta, ki se ohranja v celotnem algoritmu, je, da se lahko začetni segment s[1..i] pretvori v t[1..j] z uporabo najmanj d[i, j] operacij. Na koncu spodnji desni element matrike vsebuje odgovor.

Iterativno z dvema matričnima vrsticama

Izkaže se, da sta za konstrukcijo potrebni samo dve vrstici razpredelnice – prejšnja vrstica in trenutna vrstica, ki se izračunava, če se ne želi rekonstruirati urejenih vhodnih znakovnih nizov.

Levenštejnovo razdaljo je mogoče izračunati iterativno z uporabo naslednjega algoritma:

function LevenstejnovaRazdalja(char s[0..m-1], char t[0..n-1]):
    // označitev dveh vektorjev s celoštevilskima razdaljama
    declare int v0[n + 1]
    declare int v1[n + 1]

    // nastavitev v0 (predhodna vrstica razdalj)
    // ta vrstica je A[0][i]: urejevalna razdalja od praznega s do t;
    // ta razdalja je število znakov, ki se jih pripne nizu s za niz t.
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m - 1:
        // izračun v1 (trenutna vrstica razdalj) iz predhodne vrstice v0

        // prvi element v1 je A[i + 1][0]
        // urejevalna razdalja je brisanje (i + 1) znakov iz niza s, da je enak
        // praznemu nizu t
        v1[0] = i + 1

        // uporaba formule za zapolnitev preostale vrstice
        for j from 0 to n - 1:
            // računanje stroškov za A[i + 1][j + 1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // kopiranje v1 (trenutna vrstica) v v0 (predhodna vrstica) za
        // naslednjo iteracijo, ker so podatki v v1 vedno razveljavljeni,
        // je izmenjava brez kopiranja lahko učinkovitejša
        swap v0 with v1
    // po zadnji izmenjavi so rezultati v1 sedaj v v0
    return v0[n]

Hirschbergov algoritem združuje to metodo z algoritmom deli in vladaj. Lahko izračuna optimalno urejevalno zaporedje in ne le urejevalne razdalje v enakih asimptotičnih časovnih in prostorskih mejah.

Avtomati

Levenštejnovi avtomati učinkovito določijo, ali ima znakovni niz manjšo urejevalno razdaljo od dane konstante iz danega znakovnega niza.

Približno

Levenštejnovo razdaljo med dvema znakovnima nizoma z dolžinama $n\!\,$ je mogoče izvesti približno na faktor natančno:

$(\log n)^{O(1/\varepsilon )}\!\,,$

kjer je $\varepsilon >0\!\,$ prosti parameter, ki ga je treba nastaviti v času $O(n^{1+\varepsilon })\!\,$.

Računska zahtevnost

Pokazalo se je, da Levenštejnove razdalje dveh znakovnih nizov z dolžinama $n\!\,$ ni mogoče izračunati v času $O(n^{2-\varepsilon })\!\,$ za noben $\varepsilon \!\,$, večji od nič, razen če močna domneva o eksponentnem času ni napačna.

Glej tudi

• agrep
• algoritem Hunta in Szymanskega
• algoritem optimalnega ujemanja
• Apache Lucene – odprtokodni iskalni pogon, ki izvaja urejavalne razdalje
• Damerau-Levenštejnova razdalja
• Dice-Sørensenov koeficient
• diff
• dinamično zvijanje časa
• evklidska razdalja
• geometrija taksija
• Hammingova razdalja
• Jaccardov indeks
• Jaro-Winklerjeva razdalja
• lokacijsko občutljivo razprševanje
• metrični prostor
• MinHash
• najdaljše skupno podzaporedje
• numerična taksonomija
• računska teorija zahtevnosti
• sekvenčna homologija

Viri

• Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). Polylogarithmic approximation for edit distance and the asymmetric query complexity. IEEE Symp. Foundations of Computer Science (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079.
• Backurs, Arturs; Indyk, Piotr (2015). Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC). arXiv:1412.0348. Bibcode:2014arXiv1412.0348B.
• Hirschberg, Dan S. (1975), »A linear space algorithm for computing maximal common subsequences« (PDF), Communications of the ACM (Oddani rokopis), 18 (6): 341–343, CiteSeerX 10.1.1.348.4774, doi:10.1145/360825.360861, MR 0375829, S2CID 207694727
• Hjelmqvist, Sten (26. marec 2012), »Fast, memory efficient Levenshtein algorithm«, codeproject.com (v angleščini)
• Levenštejn, Vladimir Josifovič (1965), Двоичные коды с исправлением выпадений, вставок и замещений символов [Dvojiške kode s popravki izbrisov, vstavkov in zamenjav 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
• 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
• Schulz, Klaus U.; Mihov, Stoyan (2002), »Fast String Correction with Levenshtein-Automata«, International Journal on Document Analysis and Recognition, 5 (1): 67–85, CiteSeerX 10.1.1.16.652, doi:10.1007/s10032-002-0082-8, S2CID 207046453
• Thije, Jan D. ten; Zeevaert, Ludger, ur. (1. januar 2007), Receptive multilingualism: linguistic analyses, language policies, and didactic concepts, Amsterdam | Filadelfija: John Benjamins Publishing Company, ISBN 978-90-272-1926-8, Ob predpostavki, da je razumljivost obratno sorazmerna z jezikovno razdaljo ... vsebinske besede odstotek sorodnikov (povezanih neposredno ali prek sopomenke) ... leksikalna sorodnost ... slovnična sorodnost
• Wagner, Robert A.; Fischer, Michael John (1974), »The String-to-String Correction Problem«, Journal of the ACM, 21 (1): 168–173, doi:10.1145/321796.321811, S2CID 13381535

Zunanje povezave

• Black, Paul E., ur. (14. avgust 2008), »Levenshtein distance«, Dictionary of Algorithms and Data Structures [online] (v angleščini), U.S. National Institute of Standards and Technology, pridobljeno 2. novembra 2016
• Izvedbe Levenštejnove razdalje na Rosetta Code (angleško)