大佬教程收集整理的这篇文章主要介绍了计算字符串的相似度(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,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符,然后计算A[2,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前,然后计算A[1,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前,然后计算A[2,lenB]的距离。
在这个题目中,我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以,可以将上面6个操作合并为:
1.一步操作之后,再将A[2,lenB]变成相同字符串。
2.一步操作之后,再将A[1,lenB]变成相同字符串。
3.一步操作之后,再将A[2,lenB]变成相同字符串。
这样,很快就可以完成一个递归程序。
以上摘自原书,有兴趣的读者可以参看原书。下面的代码是根据这个思想实现的。用的是VB2005
Public Class clsCalculateStringDistance
Implements IDistance
Private mIsSame As Boolean
Private mDic As Dictionary(Of String,Integer)
Private Function CalculateStringDistance( _
ByVal StartA As Integer,_
ByVal StartB As Integer) As Integer
Dim tD As Integer
If mDic.ContainsKey(StartA & "," & StartB) = True Then _
@H_674_192@Return mDic(StartA & "," & StartB) @H_674_192@If StartA > mStringA.Length Then
@H_674_192@If StartB > mStringB.Length ThenReturn 0
@H_674_192@ElseReturn mStringB.Length - StartB + 1
@H_674_192@End IfEnd If
If StartB > mStringB.Length Then
@H_674_192@If StartA > mStringA.Length ThenReturn 0
@H_674_192@ElseReturn mStringA.Length - StartA + 1
@H_674_192@End IfEnd If
If mStringA.Chars(StartA - 1) = mStringB.Chars(StartB - 1) Then
@H_674_192@tD = CalculateStringDistance(StartA + 1,StartB + 1) @H_674_192@If mIsSame = false Then mDic.Add(StartA & "," & StartB,tD) @H_674_192@Return tDElse
@H_674_192@@H_212_1@mIsSame = false @H_674_192@Dim t1 As Integer,t2 As Integer,t3 As Integer @H_674_192@t1 = CalculateStringDistance(StartA,StartB + 1) @H_674_192@t2 = CalculateStringDistance(StartA + 1,StartB) @H_674_192@t3 = CalculateStringDistance(StartA + 1,StartB + 1) @H_674_192@tD = Min(t1,t2,t3) + 1 @H_674_192@@H_212_1@mDic.Add(StartA & ",tD) @H_674_192@Return tDEnd If
End Function
Private Function Min(ByVal ParamArray M() As Integer) As Integer
J = M(0)
For i = 1 To m.GetUpperBound(0)
@H_674_192@If M(i) < J Then J = M(i)Next
Return J
End Function
Public Function CalculateStringDistance() As IntegerImplements
@H_674_192@IDistance.CalculateStringDistanceIf mStringA.Length = 0 Then Return mStringB.Length
If mStringB.Length = 0 Then Return mStringA.Length
@H_212_1@mDic = New Dictionary(Of String,Integer)
@H_212_1@mIsSame = True
Return CalculateStringDistance(1,1)
End Function
Public ReadOnly Property DicCount() As IntegerImplements
@H_674_192@IDistance.DicCountGet
@H_674_192@Return mDic.CountEnd Get
End Property
Public Sub SetString(ByVal S1 As String,ByVal S2 As String) Implements
@H_674_192@IDistance.SetStringEnd Sub
End Class
本系列的后一篇文章“计算字符串的相似度(VB2005)——思索之二”
以上是大佬教程为你收集整理的计算字符串的相似度(VB2005)——思索之一全部内容,希望文章能够帮你解决计算字符串的相似度(VB2005)——思索之一所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。