Levenshteini kauguse visualiseerija

Sisesta kaks sõnet, et näha nende Levenshteini (redigeerimis-)kaugust — minimaalset arvu ühe tähemärgi muudatusi, mis on vaja ühe teisendamiseks teiseks.

Näidisarvutus — Levenshteini kauguse visualiseerija

Redigeerimiskaugus	3
Sarnasus	57,14%

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Levenshteini kauguse visualiseerija

Levenshteini kaugus kahe sõne vahel on vähim arv ühe märgi muudatusi, mis muudab ühe teiseks, kusjuures muudatus on lisamine, kustutamine või asendamine. See on miinimum üle kõigi võimalike tegemisviiside — ja just see teeb ta silma järgi raskeks ja ruudustikuga lihtsaks: muudatuste järjestusi on hoomamatult palju ning see meetod leiab lühima, ilma et loetleks neist ainsatki.

Mida iga sümbol tähendab

m, n: kahe sõne, A ja B, pikkused.
D(i, j): odavaim viis muuta A esimesed i märki B esimesteks j märgiks. Üks lahter sellel lehel olevast tabelist.
[aᵢ ≠ bⱼ]: maksab 1, kui need kaks märki erinevad, ja 0, kui nad langevad kokku — asendamise hind, mis kaob, kui asendada pole midagi.
d: vastus, D(m, n): parempoolne alumine lahter.

Kust valem tuleb

Otsustage, mida üks lahter tähendab, enne kui ühtegi täidate. Olgu D(i, j) vähim muudatuste arv, mis muudab A esimesed i märki B esimesteks j märgiks. Otsitav arv on D(m, n) ja iga teine lahter on sama küsimuse väiksem variant.
Servad ei nõua mõtlemist. Et B esimesed j märki tühjast kohast üles ehitada, tuleb kõik j lisada, seega D(0, j) = j. Et A esimesed i märki tühjaks taandada, tuleb kõik i kustutada, seega D(i, 0) = i. See on ruudustiku ülemine rida ja vasak veerg — ja seepärast nad lihtsalt loendavad.
Nüüd samm, mis teeb kogu töö. Võtke suvaline optimaalne käikude jada D(i, j) jaoks ja vaadake ainult selle viimast käiku. Võimalusi on täpselt kolm: see kustutas aᵢ, jättes ülesandeks D(i−1, j); see lisas bⱼ, jättes D(i, j−1); või sidus aᵢ ja bⱼ paari, jättes D(i−1, j−1). Igaüks neist on lahter, mille olete juba täitnud.
Seega on lahter neist kolmest odavaim: D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] ). Täitke ruudustik vasakult paremale ja ülalt alla, siis on igasse lahtrisse jõudes selle kolm naabrit juba teada. See ongi kogu algoritm — m × n lahtrit, igaühes kolm võrdlust.

Kuidas nähtut lugeda

Ruudustik sellel lehel ongi see tabel. Read on A, veerud on B, ning lisarida ja -veerg üleval vasakul on 2. sammu tühjad eesliited — seepärast nad loendavad 0, 1, 2, 3. Lahtri toon on tema väärtus: kahvatu diagonaalne koridor on seal, kus kaks sõnet veel odavalt kokku langevad. Liigutage kursor lahtri kohale või puudutage seda ning allolev paneel kirjutab just selle lahtri jaoks 3. sammu lahti — kolm kandidaati, igaüks oma arvutusega, võitja esile tõstetud. Värviline joon on üks optimaalne tee, mis on parempoolsest alumisest nurgast tagasi jälitatud, ja selle all olev joondusriba on seesama tee märkidena välja kirjutatud.

