Atstumas Damerau-Levenshteyn • Aleksandras Berdichevsky • Populiariosios mokslinės užduotys "Elementai" • Lingvistika

Atstumas Damerau-Levenshteyn

Automatiškai apdorojant natūralią kalbą (pavyzdžiui, naudojant automatinį rašybos tikrinimą) dažnai reikia nustatyti, kaip skirtingi du rašytiniai žodžiai. Viena iš naudojamų kiekybinių priemonių vadinama Damerau-Levenshtein atstumu – garbei Vladimirui Levenšteinui ir Frederikui Damerau. Levenšteinas išrado būdą, kaip išmatuoti "atstumą" tarp žodžių, ir Damerau, nepriklausomai nuo jo, išskyrė kelias klases, į kurias patenka dauguma klaidingų pamokų.

Užduotis

Atsižvelgiant į porą anglų kalbos žodžių ir Damerau-Levenshteyn atstumą tarp kiekvienos poros žodžių. Kai kurių numerių trūksta.

Keletas žodžiųAtstumas Damerau-Levenshteyn
1.akrasautomobilis2
2.anteaterteatras4
3.bananasauklės3
4.katėdėžė2
5.kokonasgegutė3
6.emporiumsuteikti galios4
7.lankytojasOglė2
8.lyragulėti2
9.gyvenimasmirtis5
10.taškasgriuvėsiai5
11.akmuosonetas3
12.bangaruse3
13.užduotisbrosmė1
14.durpėsjuosta4
15.BabaArabas
16.konkursastonikas
17.ungurysLee
18.kovinissantuoka
19.monarchijademokratija
20.sėdynės atlošasbackseat
21.karasAtsisveikinimas
22.rūkymasligoninė
23.apeea

1 užduotis. Užpildykite ruošinius.

2 užduotis. Pateikite atstumo "Damerau-Levenshteyna" apibrėžimą ir nurodykite, kokios klasės klaidos buvo paskirtos Damerau.

3 užduotis. Atsižvelgiant į du ilgio žodžius m ir n (m > n) Koks yra didžiausias Damerau-Levenshtein atstumas tarp šių žodžių? Mažiausias įmanomas? (Atsakyk savo atsakymus m ir n).

Pastaba Anglų kalbos žinios nėra būtinos problemai išspręsti. Žodžių reikšmės nėra reikšmingos.


Užuomina

Damerau-Levenshtein atstumas tarp dviejų žodžių yra minimalus elementarių operacijų, kurias reikia atlikti norint gauti vieną žodį iš kito, skaičius. Pradinės operacijos yra keturios, ir jos atitinka keturias Damerau klaidų klases. Kokia yra ši operacija?


Sprendimas

Pradėkime nuo 2 užduoties. Damerau-Levenshtein atstumas tarp dviejų žodžių yra minimalus pagrindinių operacijų skaičius, kuris turi būti atliktas norint gauti vieną žodį iš kito. Elementarioji operacija yra tokia: išbraukiamas vienas simbolis; pridėti vieną simbolį; pakeičiant vieną simbolį kita; pertvarkymas dviejų gretimų simbolių. (Jei mes sumažinsime leistinų operacijų skaičių iki trijų, pašalinsime permutaciją, tada gausime priemonę, kuri vadinama tiesiog Levenšteino atstumas.)

Atitinkamai, keturios klaidingos klaidos, kurias Damerau išskyrė kuriant algoritmą, skirtą jų automatinei pataisai, yra simbolio praleidimas; papildomas charakteris; pakeisti simbolį kita; Supainioti dviejų gretimų simbolių tvarką.

Kartais "solvers", atliekantys 2 užduotį, vietoj to stengiasi nustatyti algoritmą, kuris leistų rasti atstumą Damerau-Levenshtein. Tačiau tai yra gana sudėtinga, ir šios užduoties sprendimas visiškai nereikalingas, pakanka apibrėžti pirmiau minėtoje dvasią.

Dabar galime užpildyti 1 užduotį:

Keletas žodžiųAtstumas Damerau-Levenshteyn
15.BabaArabas3
16.konkursastonikas4
17.ungurysLee2
18.kovinissantuoka1
19.monarchijademokratija5
20.sėdynės atlošasbackseat8
21.karasAtsisveikinimas6
22.rūkymasligoninė7
23.apeea2

Kai kurios poros nusipelno papildomos pastabos. Kadangi galite keisti vietas tik kaimyninis simboliai (tai atsiranda iš poros durpėsjuosta sąlyga: atstumas 4, ne 2), atstumas tarp ungurys ir Lee – 2, ne 1.

Kadangi visos operacijos atliekamos su vienu ženklu, o ne dėl savavališkų simbolių sekų (tai iš karto matoma iš poros) durpėsjuosta), atstumas tarp sėdynės atlošas ir backseat – ne 1 (kaip intuityviai atrodo žmogui), o ne 4, nes sprendėjai dažnai atsako, bet 8.

