%0 Journal Article
%T 基于trie树的相似字符串查找算法
%A 刘丽霞
%A 张志强
%J 计算机应用
%D 2013
%X ？基于trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集，已有算法由于存在大量的冗余计算，导致时间复杂度和空间复杂度都比较高。针对这个问题，采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进，并对活跃节点集进行了修剪，提出了new-trie-stack算法。该算法避免了活跃节点的重复计算，以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明new-trie-stack算法在时间复杂度和空间复杂度上都有明显的下降。
%K trie树
%K 相似字符串
%K 编辑距离
%K 活跃节点
%K 动态规划
%U http://www.joca.cn/CN/abstract/abstract16628.shtml