基于Trie树的相似字符串查找算法

摘要

Similar string search algorithms based on Trie tree need to compute active-node set of a node by editing distance threshold.A large number of redundant computation leads to a high time and space complexity.A new algorithm named New-Trie-Stack was proposed,which utilized the symmetrical properties of active-node set and the dynamic programming method to improve the performance.It could avoid the redundancy cost on active-node set computing and storing;moreover,active-node sets were pruned.The experimental results show that New-Trie-Stack algorithm has lower time complexity and space complexity.%基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高.针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法.该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销.实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降.