La distancia de Levenshtein, distancia d'edición o distancia ente pallabres ye'l númberu mínimu d'operaciones riquíes pa tresformar una cadena de calteres n'otra, úsase llargamente en teoría de la información y ciencies de la computación. Entender por operación, bien un insertamientu, eliminación o la sustitución d'un calter. Esta distancia recibe esi nome n'honor al científicu rusu Vladimir Levenshtein, quien s'ocupó d'esta distancia en 1965. Ye útil en programes que determinen qué similares son dos cadenes de calteres, como ye'l casu de los correutor d'ortografía correutores d'ortografía.

Por casu, la distancia de Levenshtein ente "casa" y "cai" ye de 3 porque se precisen siquier tres ediciones elementales pa camudar unu nel otru.

1. casa → cala (sustitución de 's' por 'l')
2. cala → calla (insertamientu de 'l' ente 'l' y 'a')
3. calla → cai (sustitución de 'a' por 'y')

Considérase-y una xeneralización de la distancia de Hamming, que s'usa pa cadenes del mesmu llargor y que solo considera como operación la sustitución. Hai otres xeneralizaciones de la distancia de Levenshtein, como la distancia de Damerau-Levenshtein, que consideren l'intercambiu de dos calteres como una operación.

Como bona "distancia", cumple (anque ye complicáu demostralo formalmente), que:

Dist(A,B) == Dist(B,A)

Dist(A,B) + Dist(B,C) >= Dist(A,C)

L'algoritmu

Trátase d'un algoritmu de tipu bottom-up, común en programación dinámica. Sofitar nel usu d'una matriz (n + 1) × (m + 1), onde n y m son los llargores de les cadenes. Equí indícase l'algoritmu en pseudocódigo pa una función LevenshteinDistance que toma dos cadenes, str1 de llargor lenStr1, y str2 de llargor lenStr2, y calcula la distancia Levenshtein ente ellos:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost

for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j

for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i-1] = str2[j-1] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)

return d[lenStr1, lenStr2]

L'invariante calteníu al traviés del algorítmo ye que pueda tresformar el segmentu inicial str1[1..i] en str2[1..j] emplegando un mínimu de d[i,j] operaciones. A la fin, l'elementu allugáu na parte INFERIOR derecha de la matriz contién la respuesta.

Implementación

De siguío puede vese la implementación de la función pa dellos llinguaxes de programación. Otros llinguaxes de más alto nível, como php o les funciones d'usuariu de MySQL, incorporar yá, ensin necesidá d'implementala pa ser usada.

int Levenshtein(char *s1,char *s2) {
 int t1,t2,i,j,*m,costu,res,anchu;

// Calcula tamañu strings 
 t1=strlen(s1); t2=strlen(s2);

// Verifica qu'esista daqué que comparar
 if (t1==0) return(t2);
 if (t2==0) return(t1);
 anchu=t1+1;

// Reserva matriz con malloc m[i,j] = m[j*anchu+i] !!
 m=(int*)malloc(sizeof(int)*(t1+1)*(t2+1));
 if (m==NULL) return(-1); // ERROR!!

// Rellena primer fila y primer columna for
 (i=0;i<=t1;i++) m[i]=i;
 for (j=0;j<=t2;j++) m[j*anchu]=j;

// Percorremos restu de la matriz enllenando pesos
 for (i=1;i<=t1;i++) for (j=1;j<=t2;j++)
 { if (s1[i-1]==s2[j-1]) costu=0; else costu=1;
 m[j*anchu+i]=Minimu(Minimu(m[j*anchu+i-1]+1, // Eliminacion 
 m[(j-1)*anchu+i]+1), // Insercion 
 m[(j-1)*anchu+i-1]+costu); } // Sustitucion 

// Devolvemos esquina final de la matriz
 res=m[t2*anchu+t1];
 free(m);
 return(res);
}

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2) {
 int N1 = s1.size();
 int N2 = s2.size();
 int i, j;
 vector<int> T(N2+1);

 for ( i = 0; i <= N2; i++ )
 T[i] = i;

 for ( i = 0; i < N1; i++ ) 
 {
 T[0] = i+1;
 int corner = i;
 for ( j = 0; j < N2; j++ ) 
 {
 int upper = T[j+1];
 if ( s1[i] == s2[j] )
 T[j+1] = corner;
 else
 T[j+1] = min(T[j], min(upper, corner)) + 1;
 corner = upper;
 }
 }
 return T[N2];
}

