一种基于有序二叉树的多模式匹配算法(英文)  

Multiple Pattern Matching Algorithm Based on Sequential Binary Tree 1

作　　者：刘功申[1] 李宁[2] 

机构地区：[1]上海交通大学信息安全学院,上海200030 [2]曼彻斯特大学计算机系

出　　处：《小型微型计算机系统》2004年第7期1387-1392,共6页Journal of Chinese Computer Systems

基　　金：信息产业部中长期发展项目 :2 0 0 4-研 1-B-0 3 4

摘　　要：传统的多模式匹配算法是用树型结构的有限自动机实现的 ,它具有很多缺点 .本文提出的多模式匹配算法是基于有序二叉树的多模式匹配算法 .实验证明 ,本文算法不但具有和传统算法相当的查找速度 ,而且构造速度快、内存耗费少 .因此 。By analyzing the traditional multiple pattern matching algorithm based on tree structure, a new algorithm is proposed by substituting sequential binary tree for tree. The algorithm is suitable for the application which requires preprocessing the patterns dynamically. It is proved by experiment that the algorithm has three features: Its construction process is quick. Its cost of memory is small. At the same time, its searching process is as quick as the traditional algorithm.

关 键 词：多模式匹配 DFSA 有序二叉树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]