vbs 实现 LD 算法

lxzzr

LD算法（Levenshtein Distance）又成为编辑距离算法（Edit Distance）。他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B，那么操作的过程的次数表示两个字符串的差异。

通俗点讲就是比较两个字符串的相似程度。

http://www.enun.net/?p=2442

1. '======================
   
2. '   A   t   e   s   t
   
3. ' B 0   1   2   3   4
   
4. '
   
5. ' e 1   1   1   2   3
   
6. '
   
7. ' s 2   2   2   1   2
   
8. '
   
9. ' t 3   2   3   2   1
   
10. '======================
    
11. 
    
12. 
    
13. Wscript.Echo GetLevenshteinDistince("test", "est")
    
14. 
    
15. '==============================================================
    
16. ' Copyright (c) enun-net. All rights reserved.
    
17. ' ScriptName: GetStrLD.vbs
    
18. ' Creation Date: 10/11/2013
    
19. ' Last Modified: 10/11/2013
    
20. ' Author: 0x22e09
    
21. ' Homepage: www.enun.net
    
22. ' E-mail: 0x22e09@sina.com
    
23. ' Description: Levenshtein Distance.
    
24. '==============================================================
    
25. 
    
26. Function GetLevenshteinDistince(str1, str2)
    
27.         Dim x, y, A, B, C, K
    
28.         Dim Matrix()
    
29.         ReDim Matrix(Len(str2), Len(str1))
    
30.        
    
31.         '初始化第一行和第一列
    
32.         For x = 0 To UBound(Matrix, 1)
    
33.                 Matrix(x, 0) = x
    
34.         Next
    
35.         For y = 0 To UBound(Matrix, 2)
    
36.                 Matrix(0, y) = y
    
37.         Next
    
38. 
    
39.         '填充矩阵
    
40.         For x = 1 To UBound(Matrix, 1)
    
41.                 For y = 1 To UBound(Matrix, 2)
    
42.                         If (Mid(str1, Matrix(0, y), 1) = Mid(str2, Matrix(x, 0), 1)) Then
    
43.                                 C = Matrix(x -1 ,y - 1)
    
44.                         Else
    
45.                                 C = Matrix(x -1 ,y - 1) + 1
    
46.                         End If
    
47.                        
    
48.                         A = Matrix(x - 1, y) + 1
    
49.                         B = Matrix(x, y - 1) + 1
    
50.                        
    
51.                         If (A =< B and A =< C) Then Matrix(x, y) = A
    
52.                         If (B =< C and B =< A) Then Matrix(x, y) = B
    
53.                         If (C =< A and C =< B) Then Matrix(x, y) = C
    
54.                 Next
    
55.         Next
    
56.        
    
57.         '计算 LD 值
    
58.         If (Len(str1) > Len(str2)) Then
    
59.                 K = Len(str1)
    
60.         Else
    
61.                 K = Len(str2)
    
62.         End If
    
63. 
    
64.         GetLevenshteinDistince = FormatNumber(1 - (Matrix(Len(str2), Len(str1)) / K), 3, True)
    
65. End Function

复制代码