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

database algorithm

Question

Me gustaría poder buscar 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 analizado el uso de distancia de Levenshtein ¿alguien sabe cómo implementar esto con él?

Answer 1

Estoy preparando una búsqueda basada en Levenshtein o Damerau-Levenshtein (probablemente esta última) para búsquedas múltiples sobre un texto indexado, basado en un documento de Gonzalo Navarro y Ricardo Baeza-yates: texto del enlace

Después de compilar una matriz de sufijos ( ver wikipedia ), si está interesado en una cadena con, como máximo, 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 2

Hay una implementación de UDF mysql de la función Levenshtein Distance

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

Se implementa en C y tiene un mejor rendimiento que la "consulta de distancia Levenshtein de MySQL" mencionada por schnaader

Answer 3

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

Modifiqué la "consulta de distancia de Levenshtein de MySQL" dada anteriormente, en la primera respuesta, para aceptar un "límite" que lo acelerará un poco. Básicamente, si solo te preocupa Levenshtein <= 1, establece 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 más pronto). Por ejemplo, en una búsqueda en 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 4

Para buscar de manera eficiente usando distancia levenshtein, necesita un índice eficiente y especializado, como un 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 5

Según la respuesta de Chella y el article Ryan Ginstrom, una búsqueda difusa podría implementarse de la siguiente manera:

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 ;

Answer 6

Si solo quiere saber si la distancia de levenshtein es como máximo 1, puede usar la siguiente función de 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 de luz, es mucho más rápida.

También puede modificar esta función de modo que devuelva true si la distancia de nivel de umbral es como máximo de 2 o 3, llamándolo auto recursivamente. 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 7

Tuve un caso especializado de búsqueda de distancia k y después de instalar el Dame UDA Damerau-Levenshtein en MySQL encontré 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 agregue columnas a su tabla de destino) con columnas para cada posición de personaje en su campo objetivo. 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 de distancia k utilice el siguiente predicado:

(Columna1 = s [0]) + (Columna2 = s [1]) + (Columna3 = s [2]) + (Columna4 = s [3]) + ...> = m

donde s es su cadena de búsqueda y m 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 tomaba 4.6 segundos en promedio devolvía identificadores 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 8

Una implementación para la distancia damerau-levenshtein se puede encontrar aquí: Algoritmo Damerau-Levenshtein: Levenshtein con transposiciones La mejora sobre la distancia pura de Levenshtein es que se considera el intercambio de caracteres. Lo encontré en los comentarios del enlace de schnaader, ¡gracias!

Answer 9

puedes usar 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 obtenerlo como XX% use 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