Distanța Levenshtein

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 aprilie 2022; verificările necesită 4 modificări .

Distanța Levenshtein ( distanța de editare , distanța de editare ) este o măsurătoare care măsoară diferența absolută dintre două secvențe de caractere. Este definită ca numărul minim de operații cu un singur caracter (și anume inserții, ștergeri, înlocuiri) necesare pentru a transforma o secvență de caractere în alta. În general, operațiunilor utilizate în această transformare li se pot atribui prețuri diferite. Utilizat pe scară largă în teoria informației și lingvistica computațională .

Problema a fost pusă pentru prima dată în 1965 de matematicianul sovietic Vladimir Levenshtein când studia secvențele [1] , mai târziu o problemă mai generală pentru un alfabet arbitrar a fost asociată cu numele său. O mare contribuție la studiul problemei a adus-o Dan Gasfield [2] . $0-1$

Aplicație

Distanța Levenshtein și generalizările sale sunt utilizate în mod activ:

pentru a corecta erorile dintr-un cuvânt (în motoarele de căutare, baze de date, la introducerea textului, cu recunoașterea automată a textului sau a vorbirii scanate).
pentru a compara fișierele text cu utilitarul diff și altele asemenea. Aici rolul „personajelor” este jucat de șiruri, iar rolul „șirurilor” este jucat de fișiere.
în bioinformatică pentru a compara gene , cromozomi și proteine .

Din punct de vedere al aplicațiilor, definirea distanței dintre cuvinte sau câmpuri de text conform Levenshtein are următoarele dezavantaje:

Când cuvintele sau părțile de cuvinte sunt schimbate, se obțin distanțe relativ mari;
Distanțele dintre cuvinte scurte complet diferite se dovedesc a fi mici, în timp ce distanțele dintre cuvinte lungi foarte asemănătoare se dovedesc a fi semnificative.

Instrucțiuni editoriale

O instrucțiune editorială este o succesiune de acțiuni necesare pentru a obține a doua din prima linie în cel mai scurt mod posibil. De obicei, acțiunile sunt notate astfel: D ( eng. delete ) - delete, I (eng. insert) - insert, R ( replace ) - replace, M ( potrivire ) - potrivire.

De exemplu, pentru 2 șiruri „CONNECT” și „CONEHEAD” puteți construi următorul tabel de conversie:

M	M	M	R	eu	M	R	R
C	O	N	N		E	C	T
C	O	N	E	H	E	A	D

Găsirea doar a distanței Levenshtein este o sarcină mai ușoară decât găsirea rețetei editoriale (vezi mai jos pentru mai multe detalii).

Generalizări

Prețuri diferite de tranzacție

Prețurile operațiunii pot depinde de tipul operațiunii (inserați, ștergeți, înlocuiți) și/sau de caracterele implicate în aceasta, reflectând probabilitatea diferită a mutațiilor în biologie [3] , probabilitatea diferită a diferitelor erori la introducerea textului etc. cazul general:

w(a, b) — prețul înlocuirii caracterului a cu caracterul b
w(ε, b) — costul inserării caracterului b
w(a, ε) — prețul ștergerii simbolului a

Este necesar să se găsească o succesiune de substituții care să minimizeze costul total. Distanța Levenshtein este un caz special al acestei probleme pentru

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

Atât un caz special, cât și o problemă pentru w arbitrar sunt rezolvate de algoritmul Wagner-Fisher prezentat mai jos. Aici și mai jos, presupunem că toți w sunt nenegativi, iar inegalitatea triunghiului se aplică : înlocuirea a două operații consecutive cu una nu crește costul total (de exemplu, înlocuirea simbolului x cu y și apoi y cu z este nu) mai bine decât imediat x cu z).

Transpunere

Dacă adăugăm o transpunere la lista de operațiuni permise (două caractere adiacente sunt schimbate), obținem distanța Damerau-Levenshtein . Are, de asemenea, un algoritm care necesită operații O(MN). Damerau a arătat că 80% dintre erorile de tastare umane sunt transpoziții. În plus, distanța Damerau-Levenshtein este folosită și în bioinformatică.

Formula

Aici și mai jos, se presupune că elementele șirurilor sunt numerotate de la primul, așa cum este obișnuit în matematică, și nu de la zero, așa cum este obișnuit în multe limbaje de programare.

