Levenshtein: MySQL + PHP

Question

$word = strtolower($_GET['term']); 

$lev = 0; 

$q = mysql_query("SELECT `term` FROM `words`"); 
while($r = mysql_fetch_assoc($q)) 
{ 
    $r['term'] = strtolower($r['term']); 

    $lev = levenshtein($word, $r['term']); 

    if($lev >= 0 && $lev < 5) 
    { 
     $word = $r['term']; 
    } 
} 

Come posso spostare tutto ciò in una sola query? Non voglio dover interrogare tutti i termini e fare il filtraggio in PHP.

Answer 1

Hai bisogno di un levenshtein function in MySQL e interrogazione come

$word = mysql_real_escape_string($word); 
mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND 4"); 

Answer 2

Questa è una query. Se stai chiedendo se puoi spostare la funzionalità levenshtein in mysql, non puoi.

Ok, bene, ma non è più facile che farlo in PHP.

http://www.artfulsoftware.com/infotree/queries.php?&bw=1280#552

Answer 3

faccio questo in Oracle implementando l'algoritmo in PL/SQL all'interno di una funzione che può essere chiamata.

Answer 4

È possibile effettuare questo codice sembrare un po 'più ordinato, ma @profitphp è giusto, non è possibile farlo in MySQL, senza una libreria Levenstein.

 
$word = strtolower($_GET['term']); 

$q = mysql_uqery("SELECT LOWER(`term`) FROM `words`"); 

while($r = mysql_fetch_assoc($q)) { 

    $lev = levenshtein($word, $r['term']); 

    .... 

} 

Answer 5

Esistono due modi per implementare una funzione Levenshtein in MySQL. Il primo è quello di creare una FUNZIONE MEMORIZZATA che funzioni in modo molto simile a una TRANSAZIONE MEMORIZZATA, tranne che ha ingressi distinti e un'uscita. Questo va bene per i piccoli set di dati, ma un po 'lento su tutto ciò che si avvicina a diverse migliaia di righe.

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; 
-- 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(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// 

Conservare il codice di cui sopra in un file sql e importarlo nel vostro database in questo modo:

source /tmp/mysql_udf.sql 

Il secondo metodo è quello di implementare una funzione definita utente in C/C++ e collegarlo in MySQL come libreria condivisa (file * .so). Questo metodo utilizza anche una FUNZIONE STORED per chiamare la libreria, il che significa che la query effettiva per questo o il primo metodo potrebbe essere identica (a condizione che gli input per entrambe le funzioni siano identici). Potete saperne di più su questo metodo qui: http://samjlevy.com/mysql-levenshtein-and-damerau-levenshtein-udfs/

Con uno di questi metodi, la query sarebbe qualcosa di simile:

SELECT term FROM words WHERE levenshtein(term, 'term') < 5; 

Inoltre, ricorda che il valore di 'soglia' dovrebbe cambiare in relazione al lunghezza della parola originale. È meglio pensarlo in termini di un valore percentuale, cioè metà parola = 50%, metà di "termine" = 2.

Answer 6

Se si dispone di un enorme database, è possibile filtrare prima le parole utilizzando SOUNDEX:

$word = strtolower(mysql_real_escape_string($_GET['term'])); 

$rs = mysql_query("SELECT LOWER(`term`) FROM `words` WHERE SOUNDEX(term) = SOUNDEX(" . $word . ")"); 

while ($row = mysql_fetch_assoc($rs)) { 

    $lev = levenshtein($word, $row['term']); 

    .... 

} 

Se avete abbastanza tempo per giocare con estensione C o una procedura, è possibile ottenere prestazioni migliori, ma filtrando i record su MySQL prima di applicare reale levenshtein renderà le cose più velocemente con un minimo sforzo.

Answer 7

Se si hanno a che fare con set di dati molto grandi, ho trovato che è molto più efficiente gestire le operazioni di Levenshtein e l'ordinamento in PHP che in MySQL. ad es. interrogazione di circa 1000 record:

MySQL (~ 0.0050s) -> PHP Levenshtein (~ 1.300s)

vs.

MySQL Levenshtein (> = 5.000s) -> PHP (~ 0.250s)

Ci sono anche molte altre opzioni per l'ottimizzazione dei motori di ricerca, ma se si desidera utilizzare Levenshtein solo essere consapevoli dei dati avrete essere maneggevole e le latenze che vuoi.

Answer 8

Ti suggerisco di includere il richiamo del levenshtein (link: http://www.artfulsoftware.com/infotree/queries.php#552) nella tua richiesta.

Si dovrebbe usare mysqli_query ($ q) perché mysql_query ($ q) è deprecato e potrebbe essere rimosso in future versioni di PHP!

$word = mysql_real_escape_string($word); 
$query = "SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND 4"; 
mysqli_qery($query);