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

Abstract:

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 spac  e complexity and complicated structures. Aiming at this kind of applications, a simpler and more space-efficient multi-pattern matching algorithm is pro posed in this paper, through some modifications to the node structure of ordinary Trie trees. This algorithm possesses the good performance of multi-pat tern matching, and is more space-efficient and much easier to implement.

Key words: multi-pattern matching, binary searching tree, trie tree, compare bit