:::: MENU ::::

La distanza di Levenshtein, a cosa serve? (2° parte)

Un’implementazione della distanza di Levenshtein può essere fatta in qualsiasi linguaggio. In questo esempio, verrà utilizzato interamente il linguaggio MYSQL.

Per prima cosa, bisogna creare una routine su MySql. Aiutatevi con phpmyadmin per fare ciò. Eseguite direttamente il codice definito in questo listato per creare e aggiungere la funzione levenshtein() al vostro database MySql.

Se volete potete anche aggiungere quest’altra funzione, che restituisce la percentuale di esattezza della parola data.

A questo punto l’unica cosa da fare è quella di creare una query per interrogare il database utilizzando in modo opportuno la funzione definita sopra.

Il risultato sarà questo:

levenshtein2

L’unico vero e grande problema è la lentezza dell’esecuzione dell’algoritmo. Per calcolare la distanza di levenshtein di “romme” su una base dati di 8,092 record, il tempo di esecuzione si aggira attorno ai 12 secondi, e peggiora in maniera esponenziale se la stringa da ricercare è più lunga (es. Castelbuono anzichè Roma). Purtroppo l’algoritmo contiene un doppio WHILE all’interno e questo potrebbe rappresentare un ostacolo, sopratutto in una tabella con migliaia di record.

Tuttavia possiamo cercare di ottimizzare la query MySql in fase di interrogazione in modo da cercare di dimezzare i tempi di ricerca. Una prima ottimizzazione è quella di selezionare solamente i termini più “vicini” a quello che stiamo cercando, confrontando la lunghezza degli stessi. Aggiungo quindi una condizione sulla lunghezza del campo CityName, che deve essere di un carattere più (+1) o meno (-1) lunga rispetto a ciò che sto cercando.

 levenshtein3

Abbiamo un netto miglioramento in termini di prestazioni in fase di esecuzione: 1,17 secondi contro 12 secondi del primo! 

Esistono ovviamente altre ottimizzazioni, infatti ne ho implementata una che mi permette di raggiungere un tempo di esecuzione pari a 0,5740 secondi, ma in questo caso bisogna integrare qualche riga di codice PHP. Vi lancio la sfida di cercarne una! Qui sotto invece trovate un altra ipotesi di ottimizzazione…

Spoiler Inside SelectShow

 


Comments are closed.

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close