基于改进双链树的多模式匹配算法

doi:10.3724/SP.J.1087.2005.0365

计算机应用 ›› 2005, Vol. 25 ›› Issue (02): 365-366.DOI: 10.3724/SP.J.1087.2005.0365

基于改进双链树的多模式匹配算法

唐皓，卢显良

电子科技大学计算机科学与工程学院

发布日期:2005-02-01 出版日期:2005-02-01

Arithmetic for matching multiple patterns based on improved doubly-chained tree

TANG Hao, LU Xian-liang

College of Computer Science and Engineering,University of Electronic Science and Technology of China

Online:2005-02-01 Published:2005-02-01

摘要/Abstract

摘要： 在基于键树的多模式匹配算法中,键树的物理存储方式为双链树。通过借鉴KMP算法的思想,在键树的基础上增加了将辅助跳转结点变成改进的双链树。改进后的存储方式和匹配算法加快了匹配过程,并且做到了在搜索匹配的过程中不用回溯。

关键词: 双链树, 多模式匹配, 无回溯

Abstract: In the arithmetic for matching multiple patterns based on digital search tree,the physical storage mode of digital search tree is doubly-chained tree. Using the idea of KMP arithmetic, digital search tree has been turned into improved doubly-chained tree through added assistant jump-node. The improved storage mode and arithmetic have quickened the speed of matching, and have implemented non-backtracking in process of matching.

Key words: doubly-chained tree, multiple pattern matching, non-backtracking

中图分类号:

TP301.6

唐皓，卢显良. 基于改进双链树的多模式匹配算法[J]. 计算机应用, 2005, 25(02): 365-366.

TANG Hao, LU Xian-liang. Arithmetic for matching multiple patterns based on improved doubly-chained tree[J]. Journal of Computer Applications, 2005, 25(02): 365-366.

[1]	鲁萍王玉英. 多约束分级寻优结合预测计算的智能组卷策略[J]. 计算机应用, 2013, 33(02): 342-345.
[2]	高朝勤陈元琰李梅. 一种面向入侵检测的快速多模式匹配算法[J]. 计算机应用, 2008, 28(1): 82-84.
[3]	蔡晓妍戴冠中杨黎斌. 改进的多模式字符串匹配算法[J]. 计算机应用, 2007, 27(6): 1415-1417.

基于改进双链树的多模式匹配算法

Arithmetic for matching multiple patterns based on improved doubly-chained tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics