Levenshtein afstand

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. april 2022; checks kræver 4 redigeringer .

Levenshtein-afstanden ( rediger afstand , rediger afstand ) er en metrik , der måler den absolutte forskel mellem to sekvenser af tegn. Det er defineret som det mindste antal enkelttegnsoperationer (nemlig indsættelser, sletninger, substitutioner), der kræves for at transformere en sekvens af tegn til en anden. Generelt kan de operationer, der anvendes i denne transformation, tildeles forskellige priser. Udbredt i informationsteori og datalingvistik .

Problemet blev først stillet i 1965 af den sovjetiske matematiker Vladimir Levenshtein , da han studerede sekvenser [1] , senere blev et mere generelt problem for et vilkårligt alfabet forbundet med hans navn. Et stort bidrag til undersøgelsen af spørgsmålet blev ydet af Dan Gasfield [2] . $0-1$

Ansøgning

Levenshtein-afstanden og dens generaliseringer bruges aktivt:

at rette fejl i et ord (i søgemaskiner, databaser, ved indtastning af tekst, med automatisk genkendelse af scannet tekst eller tale).
at sammenligne tekstfiler med diff -værktøjet og lignende. Her spilles rollen som "karakterer" af strenge, og rollen som "strenge" spilles af filer.
i bioinformatik for at sammenligne gener , kromosomer og proteiner .

Fra et applikationssynspunkt har definitionen af afstanden mellem ord eller tekstfelter ifølge Levenshtein følgende ulemper:

Når ord eller dele af ord ombyttes, opnås forholdsvis store afstande;
Afstandene mellem helt forskellige korte ord viser sig at være små, mens afstandene mellem meget ens lange ord viser sig at være signifikante.

Redaktionel instruktion

En redaktionel instruktion er en sekvens af handlinger, der er nødvendige for at opnå den anden fra den første linje på den kortest mulige måde. Normalt betegnes handlinger som følger: D ( eng. delete ) - delete, I (eng. insert) - insert, R ( replace ) - replace, M ( match ) - match.

For eksempel, for 2 strenge "CONNECT" og "CONEHEAD" kan du bygge følgende konverteringstabel:

M	M	M	R	jeg	M	R	R
C	O	N	N		E	C	T
C	O	N	E	H	E	EN	D

At finde kun Levenshtein-afstanden er en lettere opgave end også at finde den redaktionelle recept (se nedenfor for flere detaljer).

Generaliseringer

Forskellige transaktionspriser

Operationspriser kan afhænge af operationstypen (indsæt, slet, erstat) og/eller af de involverede tegn, hvilket afspejler den forskellige sandsynlighed for mutationer i biologien [3] , forskellig sandsynlighed for forskellige fejl ved indtastning af tekst osv. I den generelle sag:

w(a, b) — prisen for at erstatte karakter a med karakter b
w(ε, b) — omkostninger ved at indsætte tegn b
w(a, ε) — prisen for sletning af symbol a

Det er nødvendigt at finde en sekvens af substitutioner, der minimerer de samlede omkostninger. Levenshtein-afstanden er et særligt tilfælde af dette problem for

w(a, a) = 0
w(a, b) = 1 for a≠b
w(ε, b) = 1
w(a, ε) = 1

Både et specialtilfælde og et problem for vilkårlig w løses af Wagner-Fisher-algoritmen nedenfor. Her og nedenfor antager vi, at alle w er ikke-negative, og trekantens ulighed gælder : at erstatte to på hinanden følgende operationer med én øger ikke de samlede omkostninger (for eksempel at erstatte symbolet x med y, og så er y med z nej bedre end umiddelbart x med z).

Transponering

Hvis vi tilføjer en transponering til listen over tilladte operationer (to tilstødende tegn er byttet om), får vi Damerau-Levenshtein-afstanden . Den har også en algoritme, der kræver O(MN)-operationer. Damerau viste, at 80% af menneskelige tastefejl er transpositioner. Derudover bruges afstanden Damerau-Levenshtein også i bioinformatik.

Formel

Her og nedenfor antages det, at elementerne i strenge er nummereret fra den første, som det er sædvanligt i matematik, og ikke fra nul, som det er sædvanligt i mange programmeringssprog.

Lad og være to strenge (af længde og henholdsvis) over et eller andet alfabet , så kan redigeringsafstanden (Levenshtein-afstanden) beregnes ved hjælp af følgende rekursive formel $S_{1}$ $S_{2}$ $M$ $N$ ${\rm {d}}(S_{1},S_{2})$

