Archivi tag: search

Ricerca invertita in MySQL: controlla se le parole chiave nel campo corrispondono ad un testo

Di solito, “cercare in un database” significa cercare quelle righe che contengono un “documento” in un campo, che corrisponde a delle parole chiave (di solito usando la funzione MATCH AGAINST); mettiamo invece che vogliate fare il contrario, cioè avete una tabella con delle righe che contengono un campo in cui avete memorizzato delle parole chiave, e volete selezionare solo quelle righe in cui le parole chiave corrispondono ad un testo o un particolare documento. Questa è quella che io chiamo una ricerca invertita.

Uno scenario reale: avete un sito di offerte di lavoro, ed i candidati cercano annunci di loro gradimento, ma non ne trovano nessuno, oppure ce ne sono troppo pochi e non interessanti. O continuano a collegarsi al sito ripetendo la ricerca periodicamente (ad esempio con le parole chiave “veterinar* gatt*“, perché vogliono prendersi cura degli animali, e hanno un debole per i gatti in praticolare), o si iscrivono al feed RSS di quella ricerca (se ne avete uno)… oppure “salvano” la ricerca e aspettano che sia il sito ad inviare loro una mail non appena compare un nuovo annuncio pertinente, ed è qui che torna utile questo articolo.

Salvare le parole chiave per ogni utente in una tabella MySQL è semplice, ma quanto è semplice verificare se un annuncio appena inserito corrisponde alle parole chiave? In PHP, costruireste un array delle parole chiave, e per ogni elemento richiamereste strpos() per verificare che siano tutte contenute nel testo.

In MySQL la funzione INSTR() è l’equivalente di strpos() in PHP, ma non potete salvare degli array in un campo (intendo array veri e propri, non serializzati), e d’altra parte salvare tante righe quante sono le parole chiave scelte da ogni utente è sconveniente, siccome la normalizzazione non è necessaria: un “insieme di parole chiave” è quasi sempre unico per ogni utente che si iscrive ad una ricerca, per cui ha senso salvarlo in un campo testuale nella forma di “parola1,parola2,parola3,…“; anche qui, in PHP useremmo explode(“,”,$parole) per ottenere un array, ma in MySQL non esiste nessuna funzione simile, per cui è necessario crearne una.

Idealmente, avreste bisogno di una funzione a cui passare il testo/documento in vostro possesso (la somma di titolo e corpo dell’offerta di lavoro, in questo caso), la stringa nella forma “parola1,…,parolaN“, e un parametro per indicare che il delimitatore (“colla” nel caso di implode/explode) è una virgola, quindi:

funzione(document, keywords, delimiter)

Questa funzione dovrebbe restituire un valore intero positivo se tutte le parole chiave sono presenti nel testo, oppure 0 in caso contrario.

La funzione che ho messo assieme incollando informazioni prese un po’ dovunque è:

DELIMITER ;;

DROP FUNCTION IF EXISTS `matchkwdarray`;;
CREATE FUNCTION `matchkwdarray`(`str` text, `arr` text, `delimit` tinytext) RETURNS char(1) CHARSET utf8
 DETERMINISTIC
BEGIN
 DECLARE i INT DEFAULT 1;
 DECLARE matches INT DEFAULT 1;
 DECLARE token TINYTEXT;
 label:WHILE(matches>0) DO
 SET token=replace(substring(substring_index(arr, delimit, i), length(substring_index(arr, delimit, i - 1)) + 1), delimit, '');
 IF token='' THEN LEAVE label; END IF;

 SET matches=INSTR(str, token);
 SET i=i+1;
 END WHILE;
 RETURN matches;
END;;

DELIMITER ;

Per aggiungere questa funzione al vostro database MySQL, potete collegarvi sia tramite CLI, sia usando una interfaccia web al database, come dovranno fare tutti gli utenti su un hosting condiviso, non avendo accesso alla linea di comando; phpMyAdmin, rigonfio com’è, non supporta comunque routine e funzioni, per cui avete bisogno di un altro DB manager, ed io ho scelto Adminer che svolge il suo lavoro egregiamente, più rapido di phpMyAdmin, e tutto in un piccolissimo singolo file PHP di circa 150kb.

Un esempio d’uso della funzione:

SELECT matchkwdarray('questo è solo un piccolo test molto semplice', 'solo,test', ',')
Restituisce: 2

SELECT matchkwdarray('questo è solo un piccolo test molto semplice', 'casa,albero', ',')
Restituisce: 0

SELECT matchkwdarray('questo è solo un piccolo test molto semplice', 'solo,test,semplice,albero', ',')
Restituisce: 0

