摘要正则表达式具有是一种具有强大的文本处理能力的工具，它的应用十分广泛。正则表达式主要有两种引擎， 分别为确定的有限自动机 （DFA） 和不确定的有限自动机 （NFA） ，它们都有各的特点。到目前为止，正则表达式匹配引擎优化程度越来越高，它们都是在这两种引擎的基础上进行了改进甚至是混合使用这两种引擎。本文通过构造一个简单的DFA引擎的过程，分析了 DFA与 NFA之间的明显的差异，并且进一步从原理分析了基于猜测—验证的正则表达式匹配算法，之后给出设计的程序。有限状态自动机本身存在着时间与效能之间的制约关系，解决这两者之间的矛盾问题将是正则表达式优化升级的重要途径。31392
毕业论文关键词 正则表达式 有限状态自动机 DFA NFA
Title Studies on the regular expression matching algorithmbased on speculation-validation study scheme
Abstract Regular expression is a tool with powerful text processing power, and itsapplication is very extensive.There are two main engines of regular expression.They are deterministic finite automaton(DFA) and non-deterministic finiteautomaton(NFA),and they all have characteristics.So far, the optimization ofregular expression matching engine is getting higher and higher.They are improvedeven hybrid using the two engines basing on the two engines.With the process ofconstructing a simple DFA engine in this paper,the obvious difference betweenNFA and DFA is analyzed.And the regular expression matching algorithm based onguessing - verification is further analyzed.And then the design of the programis given.Finite state automaton itself has the contradiction between time andeffectiveness.The problem of solving the contradiction between the two is animportant way to optimize the regular expression.
Keywords regular expression finite state automaton DFA NFA
目次
1绪论1
1.1正则表达式的研究意义.1
1.2正则表达式简介.1
1.3本文研究内容介绍.2
2有限状态自动机理论3
2.1有限状态自动机理论.3
2.2正则语言与有限自动机.3
2.3确定的有限状态自动机.4
2.4不确定的有限状态自动机.7
2.5不确定的有限状态自动机的确定化...10
3正则引擎原理..14
3.1正则引擎介绍...14
3.2表达式主导的NFA引擎.14
3.3文本主导的DFA引擎.16
3.4两种引擎的对比...17
4正则表达式匹配引擎算法实现..18
4.1算法构造过程...18
4.2应用程序设计...26
5基于猜测-验证匹配算法的混合引擎研究.33
5.1相关工作...33
5.2混合引擎算法设计...34
结论38
致谢39
参考文献..40
1 绪论1.1 正则表达式的研究意义伴随着网络科学技术的不断提高，网络信息数据量呈现出爆炸性的增长，互联网安全和信息的检索面对着严峻的挑战，网络上总有大量的信息数据需要处理，一方面是要过滤掉危险数据，另一方面又要保证有效数据的完整性，而正则表达式（regular expression）匹配因为有着优秀的扫描能力而成为网络内容分析与系统过滤技术中的关键核心技术。在网络安全的范畴里，开源入侵检测体系 Snort 在 2003 年以前,所有的检测规则都是精确字符串特征,但是在最新发布的规则集中,正则表达式的比例已经超过了 40%[3]。现在许多权威的入侵检测系统已经直接使用正则表达式来描述它的规则集。正则表达式在这其中需要完成的任务就是包括系统入侵检测、信息数据的过滤以及 P2P（Peer-to-Peer）排序和流量的检测等内容。用正则表达式来描述各种攻击特征以及各种协议，和使用提取精确匹配字符串的方法相比交起来，前者为我们提供了一种简便而又颇具效果的方法来解决文本处理的问题，具有更高的准确性和更高的效率。在信息检索的范畴里，信息的检索就是要从大量的按照某一特定的规则排列并存储的数据中提取所需要的特定信息，并且可以对这些数据进行整理分析。这里的正则表达式的作用，就是用某一种特定的模式来匹配文本一个公式，信息检索领域使用正则表达式在文本中标识特定文字,再进一步进行数据的检测、提取、替换和删除等一系列操作，也就是说，它可以检测到输入的字符串并且可以判断该字符串是否为邮箱、网址一类具有规范格式的字符串，并且正则表达式可以从已知字符序列中在要求提取出部分或全部字符串。还可以使用一个正则表达式来描述具有某一特征的字符串， 在输入文本内匹配到以后可以对其进行一系列的替换、删除等操作。正则表达式所提供的搜索模式要比单个字符串搜索、字符串的集合以及扩展的字符串更为复杂，它的重要性越来越突出，应用领域不断拓。到目前为止，已有许多种高效的正则表达式查询算法被研究出来，但是随着信息技术的不断进步，如搜索何充分的利用正则表达式具有极高的挑战性。 基于猜测-验证的正则表达式匹配算法研究:http://www.751com.cn/zidonghua/lunwen_27541.html