Implementación de la distancia de Levenshtein para búsqueda mysql/fuzzy?

Question

Me gustaría poder buscar en una tabla de la siguiente manera para smith, ya que tengo todo lo que está dentro de 1 varianza.

datos:

 
O'Brien 
Smithe 
Dolan 
Smuth 
Wong 
Smoth 
Gunther 
Smiht 

He mirado en el uso de la distancia Levenshtein ¿alguien sabe cómo implementar esta con ella?

Answer 1

¿Le sirve de ayuda? MySQL Levenshtein distance query

EDITAR: El antiguo enlace Levenshtein Distance as a MySQL stored function (Google Cache) está roto, gracias a Robert por señalar esto en el comentario.

Edit2: Ambos enlaces se rompen, utilice this one

Answer 2

Con el fin de buscar de manera eficiente utilizando la distancia levenshtein, necesita un, índice especializada eficiente, tales como bk-tree. Desafortunadamente, ningún sistema de base de datos que conozca, incluido MySQL, implementa índices de árbol bk. Esto es más complicado si está buscando una búsqueda de texto completo, en lugar de solo un término por fila. De la mano, no puedo pensar en ninguna forma en la que puedas hacer la indexación de texto completo de una manera que permita la búsqueda en función de la distancia levenshtein.

Answer 3

Una aplicación para la distancia Damerau-levenshtein se puede encontrar aquí: Damerau-Levenshtein algorithm: Levenshtein with transpositions La mejora con respecto a la distancia Levenshtein pura es que el intercambio de caracteres se considera. Lo encontré en los comentarios del enlace de schnaader, ¡gracias!

Answer 4

Yo soy la creación de una búsqueda basada en Levenshtein o Damerau-Levenshtein (probablemente el último) para múltiples búsquedas sobre un texto indexado, basado en un artículo de Gonzalo Navarro y Ricardo Baeza-Yates: link text

Después construyendo una matriz de sufijos (see wikipedia), si está interesado en una cadena con como mucho k no coincide con la cadena de búsqueda, divida la cadena de búsqueda en k + 1 unidad; al menos uno de ellos debe estar intacto. Encuentre las subcadenas por búsqueda binaria sobre la matriz de sufijo, luego aplique la función de distancia al parche alrededor de cada pieza coincidente.

Answer 5

puede utilizar esta función

 

CREATE FUNCTION `levenshtein`(s1 text, s2 text) RETURNS int(11) 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    DECLARE cv0, cv1 text; 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
     SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len DO 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF s1_char = SUBSTRING(s2, j, 1) THEN 
      SET cost = 0; ELSE SET cost = 1; 
      END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
      IF c > c_temp THEN SET c = c_temp; END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
      IF c > c_temp THEN 
       SET c = c_temp; 
      END IF; 
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    RETURN c; 
    END 

y para conseguirlo como el uso XX% esta función

 

CREATE FUNCTION `levenshtein_ratio`(s1 text, s2 text) RETURNS int(11) 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN 
     SET max_len = s1_len; 
    ELSE 
     SET max_len = s2_len; 
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2)/max_len) * 100); 
    END 

Answer 6

que tenía un caso especializado de búsqueda k-distancia y después de instalar el Damerau-Levenshtein UDF en MySQL descubrió que la consulta tardaba demasiado. Se me ocurrió la siguiente solución:

• Tengo un espacio de búsqueda muy restrictivo (cadena de 9 caracteres limitada a valores numéricos).

Cree una nueva tabla (o añada columnas a su tabla de destino) con columnas para cada posición de carácter en su campo de destino. es decir. Mi VARCHAR (9) terminó como 9 columnas TINYINT + 1 columna Id que coincide con mi tabla principal (agregue índices para cada columna). Agregué disparadores para asegurarme de que estas nuevas columnas siempre se actualicen cuando mi tabla principal se actualice.

para realizar una consulta k-distancia utilice el siguiente predicado:

(column1 = s [0]) + (column2 = s [1]) + (Columna3 = s [2]) + (columna4 = s [3]) + ...> = m

donde s es su cadena de búsqueda ym es el número requerido de caracteres coincidentes (o m = 9 - d en mi caso donde d es la distancia máxima que deseo devolver))

Después de las pruebas, descubrí que una consulta de más de 1 millón de filas que tardaba 4.6 segundos en promedio devolvía los ID coincidentes en menos de un segundo. Una segunda consulta para devolver los datos de las filas coincidentes en mi tabla principal de manera similar tomó menos de un segundo. (La combinación de estas dos consultas como subconsulta o unión dio como resultado tiempos de ejecución significativamente más largos y no estoy seguro de por qué).

Aunque esto no es Damerau-Levenshtein (no explica la sustitución), es suficiente para mis propósitos.

