确定状态自动机空间占用的优化研究

发布时间：2017-08-07 19:40

  本文关键词：确定状态自动机空间占用的优化研究

  更多相关文章： 确定状态自动机 完美哈希函数 存储空间 压缩算法

【摘要】：随着互联网时代的到来，计算机网络已经成为人们不可或缺的重要部分但网络中的安全问题也日趋严重；网络攻击，网络欺骗，以及盗用用户账号密码的手段层出不穷通常情况下，所有的恶意代码都被封装到网络数据包当中这样计算机安全领域的重要问题就变成了如何高效的找出数据包中恶意代码所以基于模糊查询的正则表达式应运而生，它通过自身的句法规则来描述特定字符串来提供数据集合中的查找结果，并且在模式匹配领域占据了极其重要地位，经久不衰在基于文本的编辑器和搜索工具中，正则表达式的出现也使得数据处理变得更方便更高效正则表达式的匹配过程是由确定状态自动机ξDFAο和非确定状态自动机ξNFAο来完成的经典的正则表达式自动机是Thompson自动机和Glushkov自动机，，但是经典自动机的状态转移需要占用大量的存储空间，并且状态转移的过程十分复杂，导致最终得到的实验结果在时间复杂度和空间复杂度方面并不尽如人意近年来提出的基于比特并行的模式匹配方法使得模式匹配可以通过比特向量和位操作来完成，大大的降低了模式匹配占用的存储空间利用比特并行方法实现的自动机可以进一步提高匹配速度并且减少存储空间考虑到构造Glushkov自动机的时间较快，本文以基于比特并行的Glushkov自动机作为研究对象，目的是缩小自动机占用的存储空间状态转移表T表是Glushkov自动机的重要组成部分，也是占用存储空间最多的数据表本文在原有的比特并行算法的基础上，提出了压缩T表空间两种方法：一种是通过构造移位函数和数组对T表的所有表项进行移位和压缩处理，来减少T表所占用的存储空间这种方法实现简单，但在处理表项时还是会造成存储空间的浪费另一种是使用MPHFξ最小完美哈希函数ο对T表中的表项进行优化，最小完美哈希函数是基于无向图实现的，本文中使用了比其他的完美哈希算法更快的RAM算法通过实验发现T表的存储空间要比实际占用的存储空间缩小2到3倍左右，而且完美哈希函数的方法占据的存储空间更小虽然完美哈希函数提供了完美的集合一对一映射方法，但实现的过程相对复杂当处理海量字符串生成对应的哈希值问题时，我们的目标是使用尽可能简单的算法，花费更短的处理时间，同时希望生成的哈希值是尽可能无重复的随着计算机图形处理器的更新换代，基于GPU并行计算使得大规模数据的高速处理变得游刃有余，同时NVDIA公司提供的CUDA平台也降低了并行计算编程的复杂性本文选取了八种高效哈希算法，在CUDA平台上实现了这八种算法通过算法在CPU和GPU的执行时间分析，我们发现基于多线程的GPU编程模型可以加速这八种哈希算法的执行过程，同时GPU的高计算能力也极大程度上缩短了这八种哈希算法的处理时间
【关键词】：确定状态自动机 完美哈希函数 存储空间 压缩算法
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.08
【目录】：

