计算字符串的相似度（VB2005）

　　本人阅读了《编程之美》，参阅了其中的——计算字符串的相似度——一节。感觉颇为实用。现将这一文章贴于此处，并将代码赋予其后。

　　许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：

　　　　1.修改一个字符（如把“a”替换为“b”）。

　　　　2.增加一个字符（如把“abdd”变为“aebdd”）。

　　　　3.删除一个字符（如把“travelling”变为“traveling”）。

　　比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案，都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，给定任意两个字符串，你是否能写出一个算法来计算出它们的距离？

　　分析与解法

　　不难看出，两个字符串的距离肯定不超过它们的长度之和（我们可以通过删除操作把两个串都转化为空串）。虽然这个结论对结果没有帮助，但至少可以知道，任意两个字符串的距离都是有限的。

　　我们还是应该集中考虑如何才能把这个问题转化成规模较小的同样的问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是相同的，只要计算A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行如下的操作（lenA和lenB分别是A串和B串的长度）：

　　　　1．删除A串的第一个字符，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。

　　　　2．删除B串的第一个字符，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。

　　　　3．修改A串的第一个字符为B串的第一个字符，然后计算A[2,…,lenA]和B[2,…,lenB]的距离。

　　　　4．修改B串的第一个字符为A串的第一个字符，然后计算A[2,…,lenA]和B[2,…,lenB]的距离。

　　　　5．增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。

　　　　6．增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。

　　在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面6个操作合并为：

　　　　1.一步操作之后，再将A[2,…,lenA]和B[1,…,lenB]变成相同字符串。

　　　　2.一步操作之后，再将A[1,…,lenA]和B[2,…,lenB]变成相同字符串。

　　　　3.一步操作之后，再将A[2,…,lenA]和B[2,…,lenB]变成相同字符串。

　　这样，很快就可以完成一个递归程序。

　　在以上面的思想完成代码后，对程序进行了一番测试。第一次找了两个相似的字符串，长度分别为15和17。速度和结果都比较满意。这也印证了算法的正确性。第二次找了两个相似的字符串，长度分别为1500和1507。嗯，直接跳出错误，说是堆栈错误。实际上是由于递归嵌套出了问题。采用递归算法，只是理论上有效，便于理解，实际应用中会出现各种限制。如本例，嵌套约1000层的时候就超过了系统的限制。必须想一个解决之道。仔细观察，可以发现用数学性的语言描述就是

　　F（n，m）=G（F（n，m），F（n+1，m），F（n，m+1））

　　这个可以简化为递推，由于递推可以放在一个函数内，就解决了系统的递归限制。

　　再新代码完成之后，照例还是对代码测试了一番。还是用两个相似的字符串，长度分别为1500和1507，结果能出来，但是效率差了点。在笔者的电脑上用了6秒中左右。仅仅是比较文本，就要6秒钟，比较难以接受，而且从代码看时间复杂度和空间复杂度都是O（n2）。

　　必须得改进！！！

　　在看了代码之后，发现代码运行速度慢可能出现在两个地方。一个是mDic对象，用的是Dictionary对象，在运行中反复读取和存储可能会影响速度，如果改为用数组可能效果会好点。哪位对这个有研究的同道，望不吝赐教。一个是String对象的Chars（Index）的方法。可能在每次执行到这一步时，会先把字符串转化为字符数组再返回一个字符，或者是遍历这个字符串，返回一个字符。对于本例中，大约需要执行1500×1500次，等于反复遍历，时间就浪费了。建议一开始就转化为字符数组，等到比较时就不需要遍历或转化了。

　　按照这两个思路对代码进行了修改，然后测试。效果很满意，本例测试几乎就是一瞬间。

　　程序完成之后，经测试，结果和速度都令人满意，稍显美中不足的是就是空间复杂度还是比较高，为O（S1×S2），当S1和S2都比较大的时候，可能会占用非常多的空间。

　　如何解决这个问题呢？

　　经过对计算过程的分析，我发现作为存储的二维矩阵，在每一个循环中，其实只有一行的数据参与了计算，之前的数据行就不再参与计算了。因此，从这个出发点入手，对代码进行了微调，将二维数组改为一维数组。经测试，结果和速度与之前思索之三中的代码没有差异。但空间复杂度少了很多，为O（S1）。

　　现将代码赋予其后，用的是VB2005

1 Public Class clsDistance

2 Private mCharA() As Char

3 Private mCharB() As Char

4 Private mCharALen As Integer

5 Private mCharBLen As Integer

6

7 Public Sub New(ByVal StrA As String, ByVal StrB As String)

8

9 mCharA = StrA.ToCharArray

10 mCharB = StrB.ToCharArray

11 mCharALen = mCharA.Length

12 mCharBLen = mCharB.Length

13

14 End Sub

15

16 Public Function CacuDistance() As Integer

17 Dim i As Integer

18

19 If mCharALen = 0 Then Return mCharBLen

20 If mCharBLen = 0 Then Return mCharALen

21

22 Dim j As Integer = Min(mCharALen, mCharBLen) - 1

23 Dim tP1 As Integer, tP2 As Integer

24

25 tP1 = -1

26 tP2 = -1

27

28 For i = 0 To j

29 If mCharA(i) <> mCharB(i) Then

30 tP1 = i

31 Exit For

32 End If

33 Next

34

35 If tP1 = -1 Then Return Math.Abs(mCharALen - mCharBLen)

36

37 For i = 0 To j - tP1

38 If mCharA(mCharALen - i - 1) <> mCharB(mCharBLen - i - 1) Then

39 tP2 = i

40 Exit For

41 End If

42 Next

43

44 If tP2 = -1 Then Return Math.Abs(mCharALen - mCharBLen)

45

46 Dim tA(mCharALen - tP1 - tP2) As Integer

47

48 For i = 0 To tA.GetUpperBound(0)

49 tA(i) = i

50 Next

51

52 Dim tN1 As Integer, tN2 As Integer, tN3 As Integer

53

54 For i = 0 To mCharBLen - tP1 - tP2 - 1

55 tN1 = tA(0)

56 tN2 = tN1 + 1

57 For j = 1 To tA.GetUpperBound(0)

58 If mCharA(mCharALen - tP2 - j) = _

　　　　　　　　　　　　　　mCharB(mCharBLen - tP2 - i - 1) Then

59 tN3 = tN1

60 Else

61 tN3 = Min(tA(j), tN1, tN2) + 1

62 End If

63 tA(j - 1) = tN2

64 tN2 = tN3

65 tN1 = tA(j)

66 Next

67 tA(tA.GetUpperBound(0)) = tN2

68 Next

69

70 Return tA(tA.GetUpperBound(0))

71

72 End Function

73

74 Public Function Min(ByVal ParamArray Num() As Integer) As Integer

75 Dim tN As Integer, i As Integer

76 If Num.Length = 0 Then Return Nothing

77 tN = Num(0)

78

79 For i = 1 To Num.GetUpperBound(0)

80 If Num(i) < tN Then tN = Num(i)

81 Next

82

83 Return tN

84 End Function

85

86  End Class