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

被引：10

作者：

刘丽霞 ^{[1
,2
]}

张志强 ^{[2
]}

机构：

[1] 闽南理工学院信息管理系

[2] 哈尔滨工程大学计算机科学与技术学院

来源：

计算机应用 | 2013年 / 33卷 / 08期

关键词：

Trie树; 相似字符串; 编辑距离; 活跃节点; 动态规划;

D O I：

暂无

中图分类号：

TP391.3 [检索机];

学科分类号：

081203 ; 0835 ;

摘要：

基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高。针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法。该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降。

引用

页码：2375 / 2378

页数：4