Distancia de Levenshtein

Distancia de Levenshtein

Distancia de Levenshtein

En Teoría de la información y Ciencias de la Computación se llama Distancia de Levenshtein, distancia de edición, o distancia entre palabras, al 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 sustitució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 "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

Contenido

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 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 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 nível, como php o la funciones de usuario de MySQL, las incorporan ya, sin necesidad de implementarla para ser usada.

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),                             //Inserccion 
                          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]; 
}

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

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

  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

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;

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>

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Distancia de Levenshtein — Se llama Distancia de Levenshtein o distancia de edición el número mínimo de operaciones requeridas para transformar un string en otro. Se entiende por operación una inserción, eliminación o substitución de un carácter. Esta distancia recibe ese… …   Enciclopedia Universal

  • Distancia de Damerau-Levenshtein — Saltar a navegación, búsqueda En la teoría de la información y en la ciencia de computadores, se llama distancia de Damerau Levenshtein o distancia de edición al número mínimo de operaciones requeridas para transformar una cadena de caracteres en …   Wikipedia Español

  • Distancia de Hamming — Saltar a navegación, búsqueda En Teoría de la Información se denomina distancia de Hamming a la efectividad de los códigos de bloque y depende de la diferencia entre una palabra de código válida y otra. Cuanto mayor sea esta diferencia, menor es… …   Wikipedia Español

  • Vladimir Levenshtein — Vladimir Iosifovich Levenshtein (en ruso: Владимир Иосифович Левенштейн) (nacido en 1935) es matemático y científico ruso de origen judío cuya principal área de investigación es la teoria de la información y los códigos de corrección de errores,… …   Wikipedia Español

  • Lenguas bereberes — Distribución geográfica: Norte de África Países:  Marruecos …   Wikipedia Español

  • Diff — Saltar a navegación, búsqueda En informática, diff es una utilidad para la comparación de archivos que genera las diferencias entre dos archivos o los cambios realizados en un archivo determinado comparándolo con una versión anterior del mismo… …   Wikipedia Español

  • Lenguas eslavas — Distribución geográfica: Europa Oriental y central Países:  República Checa …   Wikipedia Español

  • Lenguas mataco-guaicurú — Distribución geográfica: Gran Chaco Países:  Argentina …   Wikipedia Español

  • Lenguas tacanas — Distribución geográfica: Amazonía Países:  Bolivia …   Wikipedia Español

  • Lenguas uto-aztecas — Lenguas utoaztecas Distribución geográfica: América del Norte Países:  Estados Unidos …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”