摘要
针对网络信息审计系统的需要,提出一种新颖的基于Episode距离的快速多模式相似串匹配算法.该算法把模式串集合转换为多个有限自动机,然后利用模式串集合建立一个状态驱动器.依次用待匹配串的字符驱动状态驱动器,由状态驱动器驱动各个有限自动机,实现了中英文混合的允许插入错误的相似多模式匹配.该算法不需要匹配每个字符,能充分利用匹配过程中本次匹配不成功的信息并结合改进的文本窗机制,跳过尽可能多的字符;能够控制每个模式串的允许错误上限;匹配速度与允许插入的错误字符数k无关.该算法在信息审计、数据库、信息检索等领域有着广阔的应用前景.
This paper shows a simple, efficient, and practical algorithm for locating all occurrences of a finite number of
出处
《软件学报》
EI
CSCD
北大核心
2004年第7期1074-1080,共7页
Journal of Software
基金
国家信息产业部计算机网络与信息安全基金~~
关键词
信息审计
允许错误的匹配
多模式相似匹配
有限自动机
in a char/Chinese character string allowing k chars inserting errors. The algorithm consists of constructing multiple finite state single-pattern matching machines from keywords and a state-driver applied to drive all finite state single-patter