多种字符串相似度算法的比较研究

摘要

对计算字符串相似度的编辑距离算法、最长公共子串算法、贪心字符串匹配算法、RKR-GST等多种算法,根据匹配过程是否有序,对这些算法进行了分类.然后对每种算法的实现原理进行了描述,并给出每个算法的运行步骤,结合一个实际的例子列出了算法运行的结果,最后给出每种算法计算相似度的计算公式和算法时间复杂度及应用领域.由于字符串相似度具有广泛的应用领域,对其中经典的几种算法进行总结对比是一件十分有意义的研究工作.%For Levenshtein Distance, Longest Common Subsequences. Greedy String Tiling, RKR-GST and other algorithms, these algorithms were classified according to whether the matching process is orderly. Then the realization of the principles of each algorithm was described, and given the run of each algorithm step, combined with a practical example shows the results of the algorithm, the formula of similarity and algorithm time complexity and applications of each algorithm were given. As the string similarity with a wide range of applications, which is a very meaningful work to summarize the several classic algorithms.