Distanța de editare (distanța Levenshtein)
Scrieți recieve, iar telefonul vă sugerează receive. Știe că ați fost aproape, pentru că cele două cuvinte sunt la doar câteva operații distanță. Măsurarea acestei apropieri, adică a distanței de editare, este o problemă clasică de programare dinamică.
Problema
O operație modifică un cuvânt cu o literă: inserează o literă, șterge o literă sau înlocuiește o literă cu alta. Distanța de editare dintre două cuvinte este cel mai mic număr de operații care îl transformă pe unul în celălalt. Între cat și cut distanța este 1, între cat și cast tot 1, iar între cat și act 2. Se mai numește distanța Levenshtein, după matematicianul sovietic Vladimir Levenshtein, care a studiat-o în 1965.
Tabelul
Fie d[i][j] distanța de editare dintre primele i litere ale unui cuvânt și primele j litere ale celuilalt. Transformarea unui cuvânt în nimic cere câte o ștergere pentru fiecare literă, deci d[i][0] = i, iar construirea unui cuvânt pornind de la nimic cere câte o inserare pentru fiecare literă, deci d[0][j] = j. Dacă litera i este egală cu litera j, d[i][j] = d[i − 1][j − 1]. Altfel, d[i][j] = 1 + cel mai mic dintre d[i − 1][j − 1] (înlocuire), d[i − 1][j] (ștergere) și d[i][j − 1] (inserare).
Un exemplu
Pentru kitten și sitting, tabelul are 7 rânduri și 8 coloane. Celula din dreapta jos este 3, iar citirea înapoi pornind de la ea dă: înlocuiți k cu s, păstrați i, t și t, înlocuiți e cu i, păstrați n și inserați g. De la kitten la sitten, apoi sittin, apoi sitting: trei operații, iar tabelul demonstrează că nu există o listă mai scurtă.
Citirea înapoi a operațiilor
Porniți de la celula din dreapta jos și întrebați-vă din care vecin provine valoarea ei. Dacă literele coincid și celula este egală cu vecinul din stânga sus, litera a fost păstrată: mergeți pe diagonală. Dacă este cu unu mai mare decât vecinul din stânga sus, a fost o înlocuire; cu unu mai mare decât celula de deasupra, o ștergere; cu unu mai mare decât celula din stânga, o inserare. Mai multe drumuri pot fi la egalitate, și fiecare dă o listă de operații cât mai scurtă.
Istorie și utilizări
Levenshtein a introdus distanța în 1965, pe când lucra la coduri corectoare de erori. Metoda tabelului a fost publicată de mai mulți autori, cel mai cunoscut de Robert Wagner și Michael Fischer în 1974, de aceea este numită adesea algoritmul Wagner–Fischer. Astăzi, distanțele de editare ordonează sugestiile de ortografie, găsesc în baze de date nume scrise greșit, compară secvențe de ADN și de proteine și evaluează recunoașterea vocală.
Explorați
Deschideți aplicația și apăsați Pas. Cele două litere comparate se aprind în antete; literele egale copiază celula albastră din stânga sus, iar literele diferite citesc toți cei trei vecini albaștri și adună unu la cel mai mic. La final, drumul portocaliu pornește înapoi din colț, iar operațiile apar sub tabel.
Întrebări frecvente
Este distanța de editare o metrică?
Da. Nu este niciodată negativă, este 0 doar pentru cuvinte egale, este aceeași în ambele sensuri, iar trecerea printr-un al treilea cuvânt nu o poate scurta niciodată: d(a, c) ≤ d(a, b) + d(b, c). De aceea este utilă pentru căutarea potrivirilor apropiate.
Ce este distanța Damerau–Levenshtein?
Este distanța de editare cu o operație în plus: interschimbarea a două litere vecine. Frederick Damerau a constatat în 1964 că inserarea, ștergerea, înlocuirea și interschimbarea acoperă împreună peste 80% din greșelile de ortografie. Cu interschimbări, recieve și receive sunt la distanța 1 în loc de 2.
Se poate calcula distanța de editare mai repede decât în O(m·n)?
Nu cu mult. În 2015, Arturs Backurs și Piotr Indyk au arătat că o metodă care durează O(n^(2 − ε)) pentru un anumit ε > 0 ar infirma ipoteza timpului exponențial puternic, pe care majoritatea cercetătorilor o consideră adevărată. Pentru cuvinte apropiate, însă, e nevoie doar de o bandă îngustă în jurul diagonalei tabelului.
Cum se folosește distanța de editare la compararea ADN-ului?
Biologii folosesc același tabel cu scoruri în loc de numărători: potrivirile aduc puncte, iar înlocuirile și golurile costă puncte care depind de litere. Acesta este algoritmul Needleman–Wunsch din 1970 pentru secvențe întregi și algoritmul Smith–Waterman din 1981 pentru fragmentele care se potrivesc cel mai bine.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați distanța de editare