public int LevenshteinDistance(string s, string t, out double porcentaxe) {
 porcentaxe = 0;
 
 // d ye una tabla con m+1 renglones y n+1 columnes
 int costu = 0;
 int m = s.Length;
 int n = t.Length;
 int[,] d = new int[m + 1, n + 1]; 

 // Verifica qu'esista daqué que comparar
 if (n == 0) return m;
 if (m == 0) return n;

 // Enllena la primer columna y la primer fila.
 for (int i = 0; i <= m; d[i, 0] = i++) ;
 for (int j = 0; j <= n; d[0, j] = j++) ;
 
 
 /// percuerre la matriz enllenando cada unos de los pesos.
 /// i columnes, j renglones
 for (int i = 1; i <= m; i++)
 {
 // percuerre pa j
 for (int j = 1; j <= n; j++)
 { 
 /// si son iguales en posiciones equidistantes el pesu ye 0
 /// de lo contrario el pesu suma a unu.
 costu = (s[i - 1] == t[j - 1]) ? 0 : 1; 
 d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, //Eliminacion 
 d[i, j - 1] + 1), //Inserccion 
 d[i - 1, j - 1] + costu); //Sustitucion
 }
 }

 /// Calculamos el porcentaxe de cambeos na pallabra.
 if (s.Length > t.Length)
 porcentaxe = ((double)d[m, n] / (double)s.Length);
 else
 porcentaxe = ((double)d[m, n] / (double)t.Length); 
 return d[m, n]; 
}

public class LevenshteinDistance {
 private static int minimum(int a, int b, int c) {
 return Math.min(a, Math.min(b, c));
 }

 public static int computeLevenshteinDistance(String str1, String str2) {
 return computeLevenshteinDistance(str1.toCharArray(), str2.toCharArray());
 
 }

 private static int computeLevenshteinDistance(char [] str1, char [] str2) {
 int [][]distance = new int[str1.length+1][str2.length+1];

 for(int i=0;i<=str1.length;i++){
 distance[i][0]=i;
 }
 for(int j=0;j<=str2.length;j++){
 distance[0][j]=j;
 }
 for(int i=1;i<=str1.length;i++){
 for(int j=1;j<=str2.length;j++){ 
 distance[i][j]= minimum(distance[i-1][j]+1, distance[i][j-1]+1, distance[i-1][j-1]+
 
 
 ((str1[i-1]==str2[j-1])?0:1));
 }
 }
 return distance[str1.length][str2.length];
 
 }
}

sub fastdistance
{
my $word1 = shift;
my $word2 = shift;

return 0 if $word1 eq $word2;
my @d;

my $len1 = length $word1;
my $len2 = length $word2;

$d[0][0] = 0;
for (1.. $len1) {
$d[$_][0] = $_;
return $_ if $_!=$len1 && substr($word1,$_) eq
substr($word2,$_);
}

for (1.. $len2) {
$d[0][$_] = $_;
return $_ if $_!=$len2 && substr($word1,$_) eq
substr($word2,$_);
}

for my $i (1.. $len1) {
my $w1 = substr($word1,$i-1,1);
for (1.. $len2) {
$d[$i][$_] = _min($d[$i-1][$_]+1, $d[$i][$_-1]+1, $d[$i-1][$_-1]+($w1 

eq
substr($word2,$_-1,1) ?
0 : 1));
}
}
return $d[$len1][$len2];
}

