字符串匹配算法比较与分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇字符串匹配算法比较与分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：对几种典型字符串匹配算法适用范围和结果进行分析，并确定字符串匹配算法得分的接受阈。

关键词：字符串；匹配算法；Jaro Winkler Levenshtein；Smith Waterman

字符串匹配算法（String Matching Alogorithm）是两个字符串之间相似度的一种算法，在在数据清洗，分析，，ETL等领域有很重要的用途。在计算机算法实现中，匹配算法的分值介于0到1之间，分值越大说明这两个字符串越相似。本文探讨的字符串匹配算法有如下几种。

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9599 （2013） 02-0000-02

1 Jaro

2 Jaro Winkler

3 Levenshtein

4 Smith Waterman

说明：生物信息学中，对各种生物大分子序列进行分析是一件非常基本的工作。从序列的片段测定，拼接，基因的表达分析，到RNA和蛋白质的结构功能预测，物种亲缘树的构建都需要进行生物分子序列相似性的比较。在遗传物质长期的演化过程中，原本相同的DNA序列由于其中一条序列缺失了几个片断，或增加了几个片断，或某段子序列发生了位置的变化等，从而导致他们发生了不同，这两条序列不一定能进行精确的匹配，但是他们有一定的相似度。我们应该如何判定序列之间的这种相似性？对于这种情况，生物学家提出了一种用来评定序列相似性的方法，称为记分函数的方法。

在寻找序列最优相似比较的算法中有两种算法使用最为广泛：Blast算法和Smith Waterman算法，Blast算法的运行速度要比Smith Waterman算法快，但是Smith Waterman算法要比BLAST算法更为精确。Smith Waterman算法先用迭代方法计算出两个序列的所有可能相似性比较的分值，然后通过动态规划的方法回溯寻找最优相似性比较。

特点：比较适用于一个字符串比另一个字符串少了或多了几个字的情况。以及长字符串。Smith Waterman算法具有明显数据依赖和迭代，适合在数据流模型的并行计算机上进行并行化。

总结：以上诸方法在执行性能方面相差不是太大。应该不会成为用户选择使用的指标。最终用来决定两个字符串是否表达一个意思的阀值一般可以定在0.7到0.95之间。在阈值之上的字符串，可以近似于认为是同一实体（出错率可以通过抽样统计来判断），在阈值当中的数据，可以通过人为判断做选择，在阈值之下的数据，进行过滤清洗。当阈值调整，会带来出错率的变化，需要根据数据质量，动态调整阈值，使得错判率达到满意的水品。

参考文献：

[1]周晓方.数据质量.澳大利亚昆士兰大学，2009.

[2]Jaro-Winkler Distance[EB/OL].http：///wiki/Jaro.

[3]Levenshtein Distance[EB/OL].http：///wiki/Levenshtein_distance

[4]Smith Waterman Algorithm[EB/OL].http：///wiki/Smith_waterman

[5]Simmetrics[EB/OL].http：///projects/simmetrics.