"Volevi dire" funzione su un database di dizionario

Question

Ho una tabella di ~ 300.000 righe; che include termini tecnici; interrogato usando gli indici PHP e MySQL + FULLTEXT. Ma quando cerco un termine dattiloscritto sbagliato; per esempio "hyperpext"; naturalmente senza dare risultati.

Ho bisogno di "compattare" piccoli errori di scrittura e ottenere il record più vicino dal database. Come posso realizzare una tal cosa? So (in realtà, appreso oggi) sugli algoritmi di distanza di Levenshtein, Soundex e Metaphone, ma al momento non ho una solida idea per implementarlo in query su database.

Cordiali saluti. (Mi dispiace per il mio povero inglese, sto cercando di fare del mio meglio)

Answer 1

consulta questo articolo per come si potrebbe implement Levenshtein distance in a MySQL stored function.

Ai posteri, il suggerimento dell'autore è quello di fare questo:

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 

Egli fornisce anche un metodo di supporto LEVENSHTEIN_RATIO che valuterà il rapporto tra diversi personaggi/totale, piuttosto che una modifica distanza in linea retta. Ad esempio, se è del 60%, i tre quinti dei caratteri nella parola sorgente sono diversi dalla parola di destinazione.

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

Dai commenti di http://dev.mysql.com/doc/refman/5.0/en/udf-compiling.html

ora ho scaricare il pacchetto dal repository 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

perché non aggiungere una colonna della tabella per la memorizzazione della parola in la sua forma alternativa (es. Soundex)? in questo modo, se la tua prima SELECT non trova la corrispondenza esatta, puoi eseguire una seconda ricerca per cercare i moduli alternativi corrispondenti.

Il trucco è codificare ogni parola in modo che le variazioni di ortografia vengano convertite nella stessa forma alternativa.

Answer 4

Le suggerisco variazioni generate typo sull'input della query.

cioè hyperpext> {hyperpeext, ipertestuali, ecc ...}

Uno di questi è destinato ad essere l'ortografia corretta (soprattutto per i comuni errori di battitura)

Il modo in cui si identifica il più probabile è partita fare una ricerca per ciascuno su un indice che ti dice la frequenza del documento del termine. (ha senso?)