本人閱讀了《編程之美》，參閱了其中的——計算字符串的相似度——一節。感覺頗為實用。現將這一文章貼於此處，並將代碼賦予其後。
許多程序會大量使用字符串。對於不同的字符串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個不相同的字符串變得相同，具體的操作方法為：
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
Public Class clsDistance
Private mCharA() As Char
Private mCharB() As Char
Private mCharALen As Integer
Private mCharBLen As Integer
Public Sub New(ByVal StrA As String, ByVal StrB As String)
mCharA = StrA.ToCharArray
mCharB = StrB.ToCharArray
mCharALen = mCharA.Length
mCharBLen = mCharB.Length
End Sub
Public Function CacuDistance() As Integer
Dim i As Integer
If mCharALen = 0 Then Return mCharBLen
If mCharBLen = 0 Then Return mCharALen
Dim j As Integer = Min(mCharALen, mCharBLen) - 1
Dim tP1 As Integer, tP2 As Integer
tP1 = -1
tP2 = -1
For i = 0 To j
If mCharA(i) <> mCharB(i) Then
tP1 = i
Exit For
End If
Next
If tP1 = -1 Then Return Math.Abs(mCharALen - mCharBLen)
For i = 0 To j - tP1
If mCharA(mCharALen - i - 1) <> mCharB(mCharBLen - i - 1) Then
tP2 = i
Exit For
End If
Next
If tP2 = -1 Then Return Math.Abs(mCharALen - mCharBLen)
Dim tA(mCharALen - tP1 - tP2) As Integer
For i = 0 To tA.GetUpperBound(0)
tA(i) = i
Next
Dim tN1 As Integer, tN2 As Integer, tN3 As Integer
For i = 0 To mCharBLen - tP1 - tP2 - 1
tN1 = tA(0)
tN2 = tN1 + 1
For j = 1 To tA.GetUpperBound(0)
If mCharA(mCharALen - tP2 - j) = _ mCharB(mCharBLen - tP2 - i - 1) Then
tN3 = tN1
Else
tN3 = Min(tA(j), tN1, tN2) + 1
End If
tA(j - 1) = tN2
tN2 = tN3
tN1 = tA(j)
Next
tA(tA.GetUpperBound(0)) = tN2
Next
Return tA(tA.GetUpperBound(0))
End Function
Public Function Min(ByVal ParamArray Num() As Integer) As Integer
Dim tN As Integer, i As Integer
If Num.Length = 0 Then Return Nothing
tN = Num(0)
For i = 1 To Num.GetUpperBound(0)
If Num(i) < tN Then tN = Num(i)
Next
Return tN
End Function
End Class
