本站原创本文关于算法及计算机算法及生物信息方面的免费优秀学术论文范文，关于算法类论文范文资料,与字符串匹配算法比较与相关在职毕业论文范文，对不知道怎么写算法论文范文课题研究的大学硕士、本科毕业论文开题报告范文和文献综述及职称论文的作为参考文献资料下载。
摘 要 ：对几种典型字符串匹配算法适用范围和结果进行分析,并确定字符串匹配算法得分的接受阈.
关 键 词 ：字符串；匹配算法；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之间.在阈值之上的字符串,可以近似于认为是同一实体（出错率可以通过抽样统计来判断）,在阈值当中的数据,可以通过人为判断做选择,在阈值之下的数据,进行过滤清洗.当阈值调整,会带来出错率的变化,需要根据数据质量,动态调整阈值,使得错判率达到满意的水品.