:::: MENU ::::
Posts tagged with: levenshtein

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

 


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

In teoria dell’informazione e informatica , la distanza di Levenshtein è un’unità di misura per calcolare la differenza tra due stringhe. In altre parole, la distanza di Levenshtein tra due parole A e B è il numero minimo di modifiche di un carattere singolo (inserimento, cancellazione, sostituzione) necessario per modificare la parola A nella parola B. Con edit distance ci si riferisce spesso alla distanza di Levenshtein. La funzione prende il nome dal suo creatore Vladimir Levenshtein, scienziato russo specializzato in teoria dell’informazione, che la scoprì nel 1965.

Esempio

Calcolare la distanza di Levenshtein tra “kitten” e “sitting”. Ovviamente la risposta è 3, poiché sono necessarie tre modifiche per trasformare una parola nell’altra e non c’è altro modo per farlo con meno di tre modifiche:

  1. kitten → sitten (sostituzione di “k” con”s”)
  2. Sitten → Sittin (sostituzione di “e” con “i”)
  3. Sittin → sitting (inserimento di “g” alla fine).

Alcune precisazioni

La distanza di Levenshtein ha alcuni limiti superiori e inferiori. Questi includono:

  • La lunghezza è sempre almeno la differenza della lunghezza delle due stringhe.
  • La lunghezza può essere al massimo uguale alla lunghezza della stringa più lunga.
  • È zero se, e solo se, le stringhe sono uguali.
  • Se le stringhe sono le stesse dimensioni, la distanza di Hamming è un limite superiore alla distanza Levenshtein.
  • La distanza di Levenshtein tra due stringhe non può essere maggiore della somma delle loro distanze di levenshtein da una terza stringa (disuguaglianza triangolare).

Un classico utilizzo

Avete presente quando sbagliate a digitare una parola da cercare con Google? Il motore di ricerca vi consiglia una correzione della parola errata. Guardate l’esempio qui sotto, vi siete mai chiesti come fa Google a correggere le parole errate? La risposta è semplice: Levenshtein!

levenstein

La funzione levenhstein() in PHP

In php è presente da tempo una funzione chiamata appunto levenhstein(), e viene definita di seguito:

dove:

  • str1: prima stringa in ingresso da confrontare
  • str2: seconda stringa in ingresso da confrontare
  • cost_ins: definisce il “costo” dell’operazione di inserimento di un carattere
  • cost_rep: definisce il “costo” dell’operazione di sostituzione di un carattere
  • cost_del: definisce il “costo” dell’operazione di cancellazione di un carattere

continua…


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