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

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?

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

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!

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

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 (ie, the smallest value in the last computed row of the matrix) END IF; RETURN c; END$$ 

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 comstackr 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.

puedes usar esta función


 CREAR FUNCIÓN `levenshtein` (texto s1, texto s2) DEVOLUCIONES int (11)
     DETERMINISTIC
 EMPEZAR 
     DECLARAR s1_len, s2_len, i, j, c, c_temp, costo INT; 
     DECLARAR s1_char CHAR; 
     DECLARAR cv0, cv1 text; 
     SET s1_len = CHAR_LENGTH (s1), s2_len = CHAR_LENGTH (s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
     SI s1 = s2 ENTONCES 
       VOLVER 0; 
     ELSEIF s1_len = 0 THEN 
       RETORNO s2_len; 
     ELSEIF s2_len = 0 THEN 
       RETORNO s1_len; 
     MÁS 
       MIENTRAS j < = s2_len DO 
         SET cv1 = CONCAT (cv1, UNHEX (HEX (j))), j = j + 1; 
       TERMINAR MIENTRAS; 
       MIENTRAS que <= s1_len DO 
         SET s1_char = SUBSTRING (s1, i, 1), c = i, cv0 = UNHEX (HEX (i)), j = 1; 
         MIENTRAS j <= s2_len DO 
           SET c = c + 1; 
           IF s1_char = SUBSTRING (s2, j, 1) ENTONCES  
             SET costo = 0;  ELSE SET cost = 1; 
           TERMINARA SI; 
           SET c_temp = CONV (HEX (SUBSTRING (cv1, j, 1)), 16, 10) + costo; 
           IF c> c_temp ENTONCES SET c = c_temp;  TERMINARA SI; 
             SET c_temp = CONV (HEX (SUBSTRING (cv1, j + 1, 1)), 16, 10) + 1; 
             IF c> c_temp ENTONCES  
               SET c = c_temp;  
             TERMINARA SI; 
             SET cv0 = CONCAT (cv0, UNHEX (HEX (c))), j = j + 1; 
         TERMINAR MIENTRAS; 
         SET cv1 = cv0, i = i + 1; 
       TERMINAR MIENTRAS; 
     TERMINARA SI; 
     RETORNO c; 
   FIN

y para obtenerlo como XX% use esta función


 CREAR FUNCIÓN `levenshtein_ratio` (texto s1, texto s2) DEVOLUCIONES int (11)
     DETERMINISTIC
 EMPEZAR 
     DECLARAR s1_len, s2_len, max_len INT; 
     SET s1_len = LENGTH (s1), s2_len = LENGTH (s2); 
     SI s1_len> s2_len ENTONCES  
       SET max_len = s1_len;  
     MÁS  
       SET max_len = s2_len;  
     TERMINARA SI; 
     RONDA DE REGRESO ((1 - LEVENSHTEIN (s1, s2) / max_len) * 100); 
   FIN

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.

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 objective. 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.

Según la respuesta de Chella y el artículo de 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 ;