基于比特并行的字典搜索的研究与实现

《基于比特并行的字典搜索的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP30单位代码：10183研究生学号：2013532025密级：公开基吉林大学硕士学位论文基于比特并行的字典搜索的研究与实现Theresearchandimplementationofbit-parallelbaseddictionarysearching叶作者姓名：叶成东专业：计算机系统结构研究方向：网络安全与网格计算吉指导教师：张猛教授培养单位：计算机科学与技术学院2016年5月基于比特并行的字典搜索的研究与实现Theresearchandimplementationofbit-parallelbaseddictionarysearching作者姓名：叶成东专业

2、名称：计算机系统结构指导教师：张猛教授学位类别：工学硕士答辩日期：2016年5月24日未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何单位和个人均不得对本论文的全部或部分，内容进行任何形式的复制、、发行、出租修改、改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限）。否则应承担，侵权的法律责任。吉林大学硕±学位论文原创性声明本人郑重声明：所呈交的硕±学位论文，是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做

3、出重要贡献的个人和集体，均已在文中１：＾明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名；－曰期／名。；＞年；月曰Ｊ摘要摘要基于比特并行的字典搜索的研究与实现字符串匹配也称为模式匹配是计算机学科的重要研究方向之一。字符串匹配在文本检索、音乐检索、数据压缩和DNA序列的检测中有着广泛的应用。随着计算机网络的飞速发展，产生了一系列的数据搜索方面的应用需求。其中在网络安全方面的某些问题中，字符串匹配起着关键作用。本课题研究了基于比特并行(bit-parallel)技术的非确定性Aho-Corasick自动机（简称AC自动机）。字典树是一种在模

4、式匹配中有着广泛应用的数据结构；比特并行技术是近年来提出算法设计实现的一种有力的新技术。比特并行技术与经典的字符串匹配算法与数据结构相结合，给模式匹配的研究注入了新的动力。最近Cantone和Faro提出的采用基于比特并行技术的多模式匹配算法的思想便是一种创新。本课题研究了Cantone和Faro提出的构想——使用bit-parallel技术去模拟非确定性有限状态的AC自动机，该自动机是基于字典树(trie)来构建的，从而实现高性能模式匹配。然而他们的工作主要是在理论分析阶段，本次课题的重点研究内容是根据他们的算法思想，设计和实现高性能算法，并用实验进行算法的性能测试。通过实

5、验考察比特并行算法的性能，为后续的研究提出有价值的参考。本文的主要内容包括：首先，简单论述本次课题的研究背景及意义，并简要回顾国内外的研究学者针对字符串匹配领域所做的研究工作，并结合算法实现中遇到的问题，指出当前模式匹配算法的不足之处。对已经存在的各种优秀、经典的，并且在实际中有着良好的使用性能的串匹配算法进行综述，并简要地进行系统化的分类。回顾了计算机领域中重要的比特并行思想，由于本次研究中用到的是非确定性有限自动机，在本文中会介绍如何用比特并行技术去模拟非确定性有限自动机，当然在开展这项工作前会给出一些统一化的概念和定义。其次，对tire树结构进行了介绍，并根据先前的理论

6、铺垫和相关的准备工作，阐述将非确定性AC自动机和比特并行技术相结合的模式匹配算法的理论思想，并推出了针对多模式匹配问题的比特并行算法；随后，阐述了如何在一个字里快速索引“1”的方法。最后，对于先前提到的将比特并行技术与AC自动机相结合的理论思想用C语言编码来实现，并通过实验来同其他优秀的多模式匹配算法作一个性能比较，实验表明了使用比特并行技术的算法在实验中具有一定的优势。关键词：字符串匹配；比特并行；字典树；后缀自动机；AC自动机IAbstractAbstractTheresearchandimplementationofbit-parallelbaseddictionary

7、searchingStringmatchingalsoknownaspatternmatching,anditisoneoftheimportantresearchdirectionsincomputerscience.Stringmatchinghasbeenwidelyusedintextretrieval,musicretrieval,datacompressionandDNAsequencedetection.Withtherapiddevelopmentofcomputernetwork,it