网站原创摘 要 ：对几种典型字符串匹配算法适用范围和结果进行分析,并确定字符串匹配算法得分的接受阈.
关 键 词 ：字符串；匹配算法；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算法具有明显数据依赖和迭代,适合在数据流模型的并行计算机上进行并行化.
| 有关论文范文主题研究: | 关于算法的论文范例 | 大学生适用: | 自考论文、函授论文 |
|---|---|---|---|
| 相关参考文献下载数量: | 89 | 写作解决问题: | 如何怎么撰写 |
| 毕业论文开题报告: | 标准论文格式、论文总结 | 职称论文适用: | 论文发表、职称评中级 |
| 所属大学生专业类别: | 如何怎么撰写 | 论文题目推荐度: | 优质选题 |
总结：以上诸方法在执行性能方面相差不是太大.应该不会成为用户选择使用的指标.最终用来决定两个字符串是否表达一个意思的阀值一般可以定在0.7到0.95之间.在阈值之上的字符串,可以近似于认为是同一实体（出错率可以通过抽样统计来判断）,在阈值当中的数据,可以通过人为判断做选择,在阈值之下的数据,进行过滤清洗.当阈值调整,会带来出错率的变化,需要根据数据质量,动态调整阈值,使得错判率达到满意的水品.