摘要
网络环境的文本检索往往是同时面向大量用户的,传统的单模式匹配算法无法应付数量巨大的关键字,而一般的基于Trie树的多模式匹配算法又存在空间复杂度不良、结构复杂等问题。针对这种检索大量关键字的应用,本文通过修改Trie树节点的结构得到一种更为简单的多模式匹配算法。该算法既有多模式匹配的性能,又具有高效的空间利用率,并且非常容易实现。
Literal information searching on the Internet is often supplied to a large amount of users at the same time. Traditional single-pattern matching algorithms are not capable of dealing with a large amount of pattern strings, while common Trie-based multi-pattern matching algorithms suffer from poor space complexity and complicated structures. Aiming at this kind of applications, a simpler and more space-efficient multi-pattern matching algorithm is proposed in this paper, through some modifications to the node structure of ordinary Trie trees. This algorithm possesses the good performance of multi-pattern matching, and is more space-efficient and much easier to implement.
出处
《计算机工程与科学》
CSCD
2008年第8期69-71,共3页
Computer Engineering & Science
关键词
多模式匹配
二叉检索树
TRIE树
比较位
multi-pattern matching
binary searching tree
trie tree
compare bit