sub _min
{
return $_[0] < $_[1]
? $_[0] < $_[2] ? $_[0] : $_[2]
: $_[1] < $_[2] ? $_[1] : $_[2];
}

d=dict()
for i in range(len(str1)+1):
d[i]=dict()
d[i][0]=i
for i in range(len(str2)+1):
d[0][i] = i
for i in range(1, len(str1)+1):
for j in range(1, len(str2)+1):
d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+(not str1[i-1] == str2[j-1]))
return d[len(str1)][len(str2)]

class String
 def levenshtein(other)
 other = other.to_s
 distance = Array.new(self.size + 1, 0)
 (0..self.size).each do |i|
 distance[i] = Array.new(other.size + 1)
 distance[i][0] = i
 end
 (0..other.size).each do |j|
 distance[0][j] = j
 end

 (1..self.size).each do |i|
 (1..other.size).each do |j|
 distance[i][j] = [distance[i - 1][j] + 1, distance[i][j
 - 1] + 1, distance[i
 - 1][j - 1] + ((self[i - 1] == other[j - 1]) ? 0 : 1)].min
 end
 end
 distance[self.size][other.size]
 end
end

puts "casa".levenshtein "cai" #=> 3

<?php
 $lev = levenshtein($input, $word);
?>

function LevenshteinDistance(Str1, Str2: String): Integer;
var
 d : array of array of Integer;
 Len1, Len2 : Integer;
 i,j,cost:Integer;
begin
 Len1:=Length(Str1);
 Len2:=Length(Str2);
 SetLength(d,Len1+1);
 for i := Low(d) to High(d) do SetLength(d[i],Len2+1);.
 

 for i := 0 to Len1 do d[i,0]:=i;.
 

 for j := 0 to Len2 do d[0,j]:=j;.
 

 for i:= 1 to Len1 do for
 j:= 1 to Len2 do begin
 
 if Str1[i]=Str2[j] then
 cost:=0
 else
 cost:=1;
 d[i,j]:= Min(d[i-1, j] + 1, // deletion, Min(d[i, j-1]
 + 1, // insertion
 d[i-1, j-1] + cost) // substitution
 );
 end;
 Result:=d[Len1,Len2];
end;

 Public Function Levenshtein(ByVal s1 As String, ByVal s2 As String) As Integer
 Dim costu As Integer = 0
 Dim n1 As Integer = s1.Length
 Dim n2 As Integer = s2.Length
 Dim m As Integer(,) = New Integer(n1, n2) {}
 For i As Integer = 0 To n1
 m(i, 0) = i
 Next
 For i As Integer = 1 To n2
 m(0, i) = i
 Next
 For i1 As Integer = 1 To n1
 For i2 As Integer = 1 To n2
 costu = If((s1(i1 - 1) = s2(i2 - 1)), 0, 1)
 m(i1, i2) = Math.Min(Math.Min(m(i1 - 1, i2) + 1, m(i1, i2 - 1) + 1), m(i1 - 1, i2 - 1) + costu)
 Next
 Next
 Return m(n1, n2)
 End Function

public class StringUtils 
{ 
 public static function levenshtein(s1:String, s2:String):int
 { 
 if (s1.length == 0 || s2.length == 0)
 return 0;

 var m:uint = s1.length + 1;
 var n:uint = s2.length + 1;
 var i:uint, j:uint, cost:uint;
 var d:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();
 
 for (i = 0; i < m; i++)
 {
 d[i] = new Vector.<int>();
 for (j = 0; j < n; j++)
 d[i][j] = 0;
 }
 
 for (i = 0; i < m; d[i][0] = i++) ;
 for (j = 0; j < n; d[0][j] = j++) ;

 for (i = 1; i < m; i++)
 {
 for (j = 1; j < n; j++)
 { 
 cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
 d[i][j] = Math.min(Math.min(d[i - 1][j] + 1, d[i][j
 - 1] + 1), d[i
 - 1][j - 1] + cost);
 }
 }
 
 return d[m-1][n-1];
 }
}