$\ {\rm {d}}(S_{1},S_{2})=D(M,N)$ , hvor

$D(i,j)=\venstre\{{\begin{array}{llcl}0,&&&i=0,\ j=0\\i,&&&j=0,\ i>0\\j,&&&i =0,\ j>0\\\min\{\\&D(i,j-1)+1,\\&D(i-1,j)+1,&&j>0,\ i>0\\&D (i-1,j-1)+{\rm {m}}(S_{1}[i],S_{2}[j])\\\}\end{array}}\right.$ ,

hvor er nul hvis og en ellers; returnerer det mindste af argumenterne. ${\rm {m}}(a,b)$ $a=b$ ${\displaystyle \min\{\,a,b,c\,\))$

Her symboliserer trinnet på sletningen (D) fra den første linje, på - indsættelsen (I) i den første linje, og trinnet på begge indeks symboliserer udskiftningen af tegnet (R) eller fraværet af ændringer (M) . $jeg$ $j$

Det er klart, at følgende udsagn er sande:

${\rm {d}}(S_{1},S_{2})\geqslant {\bigl |}|S_{1}|-|S_{2}|{\bigr |}$
${\rm {d}}(S_{1},S_{2})\leqslant \max {\bigl (}|S_{1}|,|S_{2}|{\bigr )}$
${\mathop {\rm {d))}(S_{1},S_{2})=0\Leftrightarrow S_{1}=S_{2}$

Et eksempel på hvordan algoritmen fungerer.

		P	O	L	Y	N	O	M	jeg	EN	L
	0	en	2	3	fire	5	6	7	otte	9	ti
E	en	en	2	3	fire	5	6	7	otte	9	ti
x	2	2	2	3	fire	5	6	7	otte	9	ti
P	3	2	3	3	fire	5	6	7	otte	9	ti
O	fire	3	2	3	fire	5	5	6	7	otte	9
N	5	fire	3	3	fire	fire	5	6	7	otte	9
E	6	5	fire	fire	fire	5	5	6	7	otte	9
N	7	6	5	5	5	fire	5	6	7	otte	9
T	otte	7	6	6	6	5	5	6	7	otte	9
jeg	9	otte	7	7	7	6	6	6	6	7	otte
EN	ti	9	otte	otte	otte	7	7	7	7	6	7
L	elleve	ti	9	otte	9	otte	otte	otte	otte	7	6

Bevis

Lad os overveje formlen mere detaljeret. Det er klart, at redigeringsafstanden mellem to tomme linjer er nul. Det er også indlysende, at for at få en tom streng fra en streng med længde , skal du udføre sletningsoperationer, og for at få en streng med længde fra en tom, skal du udføre indsættelsesoperationer. $jeg$ $jeg$ $j$ $j$

Det er tilbage at overveje det ikke-trivielle tilfælde, når begge strenge er ikke-tomme.

Til at begynde med bemærker vi, at de i den optimale rækkefølge af operationer kan ombyttes vilkårligt. Overvej faktisk to sekventielle operationer:

To erstatninger for det samme tegn er ikke optimalt (hvis vi erstattede x med y, så y med z, ville det være mere rentabelt straks at erstatte x med z).
To erstatninger af forskellige karakterer kan byttes
To sletninger eller to indstik kan byttes
Det er ikke optimalt at indsætte et tegn med dets efterfølgende sletning (du kan annullere dem begge)
Sletning og indsættelse af forskellige tegn kan byttes om
At indsætte et tegn og derefter erstatte det er suboptimalt (overdreven udskiftning)
Indsættelse af et tegn og erstatning af et andet tegn ombyttes
At erstatte et tegn med dets efterfølgende sletning er ikke optimalt (overdreven udskiftning)
Sletning af et tegn og udskiftning af et andet tegn ombyttes

Lad det ende med tegnet "a", slut med tegnet "b". Der er tre muligheder: $S_{1}$ $S_{2}$

Tegnet "a", som slutter med , blev slettet på et tidspunkt. Lad os gøre denne sletning til den første operation. Derefter slettede vi tegnet "a", hvorefter vi forvandlede de første tegn til (hvilket krævede operationer), hvilket betyder, at alle handlinger var nødvendige $S_{1}$ $i-1$ $S_{1}$ $S_{2}$ $D(i-1,\j)$ $D(i-1,\j)+1$
Tegnet "b", som slutter med , blev tilføjet på et tidspunkt. Lad os gøre denne tilføjelse til den sidste operation. Vi blev til de første tegn , hvorefter vi tilføjede "b". I lighed med den tidligere sag tog det operationer. $S_{2}$ $S_{1}$ $j-1$ $S_{2}$ $D(i,\ j-1)+1$
Begge tidligere udsagn er forkerte. Hvis vi tilføjede tegn til højre for det sidste "a", så for at gøre det sidste tegn til "b", skulle vi enten tilføje det på et tidspunkt (men så ville udsagn 2 være sandt), eller erstatte et af disse tilføjede tegn (hvilket også er umuligt, fordi det ikke er optimalt at tilføje et tegn og derefter erstatte det). Det betyder, at vi ikke tilføjede tegn til højre for det sidste "a". Vi slettede ikke selve det sidste "a", da udsagn 1 er falsk. Så den eneste måde at ændre det sidste tegn på er at erstatte det. At udskifte det 2 eller flere gange er ikke optimalt. Midler,
1. Hvis , ændrede vi ikke det sidste tegn. Da vi heller ikke slettede det og ikke tilskrev noget til højre for det, påvirkede det ikke vores handlinger, og derfor udførte vi operationer. $a=b$ $D(i-1,\ j-1)$
2. Hvis , ændrede vi det sidste tegn én gang. Lad os lave denne ændring først. I fremtiden, i lighed med det tidligere tilfælde, skal vi udføre operationer, hvilket betyder, at alle operationer vil være påkrævet. $a\neq b$ $D(i-1,\ j-1)$ $D(i-1,\ j-1)+1$

Wagner-Fischer algoritme

For at finde den korteste afstand skal du beregne matrixen D ved hjælp af ovenstående formel . Det kan beregnes både efter rækker og efter kolonner. Algoritme pseudokode:

for alle i fra 0 til M for alle j fra 0 til N udregn D(i, j) retur D(M, N)

Eller i en mere detaljeret form og med vilkårlige priser på erstatninger, indsættelser og sletninger:

D(0, 0) = 0 for alle j fra 1 til N D(0, j) = D(0, j - 1) + symbolindsæt pris S2[j] for alle i fra 1 til M D(i, 0) = D(i - 1, 0) + omkostningerne ved at slette symbolet S1[i] for alle j fra 1 til N D(i, j) = min{ D(i - 1, j) + omkostninger ved at slette symbolet S1[i], D(i, j - 1) + omkostningerne ved at indsætte symbolet S2[j], D(i - 1, j - 1) + omkostninger ved at erstatte symbol S1[i] med symbol S2[j] } retur D(M, N)

(Vi minder dig om, at elementerne i rækkerne er nummereret fra den første , ikke fra nul.)

For at gendanne den redaktionelle recept er det nødvendigt at beregne matrixen D og derefter gå fra nederste højre hjørne (M, N) til øverste venstre, ved hvert trin på udkig efter minimum tre værdier:

hvis det er minimalt ( + omkostningerne ved at slette symbolet S1[i]), tilføj sletningen af symbolet S1[i] og gå til (i-1, j) $D(i-1,j)$
hvis det er minimalt ( + omkostningerne ved at indsætte symbolet S2[j]), skal du tilføje indsættelsen af symbolet S2[j] og gå til (i, j-1) $D(i,j-1)$
hvis det er minimalt ( + omkostningerne ved at erstatte symbolet S1[i] med symbolet S2[j]), skal du tilføje erstatningen af S1[i] med S2[j] (hvis de ikke er ens; ellers skal du ikke tilføje noget), hvorefter vi går til (i-1 , j-1) $D(i-1,j-1)$

Her (i, j) er cellen i matrixen, hvor vi er på dette trin. Hvis to af de tre værdier er minimale (eller alle tre er ens), betyder det, at der er 2 eller 3 tilsvarende redaktionelle forskrifter.

Denne algoritme kaldes Wagner-Fisher-algoritmen. Det blev foreslået af R. Wagner (RA Wagner) og M. Fischer (MJ Fischer) i 1974. [fire]

Hukommelse

Algoritmen i formen beskrevet ovenfor kræver operationer og den samme hukommelse. Sidstnævnte kan være irriterende: For eksempel vil sammenligning af filer med en længde på 10 5 linjer kræve omkring 40 gigabyte hukommelse. $\Theta (M\cdot N)$

Hvis der kun kræves afstand, er det nemt at reducere den nødvendige hukommelse til . For at gøre dette skal vi tage højde for, at efter at have beregnet en linje, er den forrige linje ikke længere nødvendig. Desuden er D(i-1,0) ... D(i-1,j-1) heller ikke nødvendig efter beregning af D(i, j). Derfor kan algoritmen omskrives som $\Theta (\min\{\,M,N\,\})$

for alle i fra 0 til M for alle j fra 0 til N udregn D(i, j) hvis jeg > 0 slet linje D(i - 1) retur D(M, N)

eller endda

for alle i fra 0 til M for alle j fra 0 til N udregn D(i, j) hvis i > 0 og j > 0 slet D(i - 1, j - 1) retur D(M, N)

Hvis et redaktionelt mandat er påkrævet, bliver det sværere at gemme hukommelsen.

For at sikre hukommelsestid definerer vi en matrix E med minimumsafstande mellem strengsuffikser , dvs. E(i, j) er afstanden mellem de sidste i-tegn og de sidste j-tegn . Det er klart, at matrixen E kan beregnes på samme måde som matricen D, og lige så hurtigt. $\Theta (M\cdot N)$ $\Theta (\min\{\,M,N\,\})$ $S_{1}$ $S_{2}$

Nu beskriver vi algoritmen, idet vi antager, at den er den korteste af de to strenge. $S_{2}$

Hvis længden af en af strengene (eller begge) højst er 1, er problemet trivielt. Hvis ikke, følg de næste trin.
Lad os opdele strengen i to understrenge med længde . (Hvis M er ulige, så vil længderne af understrengene være og .) Betegn understrengene og . $S_{1}$ $M/2$ $(M-1)/2$ $(M+1)/2$ $S_{1}^{-}$ $S_{1}^{+}$
For vi beregner den sidste række af matricen D, og for - den sidste række af matricen E. $S_{1}^{-}$ $S_{1}^{+}$
Lad os finde i sådan, at det er minimalt. Her er D og E matricerne fra det forrige trin, men vi bruger kun deres sidste rækker. Vi har således fundet en opdeling i to delstrenge, der minimerer summen af afstanden fra venstre halvdel til venstre side og afstanden af højre halvdel til højre side . Derfor svarer den venstre understreng til den venstre halvdel , og den højre understreng svarer til den højre halvdel. $D(|S_{1}^{-}|,i)+E(|S_{1}^{+}|,Ni)$ $S_{2}$ $S_{1}$ $S_{2}$ $S_{1}$ $S_{2}$ $S_{2}$ $S_{1}$
Søg rekursivt efter en redaktionel recept, der bliver til venstre side (det vil sige til en understreng ) $S_{1}^{-}$ $S_{2}$ $S2[1...i]$
Vi leder rekursivt efter en redaktionel recept, der bliver til højre side (det vil sige til en understreng ). $S_{1}^{+}$ $S_{2}$ $S2[i+1...N]$
Vi kombinerer begge redaktionelle opskrifter. [5]

Udførelsestiden opfylder (op til multiplikation med en konstant) betingelsen

T(M,N)=MN+T(M/2,N')+T(M/2,NN'),\ 0\leq N'\leq N

hvorfra det følger (bevist ved induktion på M)

T(M,N)\leq 2MN

følgelig

T(M,N)=\Theta (M\cdot N)

Påkrævet hukommelse er proportional $N+N/2+N/4+...=2N$

Derudover er der algoritmer, der sparer hukommelse på grund af en betydelig opbremsning, for eksempel bliver tiden kubisk, ikke kvadratisk, i længden af linjer.

Noter

↑ V. I. Levenshtein. Binære koder med korrektion af frafald, indsættelser og substitutioner af tegn. Rapporter fra Videnskabsakademiet i USSR, 1965. 163.4:845-848.
↑ Gasfield. Strenge, træer og sekvenser i algoritmer. Informatik og beregningsbiologi. Nevsky Dialect BVH-Petersburg, 2003.
↑ Se f.eks.: http://www.medlit.ru/medrus/mg/mg080237.htm Arkivkopi dateret 8. marts 2012 på Wayback Machine
↑ R. A. Wagner, M. J. Fischer. Strenge-til-streng-korrektionsproblemet. J. ACM 211 (1974). S. 168-173
↑ Samtidig er det i den anden redaktionelle instruktion nødvendigt at øge tegntallene for den første linje med , og den anden linje med , da de nu tælles fra begyndelsen af linjerne, og ikke fra deres midterste. $|S_{1}^{-}|$ $jeg$

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng