Discusión:Distancia de Levenshtein

distancia de levenshtein para mysql

No se si esta información debería de pasar al principal, así que la pongo en discusión:

Hay una implementación de la distancia de levenshtein para mysql, que la deja como una funcion de usuario (udf). Desde ese momento, se pueden implementar buscadores usando como backend una base de datos en mysql, y las sugerencias se pueden realizar ordenando los resultados por distancia.

No soy el autor de la implementación, simplemente la uso.

http://empyrean.lib.ndsu.nodak.edu/~nem/mysql/udf/dludf.cgi?ckey=28

Aquí se puede encontrar información de como usar UDF en mysql, y en concreto esta:

http://dev.mysql.com/doc/refman/5.0/en/udf-compiling.html

select levenshtein(w1.word,w2.word) as dist from word w1, word w2 where ETC........... order by dist asc limit 0,10;

Rapid2k1 01:54 24 ago 2007 (CEST)

Error en el algoritmo

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
  ...
    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
// si i == 1, i-1==0 str1[0] esta fuera de rango igual para j y str2
 ...