Distancia de Levenshtein

Apariencia mover a la barra lateral ocultar

La distancia de Levenshtein, distancia de edición o distancia entre palabras es el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra, se usa ampliamente en teoría de la información y ciencias de la computación. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupó 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 ortográficos.

Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

  1. casa → cala (sustitución de 's' por 'l')
  2. cala → calla (inserción de 'l' entre 'l' y 'a')
  3. calla → calle (sustitución de 'a' por 'e')

Se le considera una generalización de la distancia de Hamming, que solo compara cadenas de la misma longitud y solo considera como operación la sustitució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.

Como buena "distancia", cumple (aunque es complicado demostrarlo formalmente), que:

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

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

El algoritmo

Se trata de un algoritmo de tipo bottom-up, común en programación dinámica. Se apoya en el uso de una matriz (n + 1) × (m + 1), donde n y m son las longitudes de las 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, char str2) // d is a table with lenStr1+1 rows and lenStr2+1 columns declare int d // i and j are used to iterate over str1 and str2 declare int i, j, cost for i from 0 to lenStr1 d := i for j from 0 to lenStr2 d := j for i from 1 to lenStr1 for j from 1 to lenStr2 if str1 = str2 then cost := 0 else cost := 1 d := minimum( d + 1, // deletion d + 1, // insertion d + cost // substitution ) return d

El invariante mantenido a través del algoritmo es que pueda transformar el segmento inicial str1 en str2 empleando un mínimo de d operaciones. Al final, el elemento ubicado en la parte INFERIOR derecha de la matriz contiene la respuesta.

Implementación

A continuación se puede ver la implementación de la función para varios lenguajes de programación. Otros lenguajes de más alto nivel, como php o las funciones de usuario de MySQL, las incorporan ya, sin necesidad de implementarla para ser usada.

C

#define Min(x,y) ((x)<(y) ? (x) : (y)) #define Min3(x,y,z) Min(Min((x),(y)),(z)) int Levenshtein(char *s1,char *s2) { int t1, t2, i, j, *m, costo, res, ancho; // Calcula tamanos strings t1 = strlen(s1); t2 = strlen(s2); // Verifica que exista algo que comparar if (t1==0) return(t2); if (t2==0) return(t1); ancho = t1+1; // Reserva matriz con malloc m = m !! m = (int*) malloc(sizeof(int)*(t1+1)*(t2+1)); if (m==NULL) return(-1); // ERROR!! // Rellena primera fila y primera columna for (i=0; i<=t1; i++) { m = i; } for (j=0; j<=t2; j++) { m = j; } // Recorremos resto de la matriz llenando pesos for (i=1;i<=t1;i++) { for (j=1;j<=t2;j++) { if (s1==s2){ costo=0; } else { costo=1; } m = Min3(m+1, // Eliminacion m+1, // Insercion m+costo); // Sustitucion } } // Devolvemos esquina final de la matriz res = m; 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; for ( i = 0; i < N1; i++ ) { T = i+1; int corner = i; for ( j = 0; j < N2; j++ ) { int upper = T; if ( s1 == s2 ) T = corner; else T = min(T, min(upper, corner)) + 1; corner = upper; } } return T; }

C#

