計算字元串的相似度（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