<cfscript>
function levDistance(s,t) {
 var d = ArrayNew(2);
 var i = 1;
 var j = 1;
 var s_i = "A";
 var t_j = "A";
 var cost = 0;
 
 var n = len(s)+1;
 var m = len(t)+1;
 
 d[n][m]=0;
 
 if (n is 1) {
 return m;
 }
 
 if (m is 1) {
 return n;
 }
 
 for (i = 1; i lte n; i=i+1) {
 d[i][1] = i-1;
 }

 for (j = 1; j lte m; j=j+1) {
 d[1][j] = j-1;
 }
 
 for (i = 2; i lte n; i=i+1) {
 s_i = Mid(s,i-1,1);

 for (j = 2; j lte m; j=j+1) {
 t_j = Mid(t,j-1,1);

 if (s_i is t_j) {
 cost = 0;
 }
 else {
 cost = 1;
 }
 d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1);
 d[i][j] = min(d[i][j], d[i-1][j-1] + cost);
 }
 }
 
 return d[n][m];
}
</cfscript>

/*
LevenshteinSubminimal(String A, String B) -> {k: Integer, t: String}
 A, ye la cadena qu'introduz l'usuariu B,
 ye la cadena candidata a ser alternativa del usuariu k,
 ye la mínima Levenshtein d'A sobre toles subcadenas de B
 t, ye la cadena con menor alloña Levenshtein
*/
function LevenshteinSubminimal(A, B) {
 var a = A.length;
 var b = B.length;

 // siempres comparamos A coles subcadenas de B
 var f = function(s){return Levenshtein(A, s)};

 // si A ye mayor que B nun comparamos subcadenas
 if(a >= b)
 return {k: f(B), t: B}

 // peor casu y cotes
 var m = {k: b+2, t: null}, c1 = a-1, c2 = a+1;
 for(var p = 0; p < b - c1; p++)
 for(var l = c1, c3 = Math.min(c2, b - p); l <= c3; l++) {
 var t = B.substr(p, l), k = f(t);
 // meyor casu if(m.k
 >= k)
 m = {k: k, t: t};
 }
 return m;
}

function levenshtein(s1, s2) {
 var l1 = s1.length;
 var l2 = s2.length;
 var d = [];
 var c = 0;
 var a = 0;

 if(l1 == 0)
 return l2;

 if(l2 == 0)
 return l1;

 var d = new Buffer((l1 + 1) * (l2 + 1));
 a = l1 + 1;

 for(var i = 0; i <= l1; d[i] = i++);
 for(var j = 0; j <= l2; d[j * a] = j++);

 for(var i = 1; i <= l1; i++) {
 for(var j = 1; j <= l2; j++) {
 if(s1[i - 1] == s2[j - 1])
 c = 0;
 else
 c = 1;
 var r = d[j * a + i - 1] + 1;
 var s = d[(j - 1) * a + i] + 1;
 var t = d[(j - 1) * a + i - 1] + c;

 d[j * a + i] = Math.min(Math.min(r, s), t);
 }
 }

 return(d[l2 * a + l1]);
}

Aplicaciones

• El proyeutu ASJP usa la distancia de Levenshtein total nuna llista de pallabres en distintes llingües del mundu, pa midir la "similaridad" o "cercanía" de les mesmes, esa distancia calculada puede emplegase pa proponer una clasificación filoxenética tentativa de les llingües del mundu.^[2]
• La distancia de Damerau-Levenshtein ye una xeneralización de la distancia de Levenshtein usada polos correutor ortográficos y na detección de fraudes en llistes de datos.

Ver tamién

• Distancia de Damerau-Levenshtein
• Algoritmu Needleman-Wunsch
• Algoritmu Smith-Waterman
• Algoritmu Bitap
• Autómata de Levenshtein
• Espaciu métricu
• Agrep
• Ratcliff/Obershelp
• Dynamic time warping
• Distancia de Jaro-Winkler

Referencies