Esiste un modo per cercare nel database SQL parole simili (parole non identiche)?

Question

Esiste un modo per cercare nel database MySQL parole simili (parole non identiche). Ad esempio: l'utente cerca nel database la parola "abcd" e c'è una parola "abd" nel database in modo che il motore di ricerca o il programma chieda all'utente "Intendi [abd]?" Come nella maggior parte dei motori di ricerca nel web ? Si prega di notare che la parola di ricerca non è una parte della parola esistente (non è possibile utilizzare "come")

Answer 1

Dai un'occhiata all'algoritmo Damerau-Levenshtein distance. Calcola la "distanza" tra due stringhe e determina il numero di passaggi necessari per trasformare una stringa in un'altra. Meno passaggi si avvicinano alle due stringhe.

This articolo mostra l'algoritmo implementato come una funzione memorizzata MySQL.

L'algoritmo è molto meglio di LIKE o SOUNDEX.

Credo che Google utilizzi i dati di crowdsourcing anziché un algoritmo. vale a dire se un utente digita abcd, fa clic sul pulsante Indietro e quindi cerca immediatamente abd quindi stabilisce una relazione tra i due termini di ricerca poiché l'utente non era soddisfatto dei risultati. Una volta eseguita una ricerca di comunità molto ampia, viene visualizzato il modello.

Answer 2

dipende da quanto distanti sono, si potrebbe guardare in soundex forse ..

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

Answer 3

Check out Levenshtein_distance

Answer 4

Un'altra tecnica è creare indici su trigrams.

Answer 5

Dal momento che il link nella risposta di Dave Barker è morto, ecco il codice da 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 

notare:

• Lunghezza massima di stringhe di input è di 255 caratteri. Sono sicuro che potresti modificare la funzione per supportarla di più se necessario.

• L'ho provato con caratteri internazionali su una colonna utf8_bin e sembrava funzionare, ma non ho testato quella funzionalità in modo estensivo.

• L'ho provato solo su MySQL 5.0+. Non ho idea di come funzionerà su versioni inferiori a quella.

E come bonus Ho anche creato una funzione di supporto che restituisce il rapporto (in percentuale) di diverso: stessi personaggi, che può essere più utile di un semplice edit distance rettilineo (idea da qui).

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