fbpx
Wikipedia

Distancia de Levenshtein

Febrero 20, 2022

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 se usa para cadenas de la misma longitud y que 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[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]

El invariante mantenido a través del algoritmo 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 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

int Levenshtein(char *s1,char *s2) { int t1,t2,i,j,*m,costo,res,ancho; // Calcula tamanios 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[i,j] = m[j*ancho+i] !!  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]=i;  for (j=0;j<=t2;j++) m[j*ancho]=j; // Recorremos resto de la matriz llenando pesos  for (i=1;i<=t1;i++) for (j=1;j<=t2;j++)  { if (s1[i-1]==s2[j-1]) costo=0; else costo=1;  m[j*ancho+i]=Minimo(Minimo(m[j*ancho+i-1]+1, // Eliminacion   m[(j-1)*ancho+i]+1), // Insercion   m[(j-1)*ancho+i-1]+costo); } // Sustitucion  // Devolvemos esquina final de la matriz  res=m[t2*ancho+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 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[m + 1, n + 1]; // 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, 0] = i++) ; for (int j = 0; j <= n; d[0, j] = 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[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), //Insercion  d[i - 1, j - 1] + costo); //Sustitucion } } /// Calculamos el porcentaje de cambios en la palabra. if (s.Length > t.Length) porcentaje = ((double)d[m, n] / (double)s.Length); else porcentaje = ((double)d[m, n] / (double)t.Length); return d[m, n]; }

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[idx] = 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[i-1]== t[j-1] { costo = 0} else { costo = 1}  oper := math.Min(math.Min(d[i-1][j]+1, // Eliminacion  d[i][j-1]+1), // Inserccion  d[i-1][j-1]+costo) // Sustitucion  d[i][j] = oper  }  }   // Calcula el ratio de cambios en la palabra.  var porcentaje float64 = 0  if len(s) > len(t){  porcentaje = d[m][n] / float64(len(s))  }else{  porcentaje = d[m][n] / float64(len(t))  }   // Regresa distancia y ratio.  return d[m][n], 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[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 "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[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 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[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[1]​

/* 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] = 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 proyecto ASJP usa la distancia de Levenshtein total en una lista de palabras en diferentes lenguas del mundo, para medir la "similitud" o "cercanía" de las mismas, esa distancia calculada puede emplearse para proponer una clasificación filogenética tentativa de las lenguas del mundo.[2]​
  • La distancia de Damerau-Levenshtein es una generalización de la distancia de Levenshtein usada por los correctores ortográficos y en la detección de fraudes en listas de datos.

Véase también

Referencias

  1. «Levenshtein substring minimal distance, javascript implementation». Gist. Consultado el 9 de diciembre de 2015. 
  •   Datos: Q496939

Febrero 20, 2022
distancia, levenshtein, distancia, levenshtein, distancia, edición, distancia, entre, palabras, número, mínimo, operaciones, requeridas, para, transformar, cadena, caracteres, otra, ampliamente, teoría, información, ciencias, computación, entiende, operación, . La distancia de Levenshtein distancia de edicion o distancia entre palabras es el numero minimo de operaciones requeridas para transformar una cadena de caracteres en otra se usa ampliamente en teoria de la informacion y ciencias de la computacion Se entiende por operacion bien una insercion eliminacion o la sustitucion de un caracter Esta distancia recibe ese nombre en honor al cientifico ruso Vladimir Levenshtein quien se ocupo de esta distancia en 1965 Es util en programas que determinan cuan similares son dos cadenas de caracteres como es el caso de los correctores ortograficos 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 casa cala sustitucion de s por l cala calla insercion de l entre l y a calla calle sustitucion de a por e Se le considera una generalizacion de la distancia de Hamming que se usa para cadenas de la misma longitud y que solo considera como operacion la sustitucion Hay otras generalizaciones de la distancia de Levenshtein como la distancia de Damerau Levenshtein que consideran el intercambio de dos caracteres como una operacion Como buena distancia cumple aunque es complicado demostrarlo formalmente que Dist A B Dist B A Dist A B Dist B C gt Dist A C Indice 1 El algoritmo 2 Implementacion 2 1 C 2 2 C 2 3 C 2 4 Go 2 5 Java 2 6 Perl 2 7 Python 2 8 Ruby 2 9 PHP 2 10 Delphi 2 11 VB NET 2 12 ActionScript 3 0 2 13 ColdFusion 2 14 JavaScript 1 2 15 JavaScript NodeJS 3 Aplicaciones 4 Vease tambien 5 ReferenciasEl algoritmo EditarSe trata de un algoritmo de tipo bottom up comun en programacion dinamica Se apoya en el uso de una matriz n 1 m 1 donde n y m son las longitudes de las cadenas Aqui se indica el algoritmo en pseudocodigo para una funcion 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 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 El invariante mantenido a traves del algoritmo es que pueda transformar el segmento inicial str1 1 i en str2 1 j empleando un minimo de d i j operaciones Al final el elemento ubicado en la parte INFERIOR derecha de la matriz contiene la respuesta Implementacion EditarA continuacion se puede ver la implementacion de la funcion para varios lenguajes de programacion Otros lenguajes de mas alto nivel como php o las funciones de usuario de MySQL las incorporan ya sin necesidad de implementarla para ser usada C Editar int Levenshtein char s1 char s2 int t1 t2 i j m costo res ancho Calcula tamanios 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 i j m j ancho i 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 lt t1 i m i i for j 0 j lt t2 j m j ancho j Recorremos resto de la matriz llenando pesos for i 1 i lt t1 i for j 1 j lt t2 j if s1 i 1 s2 j 1 costo 0 else costo 1 m j ancho i Minimo Minimo m j ancho i 1 1 Eliminacion m j 1 ancho i 1 Insercion m j 1 ancho i 1 costo Sustitucion Devolvemos esquina final de la matriz res m t2 ancho t1 free m return res C Editar include lt string gt include lt vector gt include lt algorithm gt using namespace std int levenshtein const string amp s1 const string amp s2 int N1 s1 size int N2 s2 size int i j vector lt int gt T N2 1 for i 0 i lt N2 i T i i for i 0 i lt N1 i T 0 i 1 int corner i for j 0 j lt 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 Editar 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 m 1 n 1 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 lt m d i 0 i for int j 0 j lt n d 0 j j recorre la matriz llenando cada unos de los pesos i columnas j renglones for int i 1 i lt m i recorre para j for int j 1 j lt n j si son iguales en posiciones equidistantes el peso es 0 de lo contrario el peso suma a uno costo 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 Insercion d i 1 j 1 costo Sustitucion Calculamos el porcentaje de cambios en la palabra if s Length gt t Length porcentaje double d m n double s Length else porcentaje double d m n double t Length return d m n Go Editar 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 idx make float64 n 1 Recorre la matriz de acuerdo a los cambios que encuentre en la cadena for i 1 i lt m i for j 1 j lt n j if s i 1 t j 1 costo 0 else costo 1 oper math Min math Min d i 1 j 1 Eliminacion d i j 1 1 Inserccion d i 1 j 1 costo Sustitucion d i j oper Calcula el ratio de cambios en la palabra var porcentaje float64 0 if len s gt len t porcentaje d m n float64 len s else porcentaje d m n float64 len t Regresa distancia y ratio return d m n porcentaje Java Editar Implementado como una clase estatica 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 lt str1 length i distance i 0 i for int j 0 j lt str2 length j distance 0 j j for int i 1 i lt str1 length i for int j 1 j lt 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 Editar 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 amp amp substr word1 eq substr word2 for 1 len2 d 0 return if len2 amp amp 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 lt 1 0 lt 2 0 2 1 lt 2 1 2 Python Editar 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 Editar 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 calle gt 3 PHP Editar lt php lev levenshtein input word gt Delphi Editar 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 Editar 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 Editar 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 lt Vector lt int gt gt new Vector lt Vector lt int gt gt for i 0 i lt m i d i new Vector lt int gt for j 0 j lt n j d i j 0 for i 0 i lt m d i 0 i for j 0 j lt n d 0 j j for i 1 i lt m i for j 1 j lt 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 Editar lt cfscript gt 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 lt cfscript gt JavaScript 1 Editar LevenshteinSubminimal String A String B gt 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 minima 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 gt 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 lt b c1 p for var l c1 c3 Math min c2 b p l lt c3 l var t B substr p l k f t mejor caso if m k gt k m k k t t return m JavaScript NodeJS Editar 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 lt l1 d i i for var j 0 j lt l2 d j a j for var i 1 i lt l1 i for var j 1 j lt 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 EditarEl proyecto ASJP usa la distancia de Levenshtein total en una lista de palabras en diferentes lenguas del mundo para medir la similitud o cercania de las mismas esa distancia calculada puede emplearse para proponer una clasificacion filogenetica tentativa de las lenguas del mundo 2 La distancia de Damerau Levenshtein es una generalizacion de la distancia de Levenshtein usada por los correctores ortograficos y en la deteccion de fraudes en listas de datos Vease tambien EditarDistancia de Damerau Levenshtein Algoritmo Needleman Wunsch Algoritmo Smith Waterman Algoritmo Bitap Automata de Levenshtein Espacio metrico Agrep Ratcliff Obershelp Dynamic time warping Distancia de Jaro WinklerReferencias Editar Levenshtein substring minimal distance javascript implementation Gist Consultado el 9 de diciembre de 2015 ASJP World Language Tree Datos Q496939 Obtenido de https es wikipedia org w index php title Distancia de Levenshtein amp oldid 137720199, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos