多种字符串相似度算法的比较研究
牛永洁1
张成2
1.延安大学计算中心 延安7160002.延安大学网络中心 延安716000
摘要：对计算字符串相似度的编辑距离算法、最长公共子串算法、贪心字符串匹配算法、RKR-GST等多种算法,根据匹配过程是否有序,对这些算法进行了分类.然后对每种算法的实现原理进行了描述,并给出每个算法的运行步骤,结合一个实际的例子列出了算法运行的结果,最后给出每种算法计算相似度的计算公式和算法时间复杂度及应用领域.由于字符串相似度具有广泛的应用领域,对其中经典的几种算法进行总结对比是一件十分有意义的研究工作.
关键词：字符串相似度编辑距离最长公共子串贪心字符串匹配RKR-GST
分类号：TP301.6(计算技术、计算机技术)
资助基金：陕西省教育厅自然科学研究项目(11JK1054)
论文发表日期：2012-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：4( 14-17 )
英文信息