Característica "Quiso decir" en una base de datos de diccionario

Question

Tengo una tabla de ~ 300,000 filas; que incluye términos técnicos; consultado usando los índices PHP y MySQL + FULLTEXT. Pero cuando busco un término escrito incorrecto; por ejemplo, "hyperpext"; naturalmente, no dando resultados.

Necesito "compactar" pequeños errores de escritura y obtener el registro más cercano de la base de datos. ¿Cómo puedo lograr tal feaure? Sé (en realidad, aprendí hoy) sobre los algoritmos Levenshtein de distancia, Soundex y Metaphone, pero actualmente no tengo una idea sólida para implementar esto para consultar contra la base de datos.

Saludos cordiales. (Lo siento por mi pobre Inglés, estoy tratando de hacer lo mejor)

Answer 1

Consulte este artículo de cómo se podría implement Levenshtein distance in a MySQL stored function.

Para la posteridad, la sugerencia del autor es hacer esto:

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 

Él también suministra un método de ayuda LEVENSHTEIN_RATIO que evaluará la relación entre diferentes personajes/total, en lugar de una distancia de edición recta. Por ejemplo, si es 60%, entonces tres quintos de los caracteres en la palabra fuente son diferentes de la palabra de destino.

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 

Answer 2

A partir de los comentarios de http://dev.mysql.com/doc/refman/5.0/en/udf-compiling.html

ahora puedo descargar el paquete desde el repositorio MySQL UDF http://empyrean.lib.ndsu.nodak.edu/~nem/mysql/

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

ll 

tar -xzvf dludf.cgi\?ckey\=28 

gcc -shared -o libmysqllevenshtein.so mysqllevenshtein.cc -I/usr/include/mysql/ 

mv libmysqllevenshtein.so /usr/lib 

mysql -uroot -pPASS 

mysql> use DATABASE 

mysql> CREATE FUNCTION levenshtein RETURNS INT SONAME 'libmysqllevenshtein.so'; 

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

Answer 3

por qué no añadir una columna de tabla para almacenar la palabra en su forma alternativa (por ejemplo, Soundex)? De esta forma, si su primer SELECT no encuentra la coincidencia exacta, puede hacer una segunda búsqueda para buscar formularios alternativos coincidentes.

El truco consiste en codificar cada palabra para que las variaciones mal escritas terminen convertidas en la misma forma alternativa.

Answer 4

Sugiero que generate typo variaciones en la entrada de la consulta.

es decir hyperpext> {hyperpeext, hipertexto, etc ...}

Una de ellas está destinada a ser la forma correcta (especialmente para las faltas de ortografía comunes)

La forma de identificar la coincidencia más probable es para hacer una búsqueda de cada uno en un índice que le dice la frecuencia del documento del término. (¿Tiene sentido?)