Afstand Damerau-Levenshteyn • Alexander Berdichevsky • Populære videnskabsopgaver på "Elements" • Lingvistik

Afstand Damerau-Levenshteyn

Ved automatisk behandling af et naturligt sprog (f.eks. Med automatisk stavekontrol) er det ofte nødvendigt at bestemme, hvor forskellig de to skriftlige ord er. En af de kvantitative foranstaltninger, der anvendes til dette kaldes Damerau-Levenshtein afstanden – til ære for Vladimir Levenshtein og Frederick Damerau. Levenshtein opfandt en måde at måle afstanden mellem ord på, og Damerau, uafhængigt af ham, udpeget flere klasser, at de fleste fejltryk falder ind.

opgave

I betragtning af parret af engelske ord og afstanden mellem Damerau-Levenshteyn mellem ordene i hvert par. Nogle tal mangler.

Et par ordAfstand Damerau-Levenshteyn
1.acrebil2
2.myreslugerteater4
3.bananbarnepige3
4.katkasse2
5.puppegøg3
6.Emporiumbemyndige4
7.goertrold2
8.Lyralægge2
9.livdød5
10.punkthøjreb5
11.stenSonnet3
12.bølgekneb3
13.opgavebrosme1
14.tørvbånd4
15.babaarab
16.konkurrencentoner
17.ålLee
18.martialægteskabelig
19.monarkidemokrati
20.ryglænbagsæde
21.krigsførelsefarvel
22.rygninghospital
23.abeea

Opgave 1. Udfyld emnerne.

Opgave 2. Giv en definition af afstanden Damerau-Levenshteyna og foreslå hvilke klasser af typografier der er tildelt Damerau.

Opgave 3. Gives to ord med længder m og n (m > n). Hvad er den maksimale afstand mellem Damerau-Levenshtein mellem disse ord? Mindst muligt? (Udtryk dine svar i m og n).

Bemærk. Kendskab til engelsk er ikke påkrævet for at løse problemet. Betydninger af ord er irrelevante.


hjælpe

Damerau-Levenshtein afstanden mellem to ord er det mindste antal elementære operationer, der skal udføres for at få et ord fra et andet. Elementære operationer er fire, og de svarer til fire klasser af typografier Damerau. Hvad er denne operation?


beslutning

Lad os starte med opgave 2. Damerau-Levenshtein afstanden mellem to ord er det mindste antal elementære operationer, der skal udføres for at få et ord fra et andet. De elementære operationer er som følger: sletning af en enkelt karakter; tilføj et tegn erstatte et tegn med en anden; permutation af to tilstødende tegn. (Hvis vi reducerer antallet af tilladte operationer til tre, fjerner permutationen, så får vi en foranstaltning, der simpelthen hedder Levenshtein afstand.)

Følgelig er de fire klasser af typografier, som Damerau udpegede, når de udviklede en algoritme til deres automatiske korrektion, udeladelsen af ​​et symbol; ekstra karakter; erstatte en karakter med en anden; Den forvirrede rækkefølge af to tilstødende tegn.

Nogle gange forsøger solvere, der udfører opgave 2, i stedet at definere en algoritme, der vil tillade at finde afstanden Damerau-Levenshtein. Dette er dog ret vanskeligt, og for løsningen af ​​denne opgave er det fuldstændig unødvendigt, det er nok at give en definition i ovenstående ånd.

Nu kan vi afslutte opgave 1:

Et par ordAfstand Damerau-Levenshteyn
15.babaarab3
16.konkurrencentoner4
17.ålLee2
18.martialægteskabelig1
19.monarkidemokrati5
20.ryglænbagsæde8
21.krigsførelsefarvel6
22.rygninghospital7
23.abeea2

Nogle par fortjener en ekstra kommentar. Da du kun kan bytte steder tilstødende tegn (det følger af parret tørvbånd i tilstanden: afstand 4, ikke 2), afstanden mellem ål og Lee – 2, ikke 1.

Da alle operationer udføres på enkelt tegn, og ikke på vilkårlige sekvenser af tegn (dette er igen tydeligt fra parret tørvbånd), afstanden mellem ryglæn og bagsæde – ikke 1 (som det intuitivt synes at være menneske), og ikke 4, som solvere ofte svarer, men 8.

