Distancia de Levenshtein

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.

 casa → cala (sustitución de 's' por 'l')
 cala → calla (insertamientu de 'l' ente 'l' y 'a')
 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.

 C 
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);
}

 C++ 
#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];
}

 C# 
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]; 
} 


 Java 
Implementáu como una clase estática.

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];

 }
}

 Perl 

 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];
 }

 Python 
def distance(str1, str2):
 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)]

 Ruby 
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 
<?php
 $lev = levenshtein($input, $word);
?>

 Delphi 
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;

 VB.NET 
 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

 ActionScript 3.0 
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];
 }
}

 ColdFusion 
<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>

 JavaScript 
/*
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;
}

 JavaScript (NodeJS) 
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.ASJP - World Language Tree
 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 

Categoría:Algoritmos