Distanța Levenshtein

Distanța Levenshtein

În informatică, distanța Levenshtein dintre două cuvinte s și t se definește ca fiind numărul minim necesar de operații ce se pot efectua, pentru a schimba un cuvânt în celălalt. Operațiile se pot efectua la nivel de caracter și pot fi de tipul: inserare, ștergere sau înlocuire. Este numită și distanță de editare, problema fiind definită de matematicianul rus Vladimir Levenshtein în 1965.

Exemplu: pentru s=”marina” (n=6) și t=”animat” (m=6) numărul minim de operații necesar pentru a transforma pe s în t este 4:

marina ⇒ arina ⇒ anina ⇒ anima ⇒ animat

Observăm că numărul de operații necasar pentru a transforma șirul s în șirul t este mai mic sau egal cu maximul dintre n și m.
Pornind de la șirul s numărăm operațiile care se fac asupra șirului inițial pornind de la stânga spre dreapta pentru a obține șirul t.
Considerăm o matrice dist cu n+1 linii și m+1 coloane în care dist[i][j] reprezintă numărul minim de operații necesar pentru a transforma primele i caractere din șirul s în primele j caractere din șirul t. În particular dist⁰[j] reprezintă numărul minim de transformări necesare pentru a transforma șirul vid în primele j caractere din șirul t, iar dist[i]⁰ reprezintă numărul minim de transformări necesare pentru a transforma primele i caractere din șirul s în șirul vid.

dist[i][j]=j dacă i==0
dist[i][j]=i dacă j==0
dist[i][j]=dist[i-1][j-1] dacă i!=0 și j!=0 și s[i]==t[j]
dist[i][j]=1+min⁡{dist[i-1][j-1],dist[i][j-1],dist[i-1][j]),altfel

La fiecare pas se compară caracterul s[i] cu t[j].
Dacă s[i]==t[j] atunci nu se face nici o modificare și dist[i][j]=dist[i-1][j-1]
Dacă s[i]!=t[j] atunci putem să avem următoarele situațiile: Adăugarea unui caracter în t[j] caz în care dist[i][j]=1+dist[i][j-1] Ștergerea caracterului s[i] caz în care dist[i][j]=1+dist[i-1][j] Modificarea lui s[i] în t[j] caz în care dist[i][j]=1+dist[i-1][j-1]

Exemplu: pentru s=”marina” (n=6) și t=”animat” (m=6) Pentru a transforma șirul vid în cuvântul ”animat”) formăm linia 0 a matricii cu valorile:
0 1 2 3 4 5 6
(explicație: 0 operații pentru a transforma șirul vid în șirul vid, 1 operație pentru a transforma șirul vid în șirul ”a”, 2 operații pentru a transforma șirul vid în șirul ”an”… 6 operații pentru a transforma șirul vid în șirul”animat”)
Pentru a transforma șirul ”m” în șirul ”animat” formăm linia 1 a matricii cu valorile:
1 1 2 3 3 4 5
(explicație: 1 operație pentru a transforma șirul ”m” în șirul vid, 1 operație pentru a transforma șirul ”m” în șirul ”a”, 2 operații pentru a transforma șirul ”m” în șirul ”an”… 3 operații pentru a transforma șirul”m” în șirul ”ani”, tot 3 operații pentru a transforma șirul ”m” în șirul”anim”(de exemplu 3 inserări”)…6 operații pentru a transforma șirul ”m” în șirul”animat”)
……
Pentru a transforma șirul ”marina” în șirul ”animat” formăm ultima linie din matrice cu valorile:
6 5 4 4 4 4 3 4
(explicație: 6 operații pentru a transforma șirul ”marina” în șirul vid, 5 operații pentru a transforma șirul ”marina” în șirul ”a”, 4 operații pentru a transforma șirul ”marina” în șirul ”an”(ștergem literele m,r,i și a)… 4 operații pentru a transforma șirul”marina” în șirul ”animat)
Matricea va fi:
0 1 2 3 4 5 6
1 1 2 3 3 4 5
2 1 2 3 4 3 4
3 2 2 3 4 4 4
4 3 3 2 3 4 5
5 4 3 3 3 4 5
6 5 4 4 4 3 4

Numărul minim de operații pentru acest exemplu va fi dist [6] [6] adică 4

#include <bits/stdc++.h>
using namespace std;
int dist [105] [105];

int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist⁰⁰ = 0; for(int i = 1; i <= 100; i++) { dist[i]⁰ = i; dist⁰[i] = i; } string s, t; cin >> s >> t; for(int i = 1; i <= s.size(); i++) { for(int j = 1; j <= t.size(); j++) { if(s[i-1] == t[j-1]) { dist[i][j] = min(dist[i][j], dist[i-1][j-1]); } else { dist[i][j] = min(dist[i][j], 1+dist[i-1][j-1]); } dist[i][j] = min(dist[i][j], 1+dist[i-1][j]); dist[i][j] = min(dist[i][j], 1+dist[i][j-1]); } } cout<<“matricea distantelor”<<’\n’; for(int i = 0; i <= s.size(); i++) { for(int j = 0; j <= t.size(); j++) cout<<dist[i][j]<<’ ‘; cout<<’\n’; } cout << “distanta minima este : “<<dist[s.size()][t.size()]; return 0;
}