En anden almindelig fejl er at antage, at afstanden mellem abe og ea svarer til 3. De, der foreslår en sådan løsning, antager, at algoritmen bevæger sig langs linjen strengt i en retning (fra venstre til højre eller fra højre mod venstre) og kan ikke returneres, det vil sige, når den redigerede substring ikke kan redigeres en anden gang. Hvis, redigering abevi savnede en og slettet p (modtaget ae), så kan vi ikke længere bruge en permutationsoperation, der involverer, efter denne logik en. Definitionen af ​​Damerau-Levenshtein-afstanden indeholder dog ikke en sådan grænse (dette kan ses fra parret Lyra-lay), så svaret er stadig 2. Afstanden, der beregnes ud fra denne begrænsning, er et andet mål, som undertiden kaldes begrænset redaktionel afstand. Interessant nok bestemmer nogle af de algoritmer, der er tilgængelige på internettet, som erklæres for at bestemme afstanden Damerau-Levenshtein, faktisk den begrænsede redaktionelle afstand (tilsyneladende fordi det er teknisk lettere at bestemme).

Endelig er opgave 3 en rent matematisk øvelse. Damerau-Levenshtein afstanden kan naturligvis ikke overstige længden af ​​et længere ord (ved at erstatte alle tegnene, alt hvad du kan få fra det), så den maksimale afstand er m. Mindste afstand er mn (antallet af tegn du skal tilføje til det korte ord for at få en lang en). Svaret er ofte 1, men det er ikke egnet, da betingelsen kræver, at svaret udtrykkes gennem m og n.


efterskrift

Det er nysgerrig, at hverken Levenshtein eller Damerau satte sig til den umiddelbare opgave at "måle graden af ​​lighed mellem to strenge".

Levenshtein i 1965 betragtede egenskaberne for binære koder, der er i stand til at korrigere et givet antal ændringer. s (V. I. Levenshtein, 1966. Binære koder, der kan korrigere sletninger, indsætninger og reverseringer). under binær kode det betyder et vilkårligt sæt ord med fast længde l i det binære alfabet (dvs. alfabetet med tegn 0 og 1), under evnen til at rette op mulighed for at få noget ord af længde l af et og kun et ord af en given kode i ikke mere end s ændringer og under forandring – indsæt, slet og erstat

Damerau i 1963 løste et mere specifikt problem – hvordan man forbedrer informationssøgningssystemet, lærer computeren at genkende fejl (Fred J. Damerau. En teknik til computerens detektion og korrektion af stavefejl). Manuel korrektion, noteret Damerau, bliver snart umulig på grund af stigningen i mængden af ​​leksikalske oplysninger, som computere behandler. Han fandt ud af, at mere end 80% af ordene, som systemet ikke kunne genkende på grund af typografier, faldt i en af ​​fire klasser (et bogstav mangler, et bogstav er overflødigt, et bogstav erstattes af en anden, to tilstødende breve byttes) og udviklet en algoritme som fik lov til at korrigere flertallet af sådanne trykfejl.

Illustration fra Frederick Dameraus 1963 artikel

I historien forblev deres navne imidlertid primært relateret til afstande. Levenshtein afstand er nok den mest berømte og udbredte måde at sammenligne to linjer. Damerau-Levenshtein-afstanden bruges mindre ofte (og som læseren kan bekræfte, selv med eksempler fra problemet, falder ofte sammen med den klassiske Levenshtein-afstand). En anden kendt afstand er Hamming-afstanden (til ære for den berømte forsker Richard Hamming, som arbejdede hårdt på at rette fejl). Det bruges kun til at sammenligne to ord af samme længde og er simpelthen defineret som antallet af nødvendige substitutioner. (Hammings navn bærer også den prestigefyldte medalje tildelt hvert år for sit bidrag til datalogi, som Levenshtein modtog i 2006.)

Ordlængde er en ekstra faktor ved bestemmelse af afstande. Som vi ved fra den tredje opgave afhænger den maksimale afstand af længden af ​​det længste ord. Ordafstand jeg og du er – 2, og mellem ord æbletræ og æbletræ – 3, mens det er indlysende for en person, at i det første par er ordene helt forskellige, og i det andet par er de ens. Derfor er afstanden ofte normaliseret, der er divideret med længden af ​​det længste ord.Værdien af ​​den normaliserede afstand er mellem 0 og 1, for et par jegdu er det er 1, og for et par æble-æbletræ – 0,375.

