˵

经曲的字符串匹配模糊搜索算法 思想不是本人的

1.设计需求所要求的是一个简单的函数：给定两个普通的C风格字符串（以NULL）结尾，该函数就会返回一个介于0和1之间的浮点数，表示这两个字符串的匹配度（或说两个字体串之间的相似度）。
2.现有的一些解决方案
实际上我们真正寻找的是Levenshtein距离算法（这个公式是由Vladimir Levenshtein在1965年发现的），也就是算出从一个字符串转换成另一个字符串所需要的编辑次数，这个公式可以描述出两个字符串的相似度。对于我们上面所描述的实现的实现接口，单有这个公式是不够的，因为我们需要一个相似度指数，以便可以建立一个有意义的入口。
3.我自己定制的字串匹配方案
首先，我们判断出两个字串中比较长的那一个，并以它的长度作为长度计算的基准值，每个参入匹配的字母表示着一个用1除以这个长度基准值所得到的值。对于大小写的错误，我们可以向匹配中增加正常值的一个百分比90%。对于位置不正确的文本，我们只会计算它一半的值。这是因为，为了有利于前一个字集匹配，我们放弃上一个最新发现的匹配，这看上去是一个公平的估值计算，可以允许合理数量的位置错误字体。最后，缺少的、或者多出来的字体会使精度的值成比例下降。
while中主要部分循环说明：利用一个外部循环和一个内部循环，将左实验指针（lp）和右实验指针（rp）向前推进，在所有新的匹配组合中进行循环遍历，来完成上述工作。在左/右两个字符串中，我们应该推进几步才能得到一对匹配的字符？这两个值记录在lefCount和rightCount中。根据这两个值，我们可以算出一个匹配度值。将这两个值相加，我们就得到最后的分值(totalScore)。这是为了防止出现最坏匹配的情况。在这种情况下，一个无关的字母与另一个字串中接近尾部的某个字符相匹配，我们将这样的匹配标识为低匹配的匹配，并选择其他更为合理的，在两个字符串中位置更靠前的匹配。