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.

• C#
• VB.Net
• C
• C++
• PHP

									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