Eeldab: Iga muudatus maksab täpselt 1 ja märke võrreldakse täpse võrdsuse alusel — ei mingit suur- ja väiketähtede ühtlustamist, Unicode’i normaliseerimist ega arusaama sellest, millised märgid üksteise moodi välja näevad. Kaks tagajärge on siin näha. Siin loendatakse UTF-16 koodiühikuid, mitte seda, mida te tähtedeks nimetaksite: kirjutage lahtrisse üksainus emoji ja tabel on 3 × 1, sest üks emoji on kaks ühikut ja selle kustutamine maksab 2. Ja café eelkomponeeritud é-ga võrrelduna sõnega café, mis on kirjutatud kui e pluss kombineeruv rõhumärk, annab kauguse 2, kuigi ekraanil näevad mõlemad täpselt ühesugused välja.
Ei kehti, kui: Ruudustikus on m × n lahtrit, seega töö kasvab pikkuste korrutisena. Kahe sõna puhul on see hea ja miljoni kirjega sõnaraamatu vastu päringu tegemiseks lootusetu — see on miljon ruudustikku. Loomulik vastus oleks nutikam algoritm, ja üllatus on, et sisuliselt ühtegi pole: Backurs ja Indyk näitasid 2015. aastal, et tugevalt alamruutaegne redigeerimiskaugus lükkaks ümber tugeva eksponentsiaalaja hüpoteesi. Päris õigekirjakontrollid ei alista seda piiri, vaid väldivad seda — katkestavad kohe, kui kaugus ületab väikese lävendi, või indekseerivad nii, et peaaegu ühtegi kandidaati ei võrreldagi.

Ruudustik on väike, sest iga alamküsimus esitatakse ainult ühe korra 🖖

Võimalike redigeerimisjärjestuste läriotsimine on lootusetu — järjestuste arv plahvatab sõnade pikkuse kasvades. Lahendus, mis olukorra päästab, seisneb selles, et igal prefiksite paaril on täpselt üks parim vastus ning see vastus ei muutu kunagi, olenemata sellest, mis sõnes edaspidi juhtub. Seega järjestuste uurimise asemel täidetakse ruudustik: üks rida esimese sõna iga tähe kohta, üks veerg teise sõna iga tähe kohta, lisaks tühja prefiksit tähistav tühi rida ja veerg. Sõna kitten teisendamine sõnaks sitting tähendab seega 7 × 8 = 56 ruutu, millest igaühe tulemus otsustatakse kolme juba täidetud naabri põhjal, ning vastus 3 ootab all paremas nurgas. Töömaht kasvab kahe pikkuse korrutisega, mitte redigeerimisviiside arvuga.

Vahetus maksab kaks muudatust, kuni te teisiti ei ütle 🖖

Kirjutage form ja from ning Levenshtein vastab 2. Tal pole aimugi, et tähed vahetati ära, seega maksab ta kahe asenduse eest. Vahetusse läinud tähed on aga ühed levinumad näpuvead üldse, ja just seepärast lisas Damerau neljanda käigu: kui kaks märki, mida vajate, on täpselt need kaks, mis teil vastupidises järjekorras on, võtke mõlemad ühe hinnaga. Vahetage ülal hinnamudelit ja seesama paar maksab 1. Sõnades ei muutunud midagi — muutus hinnakiri. Seda tasub meeles pidada kõikjal, kus redigeerimiskaugust kasutatakse sarnasusskoorina, sest see arv on sama palju valitud hinnamudeli omadus kui kahe sõne oma.

Kiire versioon ei oska seda pilti joonistada 🖖

Iga lahter vajab ainult enda kohal olevat rida ja endast vasakul olevat lahtrit, nii et kaugemal tagapool olevad read ei võida püsimisest midagi. Päris teostused võtavad selle pakkumise vastu ja hoiavad kogu tabeli asemel kahte rida, mis viib mälukulu m × n pealt min(m, n) peale — kahe tuhandetähelise sõne puhul umbes miljonilt lahtrilt kahele tuhandele. Loobutakse aga täpselt sellest, mis on ülal joonistatud. Kaugus jääb viimasesse lahtrisse alles, kuid tee selleni elas ridades, mis üle kirjutati, nii et kaherealine teostus oskab öelda, et kaks sõnet on kolme muudatuse kaugusel, aga mitte seda, millise kolme. Tee tagasisaamine ilma täieliku ruudustikuta on raskem, kui paistab; Hirschberg lahendas selle 1975. aastal, lõigates tabeli keskelt pooleks ja laskudes rekursiivselt mõlemasse poolde.

Ülesanne täielikult lahendatud

