摘要正则表达式近年来广泛应用于网络信息的安全，其检测病毒的能力比传统基于字符串匹配的效果要好，本文主要研究了正则表达式引擎构造的方法，并讨论了两种引擎（非确定性有限自动机 NFA和确定性有限自动机DFA）之间的区别与联系，以及它们之间的相互转换。由于 DFA相比NFA的匹配速度要快，应用越来越广泛，但是随着正则表达式复杂程度的增加，DFA所需要的存储空间呈现指数型增长，为了压缩其所需存储空间，本文考虑簇分割算法，从理论研究了该算法的可行性。在对正则表达式研究的基础上，利用 MFC 平台实现了针对文本数据的正则表达式查找、替换功能的应用程序。该设计的研究可为未来开展针对网络数据流的特殊内容检查奠定基础。32330
毕业论文关键词 正则表达式 NFA DFA 簇分割 MFC
Title Studies on DFA compression algorithmbased on cluster segmentation
Abstract Regular expression is widely used in the security of network information in recentyears.The ability to detect the virus is better than the traditional string basedmatching.This paper mainly studies how the regular expression engine isconstructed.and discuss the distinction and connection between two kinds of engine(undeterministic finite automation NFA and deterministic finite automationDFA )and the conversion of them.Because the matching speed of DFA is faster thanNFA and the application is getting wider and wider However, with the increase ofthe complexity of regular expressions, the storage space DFA required isexponential growth.In order to compress the storage space, the algorithm of clustersegmentation is considered,discuss the Feasibility of the algorithm fromtheory.Based on the study of regular expression,The application of regularexpression search and replace function for text data is realized by using MFC.Theresearch of the design can lay the foundation for the future of the special contentinspection of the network data flow.
Keywords Regular Expression NFA DFA Cluster Segmentation MFC
目次
1引言1
1.1正则表达式的研究背景.1
1.2正则表达式的研究现状.1
1.3正则表达式简介.1
1.4章节安排.2
2正则表达式引擎4
2.1有限状态自动机.4
2.2非确定性有限状态自动机NFA5
2.3确定性有限状态自动机DFA7
2.4NFA与DFA比较.8
2.5本章小结.8
3正则表达式引擎的构造9
3.1NFA引擎的设计9
3.2将NFA转换成DFA.11
3.3本章小结.13
4基于簇分割的DFA压缩算法15
4.1簇.15
4.2簇分割算法.15
4.3本章小结.17
5基于MFC的正则表达式引擎测试软件的设计18
5.1MFC.18
5.2对话框的设计.18
5.3程序的设计.21
5.4本章小结.30
结论32
致谢33
参考文献34
附录35
1 引言
1.1 正则表达式的研究背景近年来，网络大数据成为人们关注的焦点，在庞大的信息传递的过程中，为了确保有害信息不在网络上蔓延，检测网络病毒，保障信息交流的安全[1]，可以利用信息的特征对数据进行检索，但是如今有的病毒善于隐藏，越来越难以被发现，普通的基于字符串的匹配效果越来越差[2]，因此正则表达式这种具有强大的描述能力的工具被广泛应用于网络数据、信息的过滤，文字的处理等领域[3]。
1.2 正则表达式的研究现状正则表达式虽然比传统的基于字符串匹配更方便、精确，但是在实现匹配的算法上却面临着很大的挑战[4]。一般来说，正则表达式匹配的引擎有两个：确定性有限状态自动机 DFA、非确定性有限状态自动机 NFA。NFA和 DFA最大的区别是它们的状态转移函数不同。NFA对同一个字符串可以产生不同的理解方式，但是 DFA只有一种唯一的理解方式。NFA在匹配的过程中因为正则表达式选择的原因可能会回溯，所以 NFA的匹配效率一般低于DFA。但是DFA所需要的存储空间随着正则表达式长度的增加呈指数型增长[5]，因此，大部分改进算法都集中在如何降低 DFA所需要的存储空间[6]。贺炜提出的基于状态约束的大规模正则表达式匹配算法[7]，通过状态之间的约束关系可大幅度减少状态量。徐乾提出的选择性分群算法通过选择性分群大幅度减少了状态机的个数，有效地降低了匹配算法的复杂性[8]。张树壮提出的基于猜测-验证的匹配方法可以在大大减少内存需求的情况下，实现正则表达式的高效匹配[9]。陈曙晖提出的两级存储匹配方案解决了正则表达式匹配中内存需求与检测性能的矛盾[10]。陈曙晖针对深度报文检测中正则表达式模式匹配的状态表爆炸问题，提出基于深度报文检测的 FSM状态表压缩算法[11]。 基于簇分割的DFA压缩算法研究:http://www.751com.cn/zidonghua/lunwen_28847.html