Distancia de Levenshtein
De Wikipedia, la enciclopedia libre
En la Teoría de la información y en la ciencia de computadores se llama Distancia de Levenshtein o distancia de edición el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación o la substitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupara de esta distancia en 1965. Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.
Por ejemplo, la distancia de Levenshtein entre "kitten" y "sitting" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.
- kitten ? sitten (sustitución de 'k' por 's')
- sitten ? sittin (sustitución de 'e' por 'i')
- sittin ? sitting (inserción de 'g' al final)
Se le considera una generalización de la distancia de Hamming, que se usa para cadenas de la misma longitud y que solo considera como operación la substitución. Hay otras generalizaciones de la distancia de Levenshtein, como la distancia de Damerau-Levenshtein, que consideran el intercambio de dos caracteres como una operación
Tabla de contenidos |
[editar] El algoritmo
Se trata de un algoritmo muy común de tipo bottom-up programación dinámica empleado en el cálculo de la distancia de Levenshtein y que implementa el uso de matriz (n + 1) × (m + 1), donde n y m son las longitudes de los cadenas. Aquí se indica el algoritmo en pseudocódigo para una función LevenshteinDistance que toma dos cadenas, str1 de longitud lenStr1, y str2 de longitud lenStr2, y calcula la distancia Levenshtein entre 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] = str2[j] 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]
El invariante mantenido a través del algorítmo es que pueda transformar el segmento inicial str1[1..i] en str2[1..j] empleando un mínimo de d[i,j] operaciones. Al final, el elemento ubicado en la parte INFERIOR derecha de la cadena contiene la respuesta.
[editar] Implementación
A continuación se puede encontrar la implementación de la función para varios lenguajes de programación. Otros lenguajes de más alto nível, como php o la funciones de usuario de MySQL, las incorporan ya, sin necesidad de implementarla para se usada.
[editar] C++
#include <string> #include <vector> #include <algorithm> using namespace std; int levenshtein(const string &s1, const string &s2) { string::size_type N1 = s1.length(); string::size_type N2 = s2.length(); string::size_type 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]; }
[editar] Java
Implementado como una clase estática.
public class LevenshteinDistance { private static int minimum(int a, int b, int c) { if(a<=b && a<=c) return a; if(b<=a && b<=c) return b; return 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]; } }
[editar] 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];
}
[editar] 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)]
[editar] Ruby
def self.LevenshteinDistance(str1,str2)
distance = Array.new(str1.size+1, 0)
for i in 0..str1.size
distance[i] = Array.new(str2.length+1)
distance[i][0] = i
end
for j in 0..(str2.size)
distance[0][j] = j
end
for i in 1..str1.size
for j in 1..str2.size
distance[i][j] = [distance[i-1][j]+1 ,
distance[i][j-1]+1 ,
distance[i-1][j-1]+((str1[i-1]==str2[j-1])? 0:1)].min
end
end
return distance[str1.size][str2.size];
end
[editar] 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;
[editar] 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>
[editar] Véase también
- Distancia de Damerau-Levenshtein
- algoritmo Needleman-Wunsch
- algoritmo Smith-Waterman
- algoritmo Bitap
- Autómata de Levenshtein
- espacio métrico
- agrep
- Ratcliff/Obershelp
- Dynamic time warping
- Jaro-Winkler distance
