10.11772/j.issn.1001-9081.2013.08.2375
基于Trie树的相似字符串查找算法
基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高.针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法.该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销.实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降.
Trie树、相似字符串、编辑距离、活跃节点、动态规划
33
TP391.3(计算技术、计算机技术)
国家自然科学基金资助项目61272184,61202090,61100007
2013-10-21(万方平台首次上网日期,不代表论文的发表时间)
共4页
2375-2378