sabato 29 ottobre 2011

[VB.NET] Distanza di Levenshtein

Descrizione :
Function per il calcolo della Distanza di Levenshtein.

+ Articolo :

La distanza di Levenshtein tra due stringhe A e B è il numero minimo di modifiche elementari che consentono di trasformare la A nella B.

Per modifica elementare si intende :

1. La cancellazione di un carattere
2. La sostituzione di un carattere con un altro
3. L'inserimento di un carattere

Il codice :

    Public Function Levenshtein(ByVal s As String, ByVal t As String) As Integer
 
        Dim i As Integer
        Dim j As Integer
        Dim s_i As String
        Dim t_j As String
        Dim cost As Integer
        Dim n As Integer = s.Length
        Dim m As Integer = t.Length
        If n = 0 Then Return m
        If m = 0 Then Return n
        Dim d(n, m) As Integer
 
        For i = 0 To n
            d(i, 0) = i
        Next
        For j = 0 To m
            d(0, j) = j
        Next
        For i = 1 To n
            s_i = s.Substring(i - 1, 1)
            For j = 1 To m
                t_j = t.Substring(j - 1, 1)
                If s_i = t_j Then
                    cost = 0
                Else
                    cost = 1
                End If
                d(i, j) = System.Math.Min(System.Math.Min((d((i - 1), j) + 1), (d(i, (j - 1)) + 1)), (d((i - 1), (j - 1)) + cost))
            Next
        Next
 
        Return d(n, m)
 
    End Function

+ Fine Articolo.

Un Click su "Mi Piace" è il modo migliore per ringraziare l'autore di questo articolo.



0 commenti:

Posta un commento

Favorites Twitter Facebook Delicious Digg Stumbleupon More

 
Design by Free WordPress Themes Modificato da MarcoGG