• 摘要4-6
• Abstract6-11
• 第1章 绪论11-12
• 1.1 引言11
• 1.2 两种构造方法比较11
• 1.3 本文工作11
• 1.4 组织结构11-12
• 第2章 研究背景12-22
• 2.1 正则表达式12-14
• 2.1.1 使用正则表达式描述模式集合12-13
• 2.1.2 正则表达式的定义13-14
• 2.2 正则表达式对应的 NFA14-16
• 2.3 构造模拟 NFA16-17
• 2.4 Thompson 自动机17-19
• 2.5 确定有限状态自动机19-20
• 2.6 经典自动机构造时间对比实验20-22
• 第3章 完美哈希函数22-35
• 3.1 最小完美哈希函数22
• 3.2 RAM 算法22-28
• 3.2.1 RAM 算法的基本组成23-24
• 3.2.2 RAM 算法的详细步骤24-28
• 3.2.2.1 RAM 算法过程的说明24-25
• 3.2.2.2 RAM 算法的构造过程25-28
• 3.3 确立哈希函数集合28-35
• 3.3.1 利用无相图的算法29-31
• 3.3.2 算法时间复杂度的分析31-32
• 3.3.3 算法实例32-34
• 3.3.4 RAM 算法实验34-35
• 第4章 Glushkov 自动机存储空间的优化方法35-42
• 4.1 Glushkov 自动机简介35-36
• 4.2 Glushkov 自动机的比特并行方法36-37
• 4.3 压缩Td 表空间方法37-40
• 4.3.1 利用移位和数组实现空间压缩38-39
• 4.3.2 通过二维数组查找数据39
• 4.3.3 使用完美哈希函数优化存储空间39-40
• 4.4 实验结果40-42
• 第5章 GPU 对哈希函数计算的研究42-51
• 5.1 图像处理器简介42-43
• 5.2 CUDA 平台介绍43-44
• 5.3 CUDA 特性44-46
• 5.4 处理字符串的高效哈希算法46-49
• 5.5 CPU 和 GPU 实现哈希算法的对比实验49-51
• 第6章 结论与下一步工作51-52
• 参考文献52-55
• 作者简介及在学期间所取得的科研成果55-56
• 致谢56

【共引文献】

中国期刊全文数据库 前10条

1 吕汇新;一个基于模式匹配入侵检测技术的防信息泄露系统的设计与实现[J];哈尔滨师范大学自然科学学报;2004年03期

2 何畏;汪荣贵;查全民;;一种新的快速移动单模式匹配算法[J];合肥工业大学学报(自然科学版);2010年05期

3 徐克付;齐德昱;郑伟平;钱正平;;一种基于Bloom Filter的正则表达式集合快速搜索算法[J];华南理工大学学报(自然科学版);2009年04期

4 钱立进,吴泽俊,董红斌;基于Horspool算法的模糊匹配[J];计算机工程;2004年01期

5 向永红,李u&,袁勇,林毓材,赵景秀;串的最大匹配算法[J];计算机工程与科学;2003年04期

6 曹京;谭建龙;刘萍;郭莉;;布尔表达式匹配问题研究[J];计算机应用研究;2007年09期

7 刘萍,谭建龙;XML内容筛选中的快速串匹配算法[J];中文信息学报;2005年02期

8 朱小栋;高春昌;王恒山;;引入资源即服务的云计算架构及其应用[J];上海理工大学学报;2013年03期

9 周飞菲;赵雪梅;;基于爬虫的用户迁徙网络的设计与实现[J];科技通报;2013年09期

10 杨子江;聂瑞华;;一种快速的单模式匹配算法[J];华南师范大学学报(自然科学版);2013年05期

中国博士学位论文全文数据库 前10条

1 代六玲;互联网内容监管系统关键技术的研究[D];南京理工大学;2005年

2 王小凤;基于内容的音乐检索关键技术研究[D];西北大学;2008年

3 王洁;基于FPGA的硬件防火墙内容过滤技术研究[D];哈尔滨工业大学;2009年

4 范洪博;快速精确字符串匹配算法研究[D];哈尔滨工程大学;2011年

5 郭磊;面向高速网络管控的多业务识别关键技术研究[D];解放军信息工程大学;2012年

6 刘瑶;社会网络特征分析与社团结构挖掘[D];电子科技大学;2013年

7 李丹;基于流聚类的网络业务识别关键技术研究[D];北京邮电大学;2013年

8 李朋;异构信息网络分析模型及其应用研究[D];重庆大学;2013年

9 程辉;网络用户偏好分析及话题趋势预测方法研究[D];北京交通大学;2013年

10 杨婧;大型工程项目网络化建模及关键节点分析方法研究[D];国防科学技术大学;2012年

本文编号：636396