基于有序二叉树的多模式匹配算法  

A Multiple Pattern Matching Algorithm Based on Sequential Binary Tree

作　　者：胡佩华[1] 王永成[1] 刘功申[1] 

机构地区：[1]上海交通大学电子信息学院,上海200030

出　　处：《计算机科学》2002年第11期65-68,共4页Computer Science

基　　金：国家自然科学基金(60082003); 科技部中小企业创新基金

摘　　要：By analyzing the multiple pattern matching algorithm based on tree structure, a multiple pattern matching algorithm based on sequential binary tree is proposed in this paper. It is proved by experiment that the algorithm has three features: its constructing process is quick. Its cost of memory is small. At the same time, its searching process is as quickly as the traditional algorithm. The algorithm proposed in this paper is suit for the application whose pattern set is changing dynamically, that is to say, it is suit for the application whose automata must be constructed dynamically. So, the algorithm has a good application prospect.By analyzing the multiple pattern matching algorithm based on tree structure, a multiple pattern matching algorithm based on sequential binary tree is proposed in this paper. It is proved by experiment that the algorithm has three features: its constructing process is quick. Its cost of memory is small. At the same time, its searching process is as quickly as the traditional algorithm. The algorithm proposed in this paper is suit for the application whose pattern set is changing dynamically, that is to say, it is suit for the application whose automata must be constructed dynamically. So, the algorithm has a good application prospect.

关 键 词：数据结构 有序二叉树 多模式匹配算法 树型结构 有限自动机 

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