| 基于有序二叉树的多模式匹配算法 |
| |
| 引用本文： | 胡佩华,王永成,刘功申.基于有序二叉树的多模式匹配算法[J].计算机科学,2002,29(11):65-68. |
| |
| 作者姓名： | 胡佩华 王永成 刘功申 |
| |
| 作者单位： | 上海交通大学电子信息学院,上海,200030 |
| |
| 基金项目： | 国家自然科学基金(60082003)，科技部中小企业创新基金 |
| |
| 摘 要： | 一、简介在一个文本串中查找用户指定的模式串在信息抽取和文本编辑中有着广泛的应用。当前,有限状态自动机(DFSA)算法是解决多模式匹配问题的常用方法。DFSA算法在匹配前对模式串集合进行预处理,转换成树型有限状态自动机,然后只需对文本串进行一次扫描就可找出所有模式串,其查找时间复杂度是O(n)。后来,在这个算法的基础上又有一些改进,实现了跳跃式查找。基于树型结构的有限自动机特别适
|
| 关 键 词： | 数据结构 有序二叉树 多模式匹配算法 树型结构 有限自动机 |
A Multiple Pattern Matching Algorithm Based on Sequential Binary Tree |
| |
| Abstract: | 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. |
| |
| Keywords: | Multiple pattern matching DFSA Sequential binary tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
