TheTruster's Box

  • Increase font size
  • Default font size
  • Decrease font size
Home Programmazione Articoli La Distanza di Levenshtein in Visual Basic 6

La Distanza di Levenshtein in Visual Basic 6

E-mail Stampa PDF

Oggi i motori di ricerca ci abituano sempre di più ad una risposta intelligente e ponderata alle nostre richieste, arrivando fino a "supporre" cosa in realtà stessimo cercando, qualora i risultati forniti dovessero essere scarsi.
E' il caso di Google, ad esempio, che a volte ci risponde con un "Forse cercavi... ". Linguaccia

L'approccio di Google, ovviamente, possiede una tecnologia estremamente sofisticata alla base delle ricerche sui suoi DB, ma con poco sforzo potremmo provare a riprodurre, su piccola scala, qualcosa di analogo per le ricerche sui DB delle nostre applicazioni.

Uno dei possibili algoritmi, facilmente implementabili, è quello che ci permette di calcolare la Distanza di Levenshtein.
La metodologia prende il nome da Vladimir Levenshtein, che per primo la introdusse nel 1965.

In parole povere, questa distanza non è altro che un valore numerico che indica il grado di differenza tra due stringhe, considerando come differenze il numero di sostituzioni, aggiunte, o cancellazioni di caratteri da effettuare su una stringa per arrivare ad ottenerne un'altra.

Prendendo ad esempio le parole SALTO e SBALZO, con l'algoritmo in questione potrò determinare che la prima stringa è "distante" dalla seconda di 2, ovvero che sono necessarie 1 aggiunta + 1 sostituzione per passare da SALTO a SBALZO.
Va da sè che, minore è la Distanza di Levenshtein, più simili sono le parole confrontate.

Il metodo consiste nell'implementazione di una matrice con righe pari al numero di caratteri della prima stringa + 1 e colonne pari ai caratteri della seconda stringa + 1:

Il procedimento prevede che si cominci dalla cella corrispondente ai primi due caratteri, nel nostro caso la S e si proceda verso il basso, una cella alla volta, di colonna in colonna.

Per calcolare il numero da inserire nella cella corrente, si devono considerare 3 valori:

  • Il "costo" determinato dal raffronto dei caratteri corrispondenti in riga e colonna.
    Se sono uguali il costo è 0, altrimenti è 1. Questo valore va sommato al numero in alto a sinistra rispetto alla cella in esame;
  • Il valore della cella a sinistra, addizionato di 1;
  • Il valore della cella a in alto, addizionato di 1.

Il minore tra questi valori dovrà essere scritto nella cella in esame.

Considerando il nostro caso, nella cella (1, 1) - ove entrambe i caratteri sono "S" - il costo è 0, che sommato alla cella in alto sinstra che vale 0, da sempre 0.
Il valore a sinistra è 1 che addizionato di 1 è uguale a 2 e lo stesso dicasi per la cella in alto.
Abbiamo quindi tre valori 0, 2 e 2. Il valore minimo tra questi va inserito nella cella in esame, ovvero 0.

Si procederà così fino alla fine della matrice, dove il valore in basso a destra (cerchiato in arancio) sarà la nostra Distanza di Levenshtein.

Ho realizzato un'implementazione di questo algoritmo in Visual Basic 6. Questo è il codice:

Function Levenshtein(word1 As String, word2 As String) As Integer
 
Dim i As Integer
Dim w1 As Integer
Dim w2 As Integer
Dim costo As Integer
Dim dist() As Variant
Dim matrix() As Integer
 
w1 = Len(word1)
w2 = Len(word2)
 
If UCase(word1) = UCase(word2) Then
    Levenshtein = 0
    Exit Function
End If
 
ReDim matrix(0 To w1, 0 To w2)
 
For i = 0 To w1
    matrix(i, 0) = i
Next i
For i = 0 To w2
    matrix(0, i) = i
Next i
 
For c = 1 To w2
    For r = 1 To w1
        cost = IIf(Mid(UCase(word2), c, 1) = Mid(UCase(word1), r, 1), 0, 1)
        matrix(r, c) = Min(matrix(r, c - 1) + 1, _
                           matrix(r - 1, c) + 1, _
                           matrix(r - 1, c - 1) + cost)
    Next r
Next c
 
Levenshtein = matrix(w1, w2)
 
End Function

Il codice fa uso della funzione Min che determina il minimo tra i valori presenti nell'array passato come argomento.
Ecco il codice anche di questa:

Function Min(ParamArray values()) As Integer
 
Min = 32767
 
For i = LBound(values) To UBound(values)
    If values(i) < Min Then
        Min = values(i)
    End If
Next i
 
End Function

L'utilizzo cui si presta la suddetta funzione è estremamente variegato e senz'altro ci consente di permettere agli utenti delle nostre applicazioni di ricevere dei suggerimenti qualora le ricerche non dessero i risultati sperati: calcolando la distanza delle parole presenti nel nostro DB dalla chiave di ricerca, infatti, potremo presentargli una serie di alternative più o meno distanti dalla chiave, massimizzando così l'efficienza della ricerca e minimizzando la sua frustrazione! Risatona

Spero di aver reso in maniera chiara e comprensibile il concetto, ma qualora vi fosse qualcosa di poco chiaro, che necessiti di ulteriori chiarimenti, contattatemi senza indugio.

 

Sondaggio

Cosa vorresti vedere di più su TheTruster's Box?
 

Utenti on-line

 217 visitatori online

MasterDrive.it



Aggiungi TheTruster's Box ai preferiti!


Scarico di Responsabilità


Tutto il materiale pubblicato è di libero utilizzo.
E' gradito il riferimento al Sito ed all'autore nel codice o nel progetto in cui questo viene utilizzato. NON si garantisce in alcun modo per errori di programmazione o eventuali danni causati da bugs, nè si è responsabili di alcuna problematica inerente all'utilizzo del codice o dei prodotti esposti. Chi usa il materiale esposto nel sito lo fà a proprio rischio assumendosene la completa responsabilità.

Questo sito utilizza cookie, anche di terze parti, per personalizzare i contenuti. Per informazioni o negare il consenso a tutti o ad alcuni cookie leggi la nostra Cookie Policy. Chiudendo questo banner, scorrendo questa pagina o cliccando su qualunque suo elemento acconsenti all'uso dei cookie. Per informazioni sui Cookies che usiamo e su come cancellarli, guarda la nostra Cookie Policy.

Accetto esplicitamente i Cookies di questo sito.

EU Cookie Directive Module Information