Levenshtein Distance 算法 ASP版

Levenshtein距离，是指将一个字符串改变成另一个字符串，最少需要的操作次数。这里的操作可以是替换一个字符、删除一个字符或者增加一个字符。
这个算法在检查文本相似性的时候很有用，如果两段文本的Levenshtein距离很小的话，那么这两个文本就是相似的。
写这个算法是为了实现YT同人小说页面的一个功能。在用户输入文章标题以后，使用此算法将标题与已存在的所有文章标题进行对比，如果Levenshtein距离小于某一个数的话，就给出一个提示，告诉用户也许已经有人添加过这篇文章了，同时给出这篇文章的地址让用户确认。

比如说两个字串，”abcd”和”abcde”，他们的Levenshtein距离是1，因为”abcd”可以通过在末尾添加一个”e”成为”abcde”。
“abcd”和”abce”的Levenshtein距离也是1，将”abcd”中的”d”替换成”e”就可以变成”abce”。

下面就是算法。

Private Function levenshtein(str1, str2)
	Dim s, t, n, m ,i, j, cost, min
	Dim mx
	'实践证明，做成字符数组会比使用Mid()函数有约10%的性能提升
	ReDim s(Len(str1) + 1)
	ReDim t(Len(str2) + 1)
	For i = 1 To UBound(s)
		s(i) = Mid(str1, i, 1)
	Next
	For i = 1 To UBound(t)
		t(i) = Mid(str2, i, 1)
	Next
	n = Len(str1)
	m = Len(str2)
	If n = 0 Then
		levenshtein = m
		Exit Function
	End If
	If m = 0 Then
		levenshtein = n
		Exit Function
	End If
	ReDim mx(m, n)
	For i = 0 To n
		mx(0, i) = i
	Next
	For i = 0 To m
		mx(i, 0) = i
	Next
	For i = 1 To n
		For j = 1 To m
			If s(i) = t(j) Then
				cost = 0
			Else
				cost = 1
			End If
			min = mx(j - 1, i) + 1
			If min >= mx(j, i - 1) + 1 Then min = mx(j, i - 1) + 1
			If  min >= mx(j - 1, i - 1) + cost Then min = mx(j - 1, i - 1) + cost
			mx(j, i) = min
		Next\t
	Next
	levenshtein = mx(m, n)
End Function