一种用于多模式匹配的高效二叉检索树  

An Efficient Binary Searching Tree for Multi-Pattern Matching

作　　者：李东[1] 古宁[1] 林育蓓[2] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510640 [2]华南理工大学南校区计算中心,广东广州510006

出　　处：《计算机工程与科学》2008年第8期69-71,共3页Computer Engineering & Science

摘　　要：网络环境的文本检索往往是同时面向大量用户的,传统的单模式匹配算法无法应付数量巨大的关键字,而一般的基于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.

关 键 词：多模式匹配 二叉检索树 TRIE树 比较位 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]