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

网络环境的文本检索往往是同时面向大量用户的，传统的单模式匹配算法无法应付数量巨大的关键字，而一般的基于Trie树的多模式匹配算法又存在空间复杂度不良、结构复 杂等问题。针对这种检索大量关键字的应用，本文通过修改Trie树节点的结构得到一种更为简单的多模式匹配算法。该算法既有多模式匹配的性能，又具有高效的空间利用率，并且非常容易实现。

An Efficient Binary Searching Tree for Multi-Pattern Matching

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.