¿Hay alguna forma de buscar en la base de datos SQL palabras similares (significa palabras no idénticas)?

Question

¿Hay alguna manera de buscar en la base de datos MySQL palabras similares (significa palabras no idénticas). Por ejemplo: el usuario busca en la base de datos la palabra "abcd" y hay una palabra "abd" en la base de datos para que el motor de búsqueda o el programa pregunte al usuario "¿Quiere decir [abd]?" Como en la mayoría de los motores de búsqueda en el web? Tenga en cuenta que el término de búsqueda no es una parte de la palabra existente (no se puede utilizar "como")

Answer 1

Echa un vistazo al algoritmo Damerau-Levenshtein distance. Calcula la "distancia" entre dos cadenas y determina cuántos pasos se necesitan para transformar una cadena en otra. Cuanto menos pasos, más cerca están las dos cuerdas.

This El artículo muestra el algoritmo implementado como una función almacenada de MySQL.

El algoritmo es mucho mejor que LIKE o SOUNDEX.

Creo que Google utiliza datos de fuente colectiva en lugar de un algoritmo. es decir, si un usuario escribe abcd, hace clic en el botón Atrás y luego busca inmediatamente abd, luego establece una relación entre los dos términos de búsqueda ya que el usuario no estaba satisfecho con los resultados. Una vez que tiene una comunidad muy grande buscando, aparece el patrón.

Answer 2

depende de lo lejos que están, usted podría mirar en soundex quizá ..

http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

Answer 3

Echa un vistazo Levenshtein_distance

Answer 4

Otra técnica es crear índices en trigrams.

Answer 5

Desde el enlace en la respuesta de Dave Barker está muerto, aquí está el código de an archived version of the website:

CREATE FUNCTION LEVENSHTEIN (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; 
     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(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 

Tomar nota:

• La duración máxima de las cadenas de entrada es de 255 caracteres. Estoy seguro de que podría editar la función para admitir más si es necesario.

• Lo he probado con caracteres internacionales en una columna utf8_bin y parecía funcionar, pero no he probado esa capacidad exhaustivamente.

• Solo lo he probado en MySQL 5.0+. No tengo idea de cómo funcionará en versiones inferiores a eso.

Y como un bono También creé una función auxiliar que devuelve la relación (en porcentaje) de diferente: los mismos caracteres que pueden ser más útil que una distancia de edición recta (idea de aquí).

CREATE FUNCTION LEVENSHTEIN_RATIO (s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    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