public int LevenshteinDistance(string s, string t, out double porcentaje) { porcentaje = 0; // d es una tabla con m+1 renglones y n+1 columnas int costo = 0; int m = s.Length; int n = t.Length; int d = new int; // Verifica que exista algo que comparar if (n == 0) return m; if (m == 0) return n; // Llena la primera columna y la primera fila. for (int i = 0; i <= m; d = i++) ; for (int j = 0; j <= n; d = j++) ; /// recorre la matriz llenando cada unos de los pesos. /// i columnas, j renglones for (int i = 1; i <= m; i++) { // recorre para j for (int j = 1; j <= n; j++) { /// si son iguales en posiciones equidistantes el peso es 0 /// de lo contrario el peso suma a uno. costo = (s == t) ? 0 : 1; d = System.Math.Min(System.Math.Min(d + 1, //Eliminacion d + 1), //Insercion d + costo); //Sustitucion } } /// Calculamos el porcentaje de cambios en la palabra. if (s.Length > t.Length) porcentaje = ((double)d / (double)s.Length); else porcentaje = ((double)d / (double)t.Length); return d; }

Go

func LevenshteinDistance(s string, t string) (float64,float64) { // Costo penaliza si hay un cambio en el caracter. var costo float64 = 0 // Obtenemos la longitud de las cadenas para crear los slices. m, n := len(s), len(t) d := make(float64,m+1, m*n) // Generamos el slice interno. for idx := range d{ d = make(float64,n+1) } // Recorre la matriz de acuerdo a los cambios que encuentre en la cadena. for i:=1; i<=m;i++{ for j:=1; j <= n; j++{ if s== t { costo = 0} else { costo = 1} oper := math.Min(math.Min(d+1, // Eliminacion d+1), // Inserccion d+costo) // Sustitucion d = oper } } // Calcula el ratio de cambios en la palabra. var porcentaje float64 = 0 if len(s) > len(t){ porcentaje = d / float64(len(s)) }else{ porcentaje = d / float64(len(t)) } // Regresa distancia y ratio. return d, porcentaje }

Java

Implementado 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; for(int i=0;i<=str1.length;i++){ distance=i; } for(int j=0;j<=str2.length;j++){ distance=j; } for(int i=1;i<=str1.length;i++){ for(int j=1;j<=str2.length;j++){ distance= minimum(distance+1, distance+1, distance+ ((str1==str2)?0:1)); } } return distance; } }

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; for (1.. $len1) { $d = $_; return $_ if $_!=$len1 && substr($word1,$_) eq substr($word2,$_); } for (1.. $len2) { $d = $_; return $_ if $_!=$len2 && substr($word1,$_) eq substr($word2,$_); } for my $i (1.. $len1) { my $w1 = substr($word1,$i-1,1); for (1.. $len2) { $d = _min($d+1, $d+1, $d+($w1 eq substr($word2,$_-1,1) ? 0 : 1)); } } return $d; } sub _min { return $_ < $_ ? $_ < $_ ? $_ : $_ : $_ < $_ ? $_ : $_; }

Python

def distance(str1, str2): d=dict() for i in range(len(str1)+1): d=dict() d=i for i in range(len(str2)+1): d = i for i in range(1, len(str1)+1): for j in range(1, len(str2)+1): d = min(d+1, d+1, d+(not str1 == str2)) return d

Ruby

class String def levenshtein(other) other = other.to_s distance = Array.new(self.size + 1, 0) (0..self.size).each do |i| distance = Array.new(other.size + 1) distance = i end (0..other.size).each do |j| distance = j end (1..self.size).each do |i| (1..other.size).each do |j| distance = + 1, distance + 1, distance + ((self == other) ? 0 : 1)].min end end distance end end puts "casa".levenshtein "calle" #=> 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,Len2+1); for i := 0 to Len1 do d:=i; for j := 0 to Len2 do d:=j; for i:= 1 to Len1 do for j:= 1 to Len2 do begin if Str1=Str2 then cost:=0 else cost:=1; d:= Min(d + 1, // deletion, Min(d + 1, // insertion d + cost) // substitution ); end; Result:=d; end;

VB.NET

Public Function Levenshtein(ByVal s1 As String, ByVal s2 As String) As Integer Dim coste 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 = 0 To n2 m(0, i) = i Next For i1 As Integer = 1 To n1 For i2 As Integer = 1 To n2 coste = 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) + coste) 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 = new Vector.<int>(); for (j = 0; j < n; j++) d = 0; } for (i = 0; i < m; d = i++) ; for (j = 0; j < n; d = 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 = Math.min(Math.min(d + 1, d + 1), d + cost); } } return d; } }

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=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; } for (j = 1; j lte m; j=j+1) { d = 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 = min(d+1, d+1); d = min(d, d + cost); } } return d; } </cfscript>

JavaScript​

/* LevenshteinSubminimal(String A, String B) -> {k: Integer, t: String} A, es la cadena que introduce el usuario B, es la cadena candidata a ser alternativa del usuario k, es la mínima Levenshtein de A sobre todas las subcadenas de B t, es la cadena con menor distancia Levenshtein */ function LevenshteinSubminimal(A, B) { var a = A.length; var b = B.length; // siempre comparamos A con las subcadenas de B var f = function(s){return Levenshtein(A, s)}; // si A es mayor que B no comparamos subcadenas if(a >= b) return {k: f(B), t: B} // peor caso y cotas 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); // mejor caso 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 = Buffer.alloc((l1 + 1) * (l2 + 1)); a = l1 + 1; for(var i = 0; i <= l1; d = i++); for(var j = 0; j <= l2; d = j++); for(var i = 1; i <= l1; i++) { for(var j = 1; j <= l2; j++) { if(s1 == s2) c = 0; else c = 1; var r = d + 1; var s = d + 1; var t = d + c; d = Math.min(Math.min(r, s), t); } } return(d); }

Aplicaciones

Véase también

Referencias

  1. ↑ «Levenshtein substring minimal distance, javascript implementation». Gist. Consultado el 9 de diciembre de 2015. 
  2. ↑ ASJP offical page
  3. ↑ ASJP - World Language Tree