Distancia de Levenshtein

De Wikipedia
Saltar a navegación Saltar a la gueta

La distancia de Levenshtein, distancia d'edición o distancia ente palabres 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 corrector d'ortografía correctores 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[editar | editar la fonte]

Tratar 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 llabre 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 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[editar | editar la fonte]

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[editar | editar la fonte]

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

// Calcula tamanios 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); // ERRU!!

// 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]) costo=0; else costo=1;
         m[j*anchu+i]=Minimo(Minimo(m[j*anchu+i-1]+1, //     Eliminacion 
                        m[(j-1)*anchu+i]+1), //              Insercion   
                        m[(j-1)*anchu+i-1]+costo); }      // Sustitucion 

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

C++[editar | editar la fonte]

#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#[editar | editar la fonte]

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 costo = 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.
            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), //Inserccion                              
                          d[i - 1, j - 1] + costo);                     //Sustitucion
         }
    }

   /// Calculamos el porcentaxe de cambeos na palabra.
    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[editar | editar la fonte]

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[editar | editar la fonte]

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[editar | editar la fonte]

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 | editar la fonte]

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[editar | editar la fonte]

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

Delphi[editar | editar la fonte]

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 | editar la fonte]

    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[editar | editar la fonte]

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[editar | editar la fonte]

<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][editar | editar la fonte]

/*
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 toos les 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)[editar | editar la fonte]

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[editar | editar la fonte]

  • El proyectu ASJP usa la distancia de Levenshtein total nuna llista de palabres 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 filogené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 corrector ortográficos y na detección de fraudes en llistes de datos.

Ver tamién[editar | editar la fonte]

Referencies[editar | editar la fonte]


Distancia de Levenshtein