字符串匹配是模式匹配中最简单的一个问题，但在文本
处理领域中字符匹配是一个非常重要的主题。它可用于数据
处理、数据压缩、文本编辑、信息检索等多种应用中，大多
数操作系统中软件实现的字符匹配算法是基本组件之一。字
符串匹配技术通常也和其他字符问题有一定关联。在实际应
用中字符串匹配技术不仅适用于计算机科学，在语义学、分
子生物学等领域也具有相当重要的应用，在以模式匹配为特
征的网络安全应用中也发挥了举足轻重的作用。
问题描述
1
定义
1 一个文本标识为…，它的长度为
(text)y=y[0n-1]
，就是待匹配的文本。
ntext
定义
2 用于进行匹配的字符串称为模式，标识
(pattern)
为…，它的长度为。
x=x[0m-1]m
定义
3 定义和中的字符串建立在有限字符集上，该字
12
符集称为字母表，由∑标示，大小为σ。该文是
(alphabet)
建立在这样一个假设上的，即从字母表∑中选取的字符串
对算法的有效性有着严格的影响。
strings
定义
4 对定义中的文本进行扫描检测时需要运用的窗
1
口，它的大小为。
windowm
定义
5 将定义中的窗口和的一端对齐，逐
4windowtext
个比较中和模式中的字符称为尝试。
window(attempt)
定义
6 在中发现一个和完全匹配的字符串或
textPattern
者发现中的字符和不匹配时，将窗口右移，
windowPattern
即。该机制称为滑动窗口机制
shift(sliding window
。当对位置进行尝试时，窗口的位置为…
mechanism)jy[jj+m
。
-1]
定义
7 如果存在两个字和使得，则是字
u vw=uz=zvzw
的边界，是的前缀也是它的后缀。注意在这种情
(border)zw
况下，并且它们是的一个。
|u| = |v|wperiod
定义
8 对于给定的…和…
text y=y[0n-1]pattern x=x[0m-
在中寻找所有出现的过程就是字符串匹配
1],textpattern
[3]
。
字符串匹配问题的解决方法
2
解决方案的评价原则
2.1
算法的复杂性是评价算法优劣的重要依据，算法的复杂
性有时间复杂性和空间复杂性之分。对任意给定的问题，设
计出复杂性尽可能低的算法是设计算法中追求的一个重要目
标；当给定的问题有多种算法时，选择其中复杂性最低者，
是选用算法所遵循的一个重要准则。因此，算法复杂性分析
对算法的设计或选用有着重要的指导意义和实用价值
[3]
。
一般而言，好的字符串匹配算法要有以下特点：
速度快：这是评价一个字符匹配算法最重要的标准。通常要
(1)
求字符匹配能以线性速度执行。目前，网络安全应用中的基于误用
的使用字符串匹配算法进行入侵检测，因此，随着网速的提
NIDS
高，对字符串匹配速度的需求同样也在提高。
有几种时间复杂性的评价指标：预处理时间的复杂性
1)
：
有
些算法在进行字符串匹配前需要对模式特征进行预处理；匹配阶
2)
段的时间复杂性：字符串匹配过程中执行查找操作的时间复杂性，
它通常和文本长度及模式长度相关；最坏情况下的时间复杂性：
3)
对一个进行字符模式匹配时，设法降低各算法的最坏情况下的
text
时间复杂性是目前的研究热点之一；最好情况下的时间复杂性：
4)
对一个进行字符模式匹配时的最好的可能性。
text
内存占用少：执行预处理和模式匹配不仅需要资源还需
(2)CPU
要内存资源，尽管目前内存的容量较以前大得多，但为了提高速
度，人们常利用特殊硬件。通常，特殊硬件中内存访问速度很快但
容量偏小，这时，占用资源少的算法将更具优势。
解决方案的分类
2.2
字符串匹配过程中从左向右滑动，而
,windowswindows
中的的字符和中的字符的匹配顺序在不同的算法
textPattern
基金项目：
国家“”计划基金资助项目；中国科
973(G1999035806)
学院知识创新工程基金资助项目
(KJCX1-09)
作者简介：
李雪莹－，女，博士生，主研领域为网络安全和
(1974)
信息处理；刘宝旭，博士、副研究员；许榕生，博导、研究员
收稿日期：
2003-10-23
：
E-mail
lixy@mail.ihep.ac.cn
字符串匹配技术研究
李雪莹
1,2
，刘宝旭
2
，许榕生
2
军事医学科学院医学情报研究所网络信息中心，北京；中国科学院高能物理研究所计算中心，北京
(1.1008502.100039)
摘要：
简述了字符串匹配算法的研究进展，分析了算法、算法以及、和
Knuth- Morris-PrattBoyer-MooreHorspoolWu & ManberAho-Corasick
针对算法提出的多种改进算法，并基于网络安全应用中开放源码的系统——，对其中几个算法进行评测，指出了实
Boyer-MooreNIDSSnort2.0
际应用中字符串匹配技术的关键点和解决办法，探讨了应用字符串匹配技术的的研发方向。
NIDS
关键词：
模式匹配；字符串匹配；时间复杂性；空间复杂性；网络入侵检测系统
Research of String Matching Techniques
LI Xueying
1,2
，
LIU Baoxu
2
，
XU Rongsheng
2
；
(1.Network Information Center, Institute of Medical Information, Academy of Military Medical Sciences ,Beijing 100850
2.Computing Center, Institute of High Energy Physics, CAS, Beijing 100039)
【】
Abstract
The evolution of string matching algorism research is surveyed in the paper. It analyzes Knuth-Morris-Pratt algorithm, Boyer-Moore
algorithm and the various changes of Boyer-Moore algorithm proposed respectively by Horspool, Wu & Manber and Aho-Corasick . The important
points of string matching techniques in practice are presented by evaluating several algorithms in Snort2.0 which is an open source NIDS system used in
the network security field. And identifies the direction of research and development in NIDS using string matching.
【
Key words
】；；；
Pattern matching String matching Time complexity Space complexity; Network intrusion detection system
第卷 第期
3022
№
Vol.30 22
计 算 机 工 程
Computer Engineering
年月
200411
November 2004
·博士论文·
中图分类号：
TP301.6
文章编号：———
10003428(2004)22 002403
文献标识码：
A
——
24
乌云
- 粉丝: 6
- 资源: 7
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- 2023年中国辣条食品行业创新及消费需求洞察报告.pptx
- 2023年半导体行业20强品牌.pptx
- 2023年全球电力行业评论.pptx
- 2023年全球网络安全现状-劳动力资源和网络运营的全球发展新态势.pptx
- 毕业设计－基于单片机的液体密度检测系统设计.doc
- 家用清扫机器人设计.doc
- 基于VB+数据库SQL的教师信息管理系统设计与实现 计算机专业设计范文模板参考资料.pdf
- 官塘驿林场林防火（资源监管）“空天地人”四位一体监测系统方案.doc
- 基于专利语义表征的技术预见方法及其应用.docx
- 浅谈电子商务的现状及发展趋势学习总结.doc
- 基于单片机的智能仓库温湿度控制系统 (2).pdf
- 基于SSM框架知识产权管理系统 (2).pdf
- 9年终工作总结新年计划PPT模板.pptx
- Hytera海能达CH04L01 说明书.pdf
- 数据中心运维操作标准及流程.pdf
- 报告模板 -成本分析与报告培训之三.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0