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

• 作者: 孙钦东 王倩 黄新波
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 多模式匹配 中英文混合 哈希 Trie
• 年，卷（期）: 2008,（3）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 674-686
• 页数: 13页
• 分类号: TP301
• 字数: 10375字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.00674

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄新波	西安工程大学电子信息学院	168	2529	27.0	44.0
2	孙钦东	西安理工大学计算机科学与工程学院	23	830	11.0	23.0
6	王倩	西安理工大学计算机科学与工程学院	35	151	5.0	11.0