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 un string en otro. 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 strings, 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 (substitución de 'k' para 's')
sitten ? sittin (substitución de 'e' para 'i')
sittin ? sitting (inserta 'g' al final)

Se le considera una generalización de la distancia de Hamming, que se usa para strings de la misma longitud y que solo considera como operación la substitución. Hay otras generalizaciones de la distancia de Levenshtein, como el considerar el cambio de dos caracteres como una operación.

[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 superior derecha de la cadena contiene la respuesta.

[editar] Implementación

[editar] C++

const unsigned int cost_del = 1;
const unsigned int cost_ins = 1;
const unsigned int cost_sub = 1;

unsigned int edit_distance( const std::string& s1, const std::string& s2 )
{
  unsigned int n1 = s1.length();
  unsigned int n2 = s2.length();

  unsigned int* p = new unsigned int[n2+1];
  unsigned int* q = new unsigned int[n2+1];
  unsigned int* r;

  p[0] = 0;
  for( unsigned int j = 1; j <= n2; ++j )
    p[j] = p[j-1] + cost_ins;

  for( unsigned int i = 1; i <= n1; ++i )
    {
      q[0] = p[0] + cost_del;
      for( unsigned int j = 1; j <= n2; ++j )
        {
          unsigned int d_del = p[j] + cost_del;
          unsigned int d_ins = q[j-1] + cost_ins;
          unsigned int d_sub = p[j-1] + ( s1[i-1] == s2[j-1] ? 0 : cost_sub );
          q[j] = std::min( std::min( d_del, d_ins ), d_sub );
      }
      r = p;
      p = q;
      q = r;
    }

  unsigned int tmp = p[n2];
  delete[] p;
  delete[] q;

  return tmp;
}

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

        for(int i=0;i<=str1.length;i++)
            {
                distance[i]=new int[str2.length+1];
                distance[i][0]=i;
            }
        for(int j=0;j<str2.length+1;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];
}