Fie și două șiruri (de lungime și respectiv) peste un alfabet , apoi distanța de editare (distanța Levenshtein) poate fi calculată folosind următoarea formulă recursivă $S_{1}$ $S_{2}$ $M$ $N$ ${\rm {d}}(S_{1},S_{2})$

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

$D(i,j)=\left\{{\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.$ ,

unde este zero dacă și unul în caz contrar; returnează cel mai mic dintre argumente. ${\rm {m}}(a,b)$ $a=b$ $\min\{\,a,b,c\,\}$

Aici pasul pe simbolizează ștergerea (D) din prima linie, pe - inserarea (I) în prima linie, iar pasul pe ambii indici simbolizează înlocuirea caracterului (R) sau absența modificărilor (M) . $i$ $j$

Evident, următoarele afirmații sunt adevărate:

${\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}$

Un exemplu despre cum funcționează algoritmul.

		P	O	L	Y	N	O	M	eu	A	L
	0	unu	2	3	patru	5	6	7	opt	9	zece
E	unu	unu	2	3	patru	5	6	7	opt	9	zece
X	2	2	2	3	patru	5	6	7	opt	9	zece
P	3	2	3	3	patru	5	6	7	opt	9	zece
O	patru	3	2	3	patru	5	5	6	7	opt	9
N	5	patru	3	3	patru	patru	5	6	7	opt	9
E	6	5	patru	patru	patru	5	5	6	7	opt	9
N	7	6	5	5	5	patru	5	6	7	opt	9
T	opt	7	6	6	6	5	5	6	7	opt	9
eu	9	opt	7	7	7	6	6	6	6	7	opt
A	zece	9	opt	opt	opt	7	7	7	7	6	7
L	unsprezece	zece	9	opt	9	opt	opt	opt	opt	7	6

Dovada

Să luăm în considerare formula mai detaliat. Evident, distanța de editare dintre două linii goale este zero. De asemenea, este evident că pentru a obține un șir gol dintr-un șir de lungime , trebuie să efectuați operații de ștergere, iar pentru a obține un șir de lungime dintr-un șir gol, trebuie să efectuați operații de inserare. $i$ $i$ $j$ $j$

Rămâne de luat în considerare cazul non-trivial când ambele șiruri sunt nevide.

Pentru început, observăm că în secvența optimă de operații ele pot fi interschimbate în mod arbitrar. Într-adevăr, luați în considerare două operații secvențiale:

Două înlocuiri pentru același caracter nu sunt optime (dacă am înlocui x cu y, apoi y cu z, ar fi mai profitabil să înlocuim imediat x cu z).
Două înlocuiri de personaje diferite pot fi schimbate
Două ștergeri sau două inserții pot fi schimbate
Inserarea unui caracter cu ștergerea lui ulterioară nu este optimă (le puteți anula pe ambele)
Ștergerea și lipirea diferitelor caractere pot fi schimbate
Inserarea unui caracter și apoi înlocuirea acestuia este suboptimă (înlocuire excesivă)
Inserarea unui caracter și înlocuirea unui alt caracter sunt schimbate
Înlocuirea unui caracter cu ștergerea lui ulterioară nu este optimă (înlocuire excesivă)
Ștergerea unui caracter și înlocuirea unui alt caracter sunt schimbate

Lasă-l să se termine cu caracterul „a”, se termină cu caracterul „b”. Există trei opțiuni: $S_{1}$ $S_{2}$

Caracterul „a”, care se termină cu , a fost șters la un moment dat. Să facem din această ștergere prima operațiune. Apoi am șters caracterul „a”, după care am transformat primele caractere în (care necesita operații), ceea ce înseamnă că toate operațiunile erau necesare $S_{1}$ $i-1$ $S_{1}$ $S_{2}$ $D(i-1,\j)$ $D(i-1,\j)+1$
Caracterul „b”, care se termină cu , a fost adăugat la un moment dat. Să facem din această adăugare ultima operație. Ne-am transformat în primele personaje , după care am adăugat „b”. Similar cu cazul precedent, a fost nevoie de operații. $S_{2}$ $S_{1}$ $j-1$ $S_{2}$ $D(i,\j-1)+1$
Ambele afirmații anterioare sunt greșite. Dacă am adăugat caractere la dreapta „a” final, atunci pentru a face ultimul caracter „b”, a trebuit fie să-l adăugăm la un moment dat (dar atunci afirmația 2 ar fi adevărată), fie să înlocuim unul dintre acestea. caractere adăugate (ceea ce este și imposibil, deoarece adăugarea unui caracter și apoi înlocuirea lui nu este optimă). Aceasta înseamnă că nu am adăugat caractere la dreapta „a” final. Nu am șters „a” final în sine, deoarece afirmația 1 este falsă. Deci singura modalitate de a schimba ultimul caracter este înlocuirea acestuia. Înlocuirea lui de 2 sau mai multe ori nu este optimă. Mijloace,
1. Dacă , nu am schimbat ultimul caracter. Deoarece nici nu l-am șters și nu i-am atribuit nimic dreptului, nu ne-a afectat acțiunile și, prin urmare, am efectuat operațiuni. $a=b$ $D(i-1,\ j-1)$
2. Dacă , am schimbat ultimul caracter o dată. Să facem mai întâi această schimbare. Pe viitor, la fel ca în cazul precedent, trebuie să facem operații, ceea ce înseamnă că toate operațiunile vor fi necesare. $a\neq b$ $D(i-1,\ j-1)$ $D(i-1,\j-1)+1$

Algoritmul Wagner-Fischer

Pentru a găsi cea mai scurtă distanță, trebuie să calculați matricea D folosind formula de mai sus . Poate fi calculat atât pe rânduri, cât și pe coloane. Pseudocod algoritm:

pentru toate i de la 0 la M pentru toate j de la 0 la N calculați D(i, j) întoarce D(M, N)

Sau într-o formă mai detaliată și cu prețuri arbitrare pentru înlocuiri, inserări și ștergeri:

D(0, 0) = 0 pentru toate j de la 1 la N D(0, j) = D(0, j - 1) + costul de inserare simbol S2[j] pentru toate i de la 1 la M D(i, 0) = D(i - 1, 0) + costul ștergerii simbolului S1[i] pentru toate j de la 1 la N D(i, j) = min{ D(i - 1, j) + costul ștergerii simbolului S1[i], D(i, j - 1) + costul inserării simbolului S2[j], D(i - 1, j - 1) + costul înlocuirii simbolului S1[i] cu simbolul S2[j] } întoarce D(M, N)

(Vă reamintim că elementele rândurilor sunt numerotate de la primul , nu de la zero.)

Pentru a restabili prescripția editorială, este necesar să se calculeze matricea D, apoi să se treacă din colțul din dreapta jos (M, N) în stânga sus, la fiecare pas căutând minim trei valori:

dacă este minim ( + costul ștergerii simbolului S1[i]), adăugați ștergerea simbolului S1[i] și mergeți la (i-1, j) $D(i-1,j)$
dacă este minim ( + costul inserării simbolului S2[j]), adăugați inserarea simbolului S2[j] și mergeți la (i, j-1) $D(i,j-1)$
dacă este minim ( + costul înlocuirii simbolului S1[i] cu simbolul S2[j]), se adaugă înlocuirea lui S1[i] cu S2[j] (dacă nu sunt egale; în caz contrar, nu se adaugă orice), după care trecem la (i-1 , j-1) $D(i-1,j-1)$

Aici (i, j) este celula matricei în care ne aflăm la acest pas. Dacă două dintre cele trei valori sunt minime (sau toate trei sunt egale), înseamnă că există 2 sau 3 prescripții editoriale echivalente.

Acest algoritm se numește algoritmul Wagner-Fisher. A fost propus de R. Wagner (RA Wagner) și M. Fischer (MJ Fischer) în 1974. [patru]

Memorie

Algoritmul în forma descrisă mai sus necesită operații și aceeași memorie. Acesta din urmă poate fi enervant: de exemplu, compararea fișierelor cu o lungime de 10 5 linii va necesita aproximativ 40 de gigaocteți de memorie. $\Theta (M\cdot N)$

Dacă este necesară doar distanța, este ușor să reduceți memoria necesară la . Pentru a face acest lucru, trebuie să ținem cont de faptul că după calcularea oricărei linii, linia anterioară nu mai este necesară. Mai mult, după calcularea D(i, j), D(i-1,0) ... D(i-1,j-1) nu este de asemenea necesar. Prin urmare, algoritmul poate fi rescris ca $\Theta (\min\{\,M,N\,\})$

pentru toate i de la 0 la M pentru toate j de la 0 la N calculați D(i, j) dacă i > 0 ștergeți linia D(i - 1) întoarce D(M, N)

sau chiar

pentru toate i de la 0 la M pentru toate j de la 0 la N calculați D(i, j) dacă i > 0 și j > 0 ștergeți D(i - 1, j - 1) întoarce D(M, N)

Dacă este necesar un mandat editorial, salvarea memoriei devine mai dificilă.

Pentru a asigura timpul de memorie , definim o matrice E de distante minime intre sufixele sirurilor , adica E(i, j) este distanta dintre ultimele i caractere si ultimele j caractere . Evident, matricea E poate fi calculată în mod similar cu matricea D și la fel de rapid. $\Theta (M\cdot N)$ $\Theta (\min\{\,M,N\,\})$ $S_{1}$ $S_{2}$

Acum descriem algoritmul, presupunând că acesta este cel mai scurt dintre cele două șiruri. $S_{2}$

Dacă lungimea unuia dintre șiruri (sau a ambelor) este de cel mult 1, problema este banală. Dacă nu, urmați pașii următori.
Să împărțim șirul în două subșiruri de lungime . (Dacă M este impar, atunci lungimile subșirurilor vor fi și .) Notați subșirurile și . $S_{1}$ $M/2$ $(M-1)/2$ $(M+1)/2$ $S_{1}^{-}$ $S_{1}^{+}$
Pentru că calculăm ultimul rând al matricei D, iar pentru - ultimul rând al matricei E. $S_{1}^{-}$ $S_{1}^{+}$
Să găsim că este minim. Aici D și E sunt matricele de la pasul anterior, dar le folosim doar ultimele rânduri. Astfel, am găsit o împărțire în două subșiruri care minimizează suma distanței dintre jumătatea stângă și partea stângă și distanța dintre jumătatea dreaptă și partea dreaptă . Prin urmare, subșirul din stânga corespunde jumătății stângi , iar subșirul din dreapta corespunde jumătății drepte. $D(|S_{1}^{-}|,i)+E(|S_{1}^{+}|,Ni)$ $S_{2}$ $S_{1}$ $S_{2}$ $S_{1}$ $S_{2}$ $S_{2}$ $S_{1}$
Căutați recursiv o rețetă editorială care se transformă în partea stângă (adică într-un subșir ) $S_{1}^{-}$ $S_{2}$ $S2[1...i]$
Căutăm recursiv o prescripție editorială care se transformă în partea dreaptă (adică într-un subșir ). $S_{1}^{+}$ $S_{2}$ $S2[i+1...N]$
Combinăm ambele prescripții editoriale. [5]

Timpul de execuție satisface (până la înmulțirea cu o constantă) condiția

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

de unde rezultă (demonstrat prin inducție pe M)

T(M,N)\leq 2MN

prin urmare

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

Memoria necesară este proporțională $N+N/2+N/4+...=2N$

În plus, există algoritmi care economisesc memorie din cauza unei încetiniri semnificative, de exemplu, timpul devine cubic, nu pătratic, în lungimea liniilor.

Note

↑ V. I. Levenshtein. Coduri binare cu corectarea abandonurilor, inserărilor și substituirilor de caractere. Rapoarte ale Academiei de Științe a URSS, 1965. 163.4:845-848.
↑ Gasfield. Șiruri, arbori și secvențe în algoritmi. Informatică și Biologie Computațională. Nevsky Dialect BVH-Petersburg, 2003.
↑ Vezi, de exemplu: http://www.medlit.ru/medrus/mg/mg080237.htm Copie de arhivă din 8 martie 2012 la Wayback Machine
↑ R. A. Wagner, M. J. Fischer. Problema corecției șir-la-șir. J. ACM 21 1 (1974). P. 168-173
↑ În același timp, în cea de-a doua instrucțiune editorială, este necesar să se mărească numerele de caractere ale primei rânduri cu , iar celei de -a doua rânduri cu , deoarece acum se numără de la începutul rândurilor, și nu de la mijlocul lor. $|S_{1}^{-}|$ $i$

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun