面向中英文混合环境的多模式匹配算法

被引：15

作者：

孙钦东 ^{[1
]}

黄新波 ^{[2
]}

王倩 ^{[1
]}

机构：

[1] 西安理工大学计算机科学与工程学院

[2] 西安工程大学电子信息学院

来源：

软件学报 | 2008年 / 03期

关键词：

多模式匹配; 中英文混合; 哈希; Trie;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.

引用

页码：674 / 686

页数：13

共 6 条

[1] 改进的AC-BM字符串匹配算法 [J].