7 replies to this topic

[Agustin Ortu]

Hola a todos
 
Existe una variedad de algoritmos que calculan la "distancia" entre dos string. La distancia esta determinada por el numero de operaciones que se deben realizar (agregar, cambiar o eliminar un caracter, o la transposicion o intercambio entre dos caracteres) para que el string "A" se convierta en el string "B". Logicamente, a mayor distancia, menos parecido seran los string entre si (estan "muy lejos") y cuanto mas cerca mas parecidos; una distancia de 0 indica que los dos son iguales
 
Es cierto que alguna vez este tema se trato en los foros. Alli, Héctor Randolph compartio la implementacion de la Distancia de Levenshtein. Si bien su implementacion es perfectamente correcta, mi aporte es dos algoritmos mas para calcular distancias
 
Uno de ellos es la Distancia de Damerau-Levenshtein, en la que la diferencia con el anterior es que la operacion de transposicion tiene "mayor peso". En el algoritmo de Levenshtein, todas las operaciones "pesan 1", es decir, suman 1 en la distancia. En este algoritmo, la transposicion sumara 2.
 
El segundo algoritmo es el de "Distancia" Optima; entre comillas, porque no es una distancia propiamente dicha (no cumple con la Desigualdad Triangular). La diferencia con el algoritmo de Damerau-Levenshtein es que agrega una condicion "ningun sub-string es editado mas de una vez"
 
Aqui esta la "mini biblioteca"
 
https://github.com/o...iStringDistance
 
Hay algunos tests en donde se muestra el uso, pero es bastante sencillo.(Utilizo DUnitX para los tests, y quien no este familiarizado con atributos puede parecer "raro")
 
Lo mas importante para el usuario es la unidad StringDistance, en donde se define la interfaz IStringDistance
 

delphi

/// <summary> Calcula la distancia entre dos string </summary>
  IStringDistance = interface
    ['{2D3C5367-4921-48ED-AF09-FB799B55C1AB}']
    function Distance(const A, B: string): Integer;
  end;

 
Luego, la misma unidad tiene una fabrica de interfaces IStringDistance, es decir, algoritmos de computo de distancias entre strings:
 

delphi

/// <summary> Fabrica de algoritmos de comparacion de strings </summary>
  StringDistanceAlgorithm = record
  public
    /// <summary> Devuelve una implementacion del algoritmo de distancia de Levenshtein </summary>
    class function Levenshtein: IStringDistance; static;
    /// <summary> Devuelve una implementacion del algoritmo de distancia de Damerau-Levenshtein </summary>
    class function DamerauLevenshtein: IStringDistance; static;
    /// <summary> Devuelve una implementacion del algoritmo de distancia de alineamiento de cadenas optimo (OSA) </summary>
    class function OptimalStringAlignment: IStringDistance; static;
  end;

 
Por lo tanto, el uso es tan sencillo como esto:
 

delphi

var
  A, B: string;
  Distance: Integer;
begin
  A := 'kitten';
  B := 'sitting';
  Distance := StringDistanceAlgorithm.Levenshtein.Distance(A, B);
  // Distance = 3;
 
  A := 'CA';
  B := 'ABC';
  Distance := StringDistanceAlgorithm.DamerauLevenshtein.Distance(A, B);
  // Distance = 2;
 
  A := 'CA';
  B := 'ABC';
  Distance := StringDistanceAlgorithm.OptimalStringAlignment.Distance(A, B);
  // Distance = 3;
end;

Hay unos cuantos mas algoritmos de distancia para implementar, por ejemplo la Distancia de Hamming, el Algoritmo de Hirschberg o el LCS

 

Saludos

[egostar]

Hola amigo Agustín

 

Por demás interesante ésta forma de "comparar" cadenas de caracteres, he descargado tu biblioteca para analizarla y aprender de tu generoso conocimiento.

 

Saludos

[Delphius]

Había escuchado sobre la Distancia de Levenshtein y la de Hamming, y medio descolgado alguna vez en alguna cátedra. Pero de las otras no estaba informado.

 

Los temas relacionados con la ciencias en/de la computación son cosas que me hubiera gustado tener un poco más de formación. En cierta forma siento que quedamos "descolgados" con lo que se aprende sobre estructuras de datos y algoritmos en las carreras más orientadas a Ingeniería. Como que vemos lo basico e intermedio, pero no más. En mi opinión, no vendría mal un poco más de perfil científico y explorar el área de las ciencias, fortalecer más sobre estructuras de datos complejas y algoritmos... al menos.

 

Esto por ejemplo, apenas tuvo una mención al pasar. Sino fuera porque tengo una mente más curiosa no me hubiera puesto a descubrir más sobre otros tipos de árboles, ni me tomaría la molestia de analizar y estudiar mis algoritmos para ver si son lo suficiente aceptables u óptimos. Tanto en términos de complejidad ciclomática, notación O y en uso de memoria.

 

Saludos,

[ELKurgan]

Gracias por compartir

 

Saludos

[FerCastro]

Excelente aporte. Tuve que hacer algo parecido hace unos meses y de mucha ayuda el algoritmo. 

[Agustin Ortu]

Mi idea en un futuro es poder crear un componente o algo que se enganche a un Edit, ComboBox, o similares para mostrar lista de sugerencias usando estos algoritmos

 

Tendria que investigar tambien que estrategia se debe usar cuando el "diccionario" de palabras a comparar es muy grande.

Tambien estaria bueno poder tener un parametro que "corte" el algoritmo para directamente descartar strings muy diferentes

[egostar]

Mi idea en un futuro es poder crear un componente o algo que se enganche a un Edit, ComboBox, o similares para mostrar lista de sugerencias usando estos algoritmos

 

Tendria que investigar tambien que estrategia se debe usar cuando el "diccionario" de palabras a comparar es muy grande.

Tambien estaria bueno poder tener un parametro que "corte" el algoritmo para directamente descartar strings muy diferentes

 

Creo que la idea es excelente, los retos como dices son las capacidades de limitar cadenas muy grandes y encontrar una eventual puerta de escape.

 

 

Saludos

[poliburro]

Que tema tan interesante. Muchas gracias por compartir con nosotros estos algoritmos.