Trovare pagine simili in Drupal e la distanza di Levenshtein

Navigando sul web mi sono imbattuto in un approccio originale per identificare le pagine che hanno un titolo simile ad una stringa data, come ad esempio il titolo della pagina corrente oppure una sotto stringa elaborata dall'URL, usando la distanza di Levenshtein. Una soluzione apprezzabile a livello accademico/informatico, ma a livello pratico molto meno interessante.

La distanza di Levenshtein è una misura che serve per definire quanto due stringhe sono diverse. Pertanto si può ordinare un vettore di stringhe usando come criterio la distanza che hanno con una stringa data. Sfortunatamente gli algoritmi di questo tipo non sono molto efficienti a meno che non si assumano particolari vincoli o si implementino opportune ottimizzazioni.

Partendo da questa idea è facile scrivere una procedura che scorra tutti i titoli delle pagine di un sito web per estrarre quelle che hanno il titolo più simile al titolo della pagina in cui un visitatore si trova. Più precisamente l'esempio che ho trovato in rete esamina tutti i titoli dei nodi in un sito Drupal e, uno ad uno, ne misura la distanza con una stringa di partenza creando un vettore dei risultati. Tale vettore viene quindi ordinato per poter distinguere le pagine con il titolo più simile alla stringa iniziale.

È chiaro come questo procedimento sia sempre più lento all'aumentare del numero di titoli da confrontare. Ad esempio, in un sito da diecimila pagine, l'algoritmo così descritto è mille volte più lento rispetto ad un sito con solo dieci pagine.

Inoltre questo metodo lavora solamente nei titoli delle pagine senza tenere conto dei loro contenuti. Se lo scopo è quello di identificare delle pagine simili a quella in cui ci si trova, basandosi solo sul titolo si riduce il livello di corrispondenza. Esistono invece delle soluzioni alternative che riescono ad offrire risultati più pertinenti poiché tengono conto di molte più variabili. In Drupal si può usare una ricerca full text nel database, lenta ma precisa, oppure sfruttare software come Apache Solr, che a sua volta sfrutta la distanza di Levenshtein, sviluppati proprio per effettuare ricerche full text ottimizzate.

In ogni caso, se qualcuno fosse interessato a determinare la distanza di Levenshtein tra due stringhe in un sito web sviluppato in Drupal usando PHP, lo può fare molto semplicemente poiché PHP stesso offre una funzione che la calcola:

int levenshtein ( string $str1, string $str2 )

Questa funzione prende in ingresso due stringhe e restituisce il numero minimo di caratteri che bisogna sostituire, inserire o eliminare per trasformare la prima stringa nella seconda, che è appunto la definizione di distanza di Levenshtein.