Odavaim muutmisjada kitten muutmiseks sõnaks sitting 5 sammu
Teisenda kitten sõnaks sitting. Leia vähima maksumusega teisenduste jada ja tõesta, et odavamat ei ole olemas — seejärel arvuta, mida see maksab, kui teine sõna on terve sõnastik.
1. Rekurrentne seos ongi kogu algoritm. Iga lahter küsib, mida maksab siia jõudmine kustutamise, lisamise või kahe praeguse märgi kohakuti seadmise teel — viimane võimalus on tasuta, kui need ühtivad. Lahter vajab vaid kolme naabrit üleval ja vasakul, seega täidab tabeli üks läbivaatus vasakult paremale.
  
  $d_{i, j} = min ⎩ ⎨ ⎧ d_{i - 1, j} + 1 d_{i, j - 1} + 1 d_{i - 1, j - 1} + [a_{i} \neq = b_{j}]$
2. Enne millegi täitmist piira vastuse vahemik. Pikkused erinevad ühe võrra, seega on vähemalt üks lisamine vältimatu; ja sõna täielik ümberkirjutamine maksab 7. Vastus jääb nende vahele, mis välistab juba enamiku pakkumisi.
  
  $∣ a ∣ - ∣ b ∣ = 1 \leq d \leq max (∣ a ∣, ∣ b ∣) = 7$
3. Kolm teisendust teevad töö ära: asenda k → s, asenda e → i, lisa g. Igaüks on üksik lubatud teisendus ja ahel lõpeb sihtmärgil.
  
  $k \underline{i} tten \to s \underline{i} tten \to sitt \underline{i} n \to sitting$
4. Kolme teisenduse esitamine tõestab vaid seda, et kaugus on kõige rohkem 3. Tabel tõestab, et see on täpselt 3, sest iga tee alumisse paremasse nurka saab hindepunktid ja igas lahtris teel võetakse miinimum. See ongi erinevus vastuse leidmise ja selle ületamatuse teadmise vahel.
  
  $d = 3, similarity = 1 - \frac{3}{7} = 0.5714 = 57.14%$
5. Maksumus on üks lahter märgipaari kohta — siin 42, mis pole midagi. 100 000-sõnalise sõnastiku puhul, kus iga sõna on seitse tähte pikk, teeb see üheainsa otsingu jaoks üle nelja miljoni lahtri uuendamise.
  
  $Θ (∣ a ∣ ∣ b ∣) = 6 \times 7 = 42 cells; d (a, c) \leq d (a, b) + d (b, c)$
Vastus

Tööriist väljastab tulemuseks 3 ja sarnasuseks 57,14%, mis on 1 − 3/7: pikema sõnaga normaliseeritud kaugus. Mõlemad pärinevad tabelist, mille saab käsitsi täita minutiga. See, mis ei skaalu, on tabel — töömaht on Θ(mn), seega mõlema sõne pikkuse kahekordistamine neljakordistab selle, ning iga õigekirjakontroll, mida olete kasutanud, on üles ehitatud nii, et seda vältida. Väljapääs ei ole kiirem tabel. Väljapääs peitub selles, et Levenshteini kaugus rahuldab kolmnurga võrratust, seega d(a, c) ≤ d(a, b) + d(b, c) võimaldab indeksil tõestada kandidaadi liiga suurt kaugust ilma seda kaugust kunagi mõõtmata.

$d (kitten, sitting) = 3, 1 - \frac{3}{7} = 57.14%$

Allikad (4)

The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.

42Mathi meeskond · Uuendatud 2026-05-21

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

kitten → sitting - kitten → sitting on õpikunäide ja vastus on 3: kaks asendust ja üks lisamine, sarnasus 57,14%
book → back - book → back on 2 sammu kahe neljatähelise sõna vahel, mida näidatakse sarnasusena 50,00%
Saturday → Sunday - Saturday → Sunday nõuab 3 muudatust ja annab sarnasuseks 62,50%, neist kaks on kustutamised
form → from (vahetus) - form → from on Damerau–Levenshteini järgi üksainus vahetus, mille tööriist loeb sarnasuseks 75,00%
DNA võrdlus - GATTACA → GCATGCG nõuab 4 sammu ja 42,86% — sama mõõt järjestusandmetel