Aunque esta solución probablemente no se adapta bien a un espacio de búsqueda más grande (longitud) funcionó muy bien para este caso restrictivo.

Answer 7

Hay una aplicación MySQL UDF de la función Levenshtein Distancia

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

Está implementado en C y tiene mejor rendimiento que la "consulta distancia MySQL Levenshtein" mencionado por schnaader

Answer 8

Si sólo desea saber si la distancia levenshtein es como máximo 1, puede usar la siguiente función MySQL.

CREATE FUNCTION `lv_leq_1` (
`s1` VARCHAR(255) , 
`s2` VARCHAR(255) 
) RETURNS TINYINT(1) DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i INT; 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1; 
    IF s1 = s2 THEN 
     RETURN TRUE; 
    ELSEIF ABS(s1_len - s2_len) > 1 THEN 
     RETURN FALSE; 
    ELSE 
     WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO 
      SET i = i + 1; 
     END WHILE; 
     RETURN SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i) OR SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i+1) OR SUBSTRING(s1,1,s1_len-i+1) = SUBSTRING(s2,1,s2_len-i); 
    END IF; 
END 

Esto es básicamente un solo paso en la descripción recursiva de la distancia levenshtein. La función devuelve 1, si la distancia es como máximo 1, de lo contrario devuelve 0.

Dado que esta función no calcula completamente la distancia del umbral, es mucho más rápida.

También puede modificar esta función de manera que devuelva true si la distancia del umbral de luz es como máximo de 2 o 3, llamándola de forma recursiva. Si MySQL no admite llamadas recursivas, puede copiar versiones ligeramente modificadas de esta función dos veces y llamarlas en su lugar. Pero no debe usar la función recursiva para calcular la distancia exacta del nivel-distancia.

Answer 9

La función dada para levenshtein < = 1 anterior no es correcta - da resultados incorrectos, por ejemplo, "cama" y "oferta".

Modifiqué la "consulta de distancia de MySQL Levenshtein" dada anteriormente, en la primera respuesta, para aceptar un "límite" que lo acelerará un poco. Básicamente, si solo le importa Levenshtein < = 1, establezca el límite en "2" y la función devolverá la distancia exacta de levenshtein si es 0 o 1; o un 2 si la distancia exacta de levenshtein es 2 o mayor.

Este mod lo hace 15% a 50% más rápido: cuanto más larga es la palabra de búsqueda, mayor es la ventaja (porque el algoritmo puede resguardarse antes). Por ejemplo, en una búsqueda contra 200,000 palabras para encontrar todas las coincidencias dentro de la distancia 1 de la palabra "risita", el original tarda 3 minutos 47 segundos en mi computadora portátil, frente a 1:39 para la versión "límite". Por supuesto, estos son demasiado lentos para cualquier uso en tiempo real.

Código:

DELIMITER $$ 
CREATE FUNCTION levenshtein_limit_n(s1 VARCHAR(255), s2 VARCHAR(255), n INT) 
    RETURNS INT 
    DETERMINISTIC 
    BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
     SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF s1_char = SUBSTRING(s2, j, 1) THEN 
      SET cost = 0; ELSE SET cost = 1; 
      END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
      IF c > c_temp THEN SET c = c_temp; END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
      IF c > c_temp THEN 
       SET c = c_temp; 
      END IF; 
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
      IF c < c_min THEN 
       SET c_min = c; 
      END IF; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    IF i <= s1_len THEN -- we didn't finish, limit exceeded  
     SET c = c_min; -- actual distance is >= c_min (i.e., the smallest value in the last computed row of the matrix) 
    END IF; 
    RETURN c; 
    END$$ 

Answer 10

Basado en Chella's answer y de article Ryan Ginstrom, una búsqueda difusa podrían implementarse como tan:

DELIMITER $$ 
CREATE FUNCTION fuzzy_substring(s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    DETERMINISTIC 
BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
      SET cv1 = CONCAT(cv1, UNHEX(HEX(0))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len DO 
      SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
      WHILE j <= s2_len DO 
       SET c = c + 1; 
       IF s1_char = SUBSTRING(s2, j, 1) THEN 
        SET cost = 0; ELSE SET cost = 1; 
       END IF; 
       SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
       IF c > c_temp THEN SET c = c_temp; END IF; 
        SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
       IF c > c_temp THEN 
        SET c = c_temp; 
       END IF; 
       SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
      END WHILE; 
      SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    SET j = 1; 
    WHILE j <= s2_len DO 
     SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10); 
     IF c > c_temp THEN 
      SET c = c_temp; 
     END IF; 
     SET j = j + 1; 
    END WHILE; 
    RETURN c; 
END$$ 
DELIMITER ;