Questa funzione è efficiente: appena verifica che una parola chiave non è contenuta nel testo interrompe la procedura e restituisce subito 0; ovviamente, se non cercate una precisione del 100% ma vi accontentate di una corrispondenza inferiore, potete modificarla per verificare comunque tutte le parole chiave, e restituire una percentuale di corrispondenza; potete anche rimuovere l’ultimo carattere dalle singole parole in modo tale che siano ammesse più varianti delle stesse.

La velocità delle funzioni PHP di ricerca su stringhe dipende dall'”ago”

Stavo giocando con alcuni test di prestazioni su dei templates nel mio post precedente, e sono incappato in una scoperta interessante riguardante il modo in cui funziona strpos, e conseguentemente tutte le altre funzioni di tipo “cerca (e sostituisci)” come str_replace, strrpos, stripos, str_ireplace, substr_replace, persino preg_match and preg_replace (ho testato solo str_replace e preg_match, ma suppongo ci siano gli stessi risultati per tutte le altre).

  1. Userò in questo articolo la convenzione di php.net, e chiamerò “ago” la stringa che state cercando, e “pagliaio” la stringa all’interno della quale effettuate la ricerca
  2. Conoscere questi risultati è utile in pratica solo se potete scegliere quali aghi inserire nel pagliaio, per poterli poi cercare successivamente, cioè se state costruendo un template
  3. Ho già cercato per controllare se questa “trovata” era già stata documentata da qualcun altro, ma così non sembra, quindi se mi fossi perso qualcosa evitate di aggredirmi

Mettiamo che stiate creando lo schema per un template, dove inserirete dei tag che dovranno essere sostituiti dai contenuti generati dinamicamente dal vostro sito. Potete chiamarli come volete purché siano stringhe uniche all’interno del modello, quindi per esempio %tag% o {tag} o <!–tag–> o ~tag~ (o come vi pare). Magari pensate che scegliere quale tipo di carattere di delimitazione usare per il nome del tag dipenda solo dai vostri gusti personali, e lo pensavo pure io prima di scoprire questa cosa per puro caso, comunque vi dico subito che se il template consiste in codice HTML ben formato, allora usare per esempio ~tag~ sarà molto più veloce che usare <!–tag–>.

Il principio generale è che cercare un ago che inizia con un carattere “raro” è molto più veloce che cercare un ago che inizia con un carattere molto comune all’interno del pagliaio.

Per esempio, se il vostro pagliaio è un estratto di un ebook, cercare “%ciao” (se presente) sarà molto più rapido che cercare “ciao”.  La giustificazione di questo? Evidentemente la funzione in C che cerca la stringa, inizia col cercare il primo carattere, e una volta trovato vede se quello successivo corrisponde, e così via; quindi cercando “ciao” la funzione incapperà in tutte le “c” per controllare se sono seguite da una “i”, se sì poi verificherà se c’è una “a”, ma se ad esempio la parola è “ciarpame”, la funzione verificando l’assenza della “o” finale dovrà scartare il lavoro ed il tempo impiegato, e proseguire. Invece il carattere “%” è raro, se non unico, all’interno di un testo “normale”, quindi la funzione dovrà “fermarsi” molte meno volte a controllare prima di trovare una corrispondenza piena.

Mettiamo questa teoria alla prova, ecco il codice:

$creationstart=strtok(microtime()," ")+strtok(" ");
for ($i=0;$i<100000;$i++) $testpos=strpos($test,"malesuarda");
$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "malesuarda $testpos: ".$creationtime."<br />";

$creationstart=strtok(microtime()," ")+strtok(" ");
for ($i=0;$i<100000;$i++) $testpos=strpos($test,"%malesuada");
$creationend=strtok(microtime()," ")+strtok(" ");
$creationtime=number_format($creationend-$creationstart,4);
echo "%malesuada $testpos: ".$creationtime."<br />";

Spieghiamo un po’ di cose: $test è una stringa relativamente lunga, definita precedentemente nel codice (è composta da un testo lorem ipsum con diversi paragrafi, per 13kb totali), all’interno della quale ho scelto una parola a caso, “malesuada“, che viene ripetuta diverse volte, e ho cambiato due occorrenze di questa parola, entrambe verso la fine della stringa, per renderle uniche, una è diventata malesuarda, cioè ho aggiunto una “r”, e l’altra (più avanti nella stringa) invece è stata modificata in %malesuada, quindi alla fine ho caricato lo script PHP; ho aggiunto un echo per $testpos in modo da confermare che le stringhe fossero state realmente trovate da strpos.

Come atteso, ecco i risultati:

malesuarda 10970: 3.5609
%malesuada 11514: 0.7632

Sostituendo strpos con qualunque altra funzione elencata all’inizio dell’articolo otterrete valori simili.

  This article has been Digiproved