Alle de afstande, der er opført hidtil, tilhører klassen. redaktionelle afstande, det vil sige bestemt ved antallet af nødvendige elementære operationer. Faktisk kaldes rækkefølgen af ​​operationer, der skal udføres redaktionel recept. For Levenshtein-afstanden kan den redaktionelle recept findes ved hjælp af Wagner-Fisher-algoritmen (se Wagner-Fischer-algoritmen).

Det er klart, at Damerau-Levenshtein afstanden i nogle tilfælde giver et ufuldstændigt resultat. Vi har allerede set i problemet det tørv og bånd, Lee og ål og især ryglæn og bagsæde vise sig at være længere fra hinanden end man vil gerne, men det er kun et af de mulige problemer.

Der er dusinvis af andre måder at måle ligheden mellem to linjer (vi kan anbefale et kort overblik over mange forskellige måder her eller en mere grundig beskrivelse af flere nøgleklasser af metoder her).

I en fælles klasse afstande er nøglerollen spillet af tilpasning sekvenser. I modsætning til klassiske redaktionelle afstande, metoder tilpasning kom fra bioinformatik, det vil sige, at de oprindeligt blev udviklet ikke til tekstbehandling, men til sammenligning af protein og nukleotidsekvenser. Bemærkelsesværdige eksempler er Needleman-Wunsch-algoritmen. Det ligner beregningen af ​​Levenshtein-afstanden, men operationer kan tilskrives forskellig vægt. Derudover for hvert par tegn, du kan angive grad af deres ligheder (det vil sige for eksempel det b mere som pend på en). Til sidst er strengen tilladt til justering. rive af (modtager f.eks. noget som CRATE / C-AT), for hvilket en straf af en given værdi antages.

En anden løsning er at præsentere strengen som en vektor. Dette kan f.eks. Gøres ved at indstille nogle sprog (sæt ord) og derefter tælle hvor mange gange hvert ord af et givet sprog opstår som en substring af en given streng. Hvis vi for eksempel angiver et sprog {aaa, AaB, aba, abb, baa, bab, BBA, bbb} og vektoriser ord ababba og bababb, vi får to ottedimensionale vektorer (0, 0, 1, 1, 0, 1, 1, 0) og (0, 0, 1, 1, 0, 2, 0, 0) (et eksempel herfra). For at sammenligne to vektorer er der mange matematiske metoder: Du kan beregne cosinus af vinklen mellem dem (se Cosine-lighed), beregne den euklidiske afstand eller bruge nogle af de mere sofistikerede foranstaltninger.

Der er mere specifikke løsninger.Så for eksempel er der måder at sammenligne klingende to ord, baseret på deres rekord: dette er nyttigt, når du kontrollerer stavemåden, da folk har en tendens til at forvirre præcis som lydende ord. Nyligt udviklet metode Mest hyppige k tegn repræsenterer et ord som en sekvens k De hyppigste symboler i et givet ord med en angivelse af deres frekvens, og derefter på en særlig måde sammenligner disse repræsentationer. Så, for eksempel, hvornår k = 2 ord Lowenstein vil blive præsenteret som e3n2og ordet Damerau – hvordan a2D1 (D er taget som den første af de samme frekvens symboler). Den kontrol, som udviklerne af denne foranstaltning udførte (ved hjælp af forskellige afstande i samme algoritme til bestemmelse af tekstforfatterskab) viste, at den er lidt underordnet Levenshtein-afstanden nøjagtigt, men det tager mindre tid at beregne.

Vladimir Levenshtein (tredje venstre) i receptionen ved Universitetet i Bielefeld (Tyskland) i 2003

Det sidste eksempel viser især levende, at ethvert forsøg på at kvantificere ligheden mellem to ord altid medfører noget tab af information (Levenshtein-afstanden "ser ikke" ligheden ryglæn og bagsæde; Den ovenfor beskrevne vektoriseringsmetode tager ikke hensyn til rækkefølgen af ​​understrengene i strengen; den sidst beskrevne metode kasserer simpelthen en væsentlig del af tegnene osv.). Således vil der for enhver foranstaltning være par ord, hvor dets betydning ikke vil være helt intuitiv. Dette er naturligvis taget i betragtning ved valg af den foranstaltning, der passer bedst til en bestemt opgave, det være sig en typografisk korrektion, tekstklassificering, definition af sprogrelateret sammenhæng, sammenligning af tekststimuli i psykologiske eksperimenter, DNA-sammenligning eller noget andet.

Opgaven blev brugt på den lettiske Olympiad i Lingvistik i 2015.


Like this post? Please share to your friends:
Skriv et svar

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