Journal of Computer Applications ›› 2005, Vol. 25 ›› Issue (02): 365-366.DOI: 10.3724/SP.J.1087.2005.0365
• Software technology • Previous Articles Next Articles
TANG Hao, LU Xian-liang
Online:
Published:
唐皓,卢显良
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
摘要: 在基于键树的多模式匹配算法中,键树的物理存储方式为双链树。通过借鉴KMP算法的思想,在键树的基础上增加了将辅助跳转结点变成改进的双链树。改进后的存储方式和匹配算法加快了匹配过程,并且做到了在搜索匹配的过程中不用回溯。
关键词: 双链树, 多模式匹配, 无回溯
CLC Number:
TP301.6
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.
唐皓,卢显良. 基于改进双链树的多模式匹配算法[J]. 计算机应用, 2005, 25(02): 365-366.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.3724/SP.J.1087.2005.0365
http://www.joca.cn/EN/Y2005/V25/I02/365