Levenshtein Distance

Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named after Vladimir Levenshtein, who considered this distance in 1965.



									Private Shared Function MIN3(a As UInteger, b As UInteger, c As UInteger) As UInteger
	Return (If((a) < (b), (If((a) < (c), (a), (c))), (If((b) < (c), (b), (c)))))
End Function

Public Shared Function LevenshteinDistance(s1 As String, s2 As String) As Integer
	Dim s1len As UInteger, s2len As UInteger, x As UInteger, y As UInteger, lastdiag As UInteger, olddiag As UInteger
	s1len = CUInt(s1.Length)
	s2len = CUInt(s2.Length)
	Dim column As UInteger() = New UInteger(s1len) {}

	For y = 1 To s1len
		column(y) = y
	Next

	For x = 1 To s2len
		column(0) = x

		y = 1
		lastdiag = x - 1
		While y <= s1len
			olddiag = column(y)
			column(y) = MIN3(column(y) + 1, column(y - 1) + 1, CUInt(lastdiag + (If(s1(CInt(y - 1)) = s2(CInt(x - 1)), 0, 1))))
			lastdiag = olddiag
			y += 1
		End While
	Next

	Return CInt(column(s1len))
End Function
								


Example

									Dim result As Integer = LevenshteinDistance("kitten", "sitting")
								


Output

									result: 3