Distanța Levenshtein este o măsură a diferenței dintre două șiruri de simboluri, definită ca numărul minim de operații elementare necesare pentru transformarea unui șir în celălalt. În forma clasică sunt permise trei operații, fiecare cu costul 1: inserarea unui simbol, ștergerea unui simbol și înlocuirea unui simbol cu altul.Paul E. Black (ed.): „Levenshtein distance”, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology. Actualizat la 15 mai 2019. Accesat la 10 septembrie 2026.
Măsura poartă numele matematicianului sovietic Vladimir I. Levenshtein, care a introdus conceptul în 1965 în contextul codurilor capabile să corecteze ștergeri, inserări și substituții.V. I. Levenshtein: „Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady, vol. 10, nr. 8, 1966, pp. 707–710. Originalul în limba rusă a fost publicat în 1965. Distanța Levenshtein este un caz particular de distanță de editare, nu un sinonim pentru întreaga familie a distanțelor de editare. Ea este folosită în potrivirea aproximativă a șirurilor, corectarea ortografică, lingvistica computațională, analiza variantelor lingvistice și alte probleme în care secvențele pot diferi prin inserări, ștergeri sau înlocuiri.Gonzalo Navarro: „A Guided Tour to Approximate String Matching”, ACM Computing Surveys, vol. 33, nr. 1, 2001, pp. 31–88. doi:10.1145/375360.375365.
Definiție Fie și două șiruri. Se notează cu distanța Levenshtein dintre prefixul format din primele simboluri ale lui și prefixul format din primele simboluri ale lui . Condițiile de margine sunt
Pentru și ,
unde
Primul termen corespunde unei ștergeri, al doilea unei inserări, iar al treilea unei potriviri sau unei înlocuiri. Distanța dintre șirurile complete este .Robert A. Wagner și Michael J. Fischer: „The String-to-String Correction Problem”, Journal of the ACM, vol. 21, nr. 1, 1974, pp. 168–173. doi:10.1145/321796.321811.
Definiția este formulată pentru secvențe și nu impune ca elementele comparate să fie neapărat caractere. În funcție de aplicație, o unitate poate fi un caracter, un punct de cod Unicode, un grafem, un cuvânt sau un alt simbol discret. Rezultatul trebuie interpretat întotdeauna în raport cu unitatea de comparație aleasă.
Exemple Distanța Levenshtein dintre cuvintele carte și parte este 1: este suficientă înlocuirea literei c cu p.
Pentru mare și marea, distanța este 1, deoarece al doilea șir se obține prin inserarea literei a la sfârșitul primului.
Operațiile nu trebuie să fie unice. Pentru unele perechi de șiruri pot exista mai multe secvențe de editare distincte care au același cost minim.
Calcul prin programare dinamică Metoda clasică de calcul folosește programare dinamică. Algoritmul Wagner–Fischer construiește o matrice cu poziții și calculează distanțele dintre prefixele celor două șiruri, reutilizând rezultatele subproblemelor deja rezolvate.
Un pseudocod simplificat este:
function LevenshteinDistance(a, b): m := length(a) n := length(b) create D[0..m, 0..n]
for i := 0..m: D[i, 0] := i for j := 0..n: D[0, j] := j
for i := 1..m: for j := 1..n: if a[i] = b[j]: cost := 0 else: cost := 1
D[i, j] := min( D[i-1, j] + 1, D[i, j-1] + 1, D[i-1, j-1] + cost )
return D[m, n]
Dacă matricea completă este păstrată, poate fi reconstruit și un traseu optim de editare pornind din celula și urmărind în sens invers predecesorii care produc valorile minime. Dacă există egalități între mai mulți predecesori optimi, pot exista mai multe secvențe optime de operații.
Complexitate temporală și spațială Pentru șiruri de lungimi și , calculul matricei complete necesită timp. Dacă este memorată întreaga matrice, memoria necesară este tot . Dacă este nevoie numai de valoarea distanței și nu de reconstruirea unei secvențe de editare, sunt suficiente liniile matricei necesare pasului curent, iar memoria poate fi redusă la .Esko Ukkonen: „Algorithms for approximate string matching”, Information and Control, vol. 64, nr. 1–3, 1985, pp. 100–118. doi:10.1016/S0019-9958(85)80046-2.
Când este cunoscută în prealabil o limită mică pentru distanța acceptată, nu este necesar în toate cazurile să fie evaluată întreaga matrice. Ukkonen a descris algoritmi a căror zonă de calcul și complexitate depind de distanța efectivă sau de pragul impus.
Algoritmi bit-vectoriali Pentru potrivirea aproximativă a unui model într-un text, mai multe stări ale programării dinamice pot fi reprezentate prin biți ai unui cuvânt de mașină. Algoritmul lui Gene Myers din 1999 folosește operații bit-vectoriale pentru a actualiza simultan mai multe poziții ale calculului și oferă o implementare eficientă a potrivirii aproximative în anumite regimuri de lungime a modelului și prag de eroare.Gene Myers: „A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming”, Journal of the ACM, vol. 46, nr. 3, 1999, pp. 395–415. doi:10.1145/316542.316550. Această tehnică nu schimbă definiția distanței Levenshtein, ci modul în care este calculată.
Automate Levenshtein Pentru un șir de referință și un prag poate fi construit un automat finit care acceptă șirurile aflate la distanță Levenshtein cel mult față de șirul dat. Schulz și Mihov au studiat asemenea automate pentru corectarea rapidă a șirurilor pe baza unui dicționar.Klaus U. Schulz și Stoyan Mihov: „Fast string correction with Levenshtein automata”, International Journal on Document Analysis and Recognition, vol. 5, nr. 1, 2002, pp. 67–85. doi:10.1007/s10032-002-0082-8.
Limite condiționate de complexitate Pentru calculul exact al distanței de editare pe intrări generale de lungimi comparabile, algoritmul dinamic clasic are comportament pătratic. Backurs și Indyk au arătat o limită inferioară condiționată: dacă distanța de editare exactă pentru șiruri de lungime ar putea fi calculată în timp pentru o constantă , atunci Strong Exponential Time Hypothesis (SETH) ar fi falsă.Arturs Backurs și Piotr Indyk: „Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False)”, SIAM Journal on Computing, vol. 47, nr. 3, 2018, pp. 1087–1097. doi:10.1137/15M1053128.
Rezultatul este condiționat, nu o imposibilitate necondiționată. El nu exclude algoritmi mai rapizi pentru cazuri speciale, pentru distanțe mici, pentru aproximări sau pentru modele de calcul cu ipoteze suplimentare.
Proprietăți Cu costurile clasice egale cu 1, distanța Levenshtein este o metrică pe mulțimea șirurilor: este nenegativă, este 0 dacă și numai dacă șirurile sunt identice, este simetrică și satisface inegalitatea triunghiului. În acest sens, mulțimea șirurilor împreună cu distanța Levenshtein formează un spațiu metric.
Dacă lungimile celor două șiruri sunt și , atunci
Limita inferioară rezultă din faptul că diferența de lungime necesită cel puțin inserări sau ștergeri. Pentru limita superioară, caracterele din partea comună ca lungime pot fi înlocuite, după care simbolurile rămase pot fi inserate sau șterse.
Relația cu distanța Hamming Pentru două șiruri de aceeași lungime, distanța Levenshtein este cel mult distanța Hamming:
Egalitatea nu este garantată. Distanța Hamming numără pozițiile necorespunzătoare și poate fi privită ca folosind numai înlocuiri, pe când Levenshtein permite și inserări și ștergeri, care pot produce un traseu de editare mai ieftin.
Relația cu cel mai lung subsequence comun Dacă înlocuirea nu este permisă și sunt folosite numai inserări și ștergeri, costul minim dintre două șiruri de lungimi și este
unde este lungimea celui mai lung subsequence comun (longest common subsequence). Această formulă aparține variantei insertion–deletion a distanței de editare; nu trebuie confundată cu modelul Levenshtein clasic în care înlocuirea are costul 1.
Variante ponderate și distanțe înrudite În modelul clasic, inserarea, ștergerea și înlocuirea au toate costul 1. Într-o distanță de editare ponderată, costul poate depinde de tipul operației sau de simbolurile implicate. Un asemenea model poate reprezenta, de exemplu, faptul că anumite confuzii ortografice sau fonetice sunt mai probabile decât altele. Alegerea arbitrară a ponderilor poate însă elimina unele dintre proprietățile metrice ale formei clasice.
Distanța Damerau–Levenshtein este o măsură înrudită în care, pe lângă inserare, ștergere și înlocuire, transpunerea a două simboluri adiacente este permisă ca o singură operație. Ea nu este identică cu distanța Levenshtein clasică.
Aplicații Corectare ortografică și căutare aproximativă Într-un corector ortografic, un cuvânt necunoscut poate fi comparat cu intrările unui lexicon, iar formele cu distanță mică pot fi tratate ca variante candidate. Distanța singură nu stabilește însă care candidat este lingvistic cel mai probabil, astfel încât sistemele practice o pot combina cu frecvențe, modele de limbă, informație morfologică, context sau similaritate fonetică.
În căutarea aproximativă se pot recupera șirurile aflate la o distanță cel mult egală cu un prag față de interogare, ceea ce permite tolerarea unor mici erori de tastare, omisiuni sau caractere suplimentare.
Prelucrarea limbii române și corectarea ortografică Într-un sistem de traducere vorbire-la-vorbire română–engleză dezvoltat la Institutul de Cercetări pentru Inteligență Artificială „Mihai Drăgănescu” al Academiei Române, componenta de corectare ortografică generează variante prin ștergerea, înlocuirea sau adăugarea de litere și spații, apoi le reclasifică folosind probabilități de tip n-gramă. Funcția de scor include un factor dependent de distanța Levenshtein dintre interogarea inițială și varianta ortografică.Tiberiu Boroș și Dan Tufiș: „Romanian-English Speech Translation”, Proceedings of the Romanian Academy, Series A, vol. 15, nr. 1, 2014, pp. 68–75.
Această utilizare ilustrează rolul distanței ca una dintre componentele unui sistem mai larg: selecția finală nu este făcută exclusiv după distanța de caractere, ci și după probabilități contextuale și alte informații lingvistice.
Dialectologie computațională românească Alina Maria Ciobanu și Liviu P. Dinu au folosit o versiune normalizată a distanței Levenshtein într-un studiu computațional al românei, aromânei, meglenoromânei și istroromânei. Setul de date conținea lista Swadesh scurtă de 108 cuvinte, în reprezentare ortografică și fonetică.Alina Maria Ciobanu și Liviu P. Dinu: „A Computational Perspective on the Romanian Dialects”, în Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC'16), 2016, pp. 3281–3285.
În studiu, distanța de editare este împărțită la lungimea celui mai lung dintre cele două cuvinte. Pentru formele ortografice, distanțele medii față de română au fost 0,44 pentru aromână, 0,47 pentru meglenoromână și 0,55 pentru istroromână. Pentru reprezentările fonetice valorile au fost 0,40, 0,39 și, respectiv, 0,42. Autorii au folosit apoi aceste distanțe și alte caracteristici ortografice și fonetice pentru a analiza apropierea dintre varietăți și pentru o problemă de identificare automată a dialectului.
Aceste valori aparțin setului de 108 cuvinte și normalizării definite în studiul respectiv; ele nu reprezintă o „distanță absolută” între limbile sau varietățile analizate.
Texte românești din secolul al XIX-lea, OCR și transliterare