Kita dažna klaida yra manyti, kad atstumas tarp ape ir ea lygus 3. Tie, kurie siūlo tokį sprendimą, daro prielaidą, kad algoritmas juda išilgai linijos griežtai viena kryptimi (iš kairės į dešinę arba iš dešinės į kairę) ir negali būti grąžinamas, tai yra, kai redaguota substrė negalima redaguoti antrą kartą. Jei redaguoti apemes praleidome a ir ištrinta p (gavimo ae), tada, vadovaudamiesi šia logika, mes negalime naudoti permutacijos operacijos, susijusios su a. Tačiau Damerau-Levenshtein atstumo apibrėžtyje nėra tokios ribos (tai matyti iš poros lyra-gulėti), todėl atsakymas vis dar yra 2. Atstumas, apskaičiuotas pagal šį apribojimą, yra dar viena priemonė, kuri kartais vadinama ribotas redakcinis atstumas. Įdomu tai, kad kai kurie interneto algoritmai, paskelbti Damerau-Levenshtein atstumu nustatyti, iš tikrųjų nustato ribotą redakcijos atstumą (matyt, techniškai lengviau jį nustatyti).

Galiausiai užduotis 3 yra tik matematinis pratybas. Akivaizdu, kad Damerau-Levenshtein atstumas negali viršyti ilgesnio žodžio ilgio (pakeičiant visus simbolius, ką galite gauti iš jo), todėl didžiausias atstumas yra m. Mažiausias atstumas yra mn (simbolių, kuriuos reikia pridėti prie trumpo žodžio, kad gautumėte ilgą, skaičius). Dažnai atsakymas yra 1, tačiau jis nėra tinkamas, nes sąlyga reikalauja, kad atsakymas būtų išreikštas m ir n.


Po žodžio

Įdomu tai, kad nei Levenšteinas, nei Damerau nesutiko su užduotimi "įvertinti dviejų stygų panašumo laipsnį".

1965 m. Levenšteinas laikė dvejetainių kodų savybes, galinčias pataisyti tam tikrą pakeitimų skaičių. s (V. I. Levenshtein, 1966. Dvinariniai kodai, galintys ištaisyti ištrynimus, įterpimus ir pasikeitimus). Pagal dvejetainis kodas tai reiškia savavališką fiksuoto ilgio žodžių rinkinį l dvejetainėje abėcėlėje (ty, simbolių 0 ir 1 abėcėlė), po gebėjimas pataisyti – galimybė gauti bet kokį ilgio žodį l vieno ir vienintelio konkretaus kodo žodis ne daugiau kaip s pokyčiai ir pagal pokyčiai – Įterpti, ištrinti ir pakeisti.

Damerau 1963 m. Išsprendė konkretesnę problemą – kaip tobulinti informacijos paieškos sistemą, mokyti kompiuterį atpažinti klaidas (Fredas J. Damerau. Technika kompiuterio aptikimui ir rašybos klaidų taisymui). Dekoratyvinė korekcija, pažymėta Damerau, netrukus taptų neįmanoma, nes didėja leksinės informacijos, kurią apdoroja kompiuteriai, kiekis. Jis nustatė, kad daugiau nei 80% žodžių, kuriuos sistema negalėjo atpažinti dėl klaidingų klaidų, pateko į vieną iš keturių klasių (trūksta vienos raidės, viena raidė yra nereikalinga, viena raidė pakeičiama kita, pakeičiamos dvi gretimos raidės) ir sukurtas algoritmas kuris leido ištaisyti daugumą tokių klaidų.

1963 m. Frederiko Damerau straipsnio iliustracija

Tačiau istorijoje jų vardai iš esmės buvo susiję su atstumais. Levenšteino atstumas tikriausiai yra labiausiai žinomas ir plačiai naudojamas dviejų linijų palyginimas. Damerau-Levenshtein atstumas yra naudojamas rečiau (ir, kaip skaitytojas gali patikrinti net pavyzdžių iš problemos, dažnai sutampa su klasikiniu Levenshtein atstumu). Kitas žinomas atstumas yra Hammingo atstumas (garsus mokslininkas Richardas Hammingas, kuris sunkiai dirbo klaidų taisymui). Jis naudojamas tik palyginti du tokio paties ilgio žodžius ir yra tiesiog apibrėžiamas kaip reikalingų pakeitimų skaičius. (Hammingo vardu taip pat yra prestižinis medalis, skiriamas kasmet už jo indėlį į kompiuterių mokslą, kurį Levenshtein gavo 2006 m.).

Žodžio ilgis yra papildomas veiksnys nustatant atstumą. Kaip mes žinome iš trečiosios užduoties, maksimalus atstumas priklauso nuo ilgiausio žodžio ilgio. Žodžių tarpai ir tu esi – 2, ir tarp žodžių obelis ir obelis – 3, nors asmeniui yra akivaizdu, kad pirmoje poroje žodžiai yra visiškai kitokie, o antroji pora – vienodi. Todėl atstumas yra dažnas normalizuojasi, tai yra padalinta iš ilgiausio žodžio ilgio.Normalizuoto atstumo reikšmė yra nuo 0 iki 1 pora tu esi tai yra 1, ir pora obelinė-obelis – 0,375.

Visi atstumai iki šiol yra klasėje. redakciniai atstumai, t. y. nustatoma pagal būtinų pagrindinių operacijų skaičių. Iš tikrųjų vadinama operacijų seka redakcinis receptas. Dėl Levenshtein atstumo redakcinį receptą galima rasti naudojant Wagner-Fisher algoritmą (žr. Wagner-Fischer algoritmą).

Akivaizdu, kad kai kuriais atvejais Damerau-Levenshtein atstumas grąžina netobulų rezultatą. Mes jau matėme šią problemą durpės ir juosta, Lee ir ungurys ir ypač sėdynės atlošas ir backseat pasirodytų toli nuo to, ko norėtųsi, bet tai tik viena iš galimų problemų.

Yra du dešimtys kitų būdų, kaip išmatuoti dviejų eilučių panašumą (čia mes rekomenduojame trumpai apžvelgti daugybę skirtingų būdų arba išsamiau apibūdinti kelias pagrindines metodų klases čia).

Vienoje bendroje atstumų klasėje pagrindinis vaidmuo tenka suderinimas sekas. Skirtingai nuo klasikinių redakcinių atstumų, metodų suderinimas kilo iš bioinformatikos, tai yra, jie iš pradžių buvo sukurti ne teksto apdorojimui, o baltymų ir nukleotidų sekas palyginimui. Žymūs pavyzdžiai Algoritmas Needleman-Wunsch. Tai yra panašus į Levenshtein atstumo apskaičiavimą, tačiau operacijas galima priskirti skirtingas svoris. Be to, kiekvienai ženklų porai galite nurodyti laipsnis jų panašumai (tarkim, pavyzdžiui, kad b labiau patinka pkaip apie a) Pagaliau derinimo tikslais eilutė leidžiama. atsikratyti (gaunate, pavyzdžiui, CRATE / C-AT), už kurį numatoma skirti tam tikros vertės baudą.

Kitas sprendimas – pateikti eilutę kaip vektorių. Tai gali būti padaryta, pavyzdžiui, nustatant kai kuriuos kalba (žodžių rinkinys), tada skaičiuojant, kiek kartų kiekvienas konkrečios kalbos žodis susiduria su tam tikros eilutės substrine. Jei, pavyzdžiui, nurodome kalbą {aaa, aab, aba, abb, baa, Babas, bba, bbb} ir vektorizuoti žodžius Ababba ir bababb, mes gauname du aštuonių matmenų vektorius (0, 0, 1, 1, 0, 1, 1, 0) ir (0, 0, 1, 1, 0, 2, 0, 0) (pavyzdys iš čia). Siekiant palyginti du vektorius, yra daug matematinių metodų: galite apskaičiuoti kampo tarpusavio santykį (žr. Kosinino panašumą), apskaičiuoti Euklido atstumą arba naudoti kai kurias sudėtingesnes priemones.

Yra daugiau konkrečių sprendimų.Pavyzdžiui, yra būdų palyginti garsas du žodžiai, pagrįsti jų įrašais: tai yra naudinga tikrinant rašybą, nes žmonės linkę tiksliai supainioti kaip skambantys žodžiai. Neseniai sukurtas metodas Dažniausiai k simboliai reiškia žodį kaip seką k labiausiai paplitę simboliai tam tikruose žodžiuose, nurodant jų dažnumą, o tada ypatingu būdu palygina šiuos vaizdus. Taigi, pavyzdžiui, kada k = 2 žodžiai Lowenstein bus pristatytas kaip e3n2ir žodis Damerau – kaip a2d1 (D yra laikomas pirmuoju iš vienodo dažnio simbolių). Patikrinimas, kad šios priemonės kūrėjai (taikydami skirtingus to paties algoritmo atstatus tekstų autorystės nustatymui) parodė, kad jis yra šiek tiek prastesnis už Levenshteino atstumą, bet skaičiavimui reikia mažiau laiko.

Vladimiras Levenshteinas (Trečias kairysis) 2003 m. Bielefeldo universitete (Vokietija) priėmimo metu

Paskutinis pavyzdys ypač ryškiai rodo, kad bet koks bandymas kiekybiškai įvertinti dviejų žodžių panašumą visada sukelia tam tikrą informacijos praradimą (Levenšteino atstumas "nemato" panašumo sėdynės atlošas ir backseat; Aukščiau aprašytas vektorizacijos metodas neatsižvelgia į eilutės substratų eiliškumą; paskutinis apibūdintas metodas paprasčiausiai atmeta didelę ženklų dalį ir pan.). Taigi, bet kokios priemonės atveju bus žodžių poros, kurių prasmė nebus visiškai intuityvi. Tai, žinoma, yra atsižvelgiama renkantis priemonę, kuri labiausiai tinka tam tikrai užduočiai, ar tai yra klaidų pataisa, teksto klasifikacija, kalbinės priklausomybės apibrėžimas, tekstinių stimulų palyginimas psichologinių eksperimentų metu, DNR palyginimas ar kas nors kitas.

Ši užduotis buvo naudojama Latvijos olimpiadoje kalbotyros srityje 2015 metais.


Like this post? Please share to your friends:
Parašykite komentarą

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: