KMP算法的FPGA实现-科技大学本科毕业设计

本 科 毕 业 设 计（2011 届）题 目 KMP 算法的 FPGA 实现学 院 电子信息学院专 业 集成电路设计与集成系统班 级学 号学生姓名指导教师完成日期诚 信 承 诺我谨在此承诺：本人所写的毕业论文KMP 算法的 FPGA 实现均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。承诺人（签名）： 年 月 日杭州电子科技大学本科毕业设计摘 要随着网络技术的迅猛发展，所要检测的数据包越来越多，单纯的依靠软件来检测，越来越显得力不从心。伴随着 FPGA 技术的发展，在硬件上实现模式匹配，来提高网络数据处理速度的需求越来越普遍。把搜索算法固化到 FPGA 里，从而可以大大提高算法的速度，适应科技的迅速发展。本文重点分析了几种典型的模式匹配算法。包括：BF算法、KMP算法、BM算法、BMH算法、AC算法和AC-BM算法。另外文章还介绍了FPGA的的相关基本知识以及硬件描述语言的选择。综合考虑现有的比较成熟的模式匹配算法，并且追踪国外基于FPGA技术来实现模式匹配的研究成果，认为在硬件实现方面，KMP算法效率较高，结构简单，可行性强，而且易于对主串进行多模式的匹配，所以选其作为模式匹配硬件模块的核心算法，通过硬线逻辑来进一步提高串模式匹配的效率。本文KMP算法程序设计部分主要分为三个部分：模式串输入、next函数的计算、字符串的匹配。具体情况会在第四章中介绍。关键词：模式匹配算法；KMP 算法；FPGA电子科技大学本科毕业设计ABSTRACTWith the rapid development of network technology, have to text more and more packets. Thus, simply relying on software to detect becomes more and more inadequate.As the development of FPGA technology, its becomes increasingly popular to realize the pattern matching on hardware to meet the demand for the improvement of the processing speed of network data. Putting the search algorithm to the FPGA, which can greatly improve the speed of the algorithm, is adapt to the quick development of technology.This paper focuses on several typical patterns matching algorithm involving: BF algorithm, KMP algorithm, BM algorithm, BMH algorithm, AC algorithm and the AC-BM algorithm.Besides, this paper will also introduce the basic knowledge related to FPGA as well as the selection of the description language of hardware. Considering the current pattern matching algorithms which are relatively through and the reseaching findings from abroad of using FPGA to achieve pattern mactching, KMP has advantages of efficient arithmetic, simple organization, strong feasibility and easy multi-pattern macthing to primary string in realizing hardware.Thats the reason why choose it to be the core arithmetic of matching pattern and hardware module, which makes further improvement on effiency of pattern maching in string by via hard wire logic.This part of KMP Algorithm Programming is divided into three parts: the pattern string entered, next function calculation, string matching. The circumstances described in the fourth chapter.Key words：Pattern matching algorithm；KMP algorithm；FPGA杭州电子科技大学本科毕业设计目 录第 1 章引言 .11.1 研究背景 .11.2 模式匹配算法的发展与研究现状 .1第 2 章 模式匹配算法 .32.1 模式匹配定义 .32.2 单模式匹配 .32.2.1BF 算法 .32.2.2KMP 算法 .42.2.3BM 算法 .62.2.4BMH 算法 .72.3 多模式匹配 .72.3.1AC 算法 .72.3.2AC-BM 算法 .82.4 影响模式匹配算法的因素 .9第 3 章 FPGA 基本的知识 .113.1FPGA 简介 .113.2FPGA 与 CPLD 的关系以及工作原理 .113.3 硬件语言选择 .12第 4 章 KMP 算法 VerilogHDL 实现 .144.1 模式串输入 .144.2next 函数的计算 .154.3 字符串匹配 .194.4 代码通用性的验证 .22第 5 章结束语 .27致谢 .28附录 .31电子科技大学本科毕业设计- 1 -第1章 引言1.1研究背景 1在网络处理中，模式匹配是指将分组各域进行比特位的匹配处理。一般，模式匹配模块有两个输入，一个是规则的模式表达式，另一个是分组域。它的输出是输入分组的各域是否与输入模式的布尔值匹配。这类模式匹配的实质还是字符串匹配，它的基本运算就是从一个主字符串中找到某个特定模式串出现的位置。目前，串匹配算法一般是以模式串的长度为扫描窗口大小，在窗口中使用不同的扫描策略来进行匹配。假设模式串长为m，主串长为n，串匹配算法根据策略的不同，大致可以分为以下3类 23：从前往后匹配模式前缀的KMP算法，从后往前匹配模式后缀的BM算法及其各种变形，以及从后往前匹配模式前缀的RF算法等等。KMP4算法是从前往后进行扫描，使用自动机记住己匹配模式前缀的正文内容，并依据这些内容来确定是否已经匹配成功。换句话说，就是先对模式串进行预计算，然后再与主串匹配，而且主串不需要回溯，它的时间复杂度比较好，一般是O(m+n)。BM 5算法及其变形是在扫描窗口中从后往前进行扫描，记住已匹配模式后缀的正文内容，并依据这些内容来进行窗口移动，这种方法虽然简单易行，但是时间复杂度比较差，最坏情况下为0(m+n)，所以当串比较长时，效率就会很低。RF算法等是在从后往前进行扫描时，反向使用模式逆串的后缀自动机来匹配模式的前缀，这样可以增大窗口移动的距离，从而获得更好的平均时间复杂度，达到理论最优结果。该方法效率较高，但是比较复杂，硬件实现难度大。综合考虑现有的比较成熟的模式匹配算法，认为在硬件实现方面，KMP算法具有其他算法没有的优势，所以本文选择KMP算法作为研究的主要对象。1.2模式匹配算法的发展与研究现状 14BF算法是最早提出来的模式匹配算法，也是最简单的一个算法。该算法的最坏时间复杂度为O(M*N)。1970年，SACOOK从理论上证明了串匹配问题可以在O(m+n)时间内解决，同一年，Morris和Pratt仿照COOK的证明构造了一个算法，随后，Knuth对这个算法进行了一些改进，在1976年，Knuth提出了第一个在线性时间内解决字符串的模式匹配算法，这个算法被称为KMP算法它的时间复杂度为O(m+n)。1977年，Boyer和Moore提出了另一个与KMP算法截然不同的却同样拥有线性时间复杂度的算法(BM算法)。BM算法在实际的模式匹配中，跳过了很多无用的字电子科技大学本科毕业设计- 2 -符，这种跳跃式的比较方式，使BM算法获得了极高的效率，特别是在大字符集上进行字符串的模式匹配时。在实际的应用中，BM算法比KMP算法更有效率。多模式匹配是另一个研究热点。Aho-Corasie算法(AC算法)是第一个在O(N)上解决这个问题的算法。AC算法可以被看作是KMP算法的更一般化形式。此后，BM算法跳跃的思想也被应用到了多模式匹配上，1979年CommentsWalter提出了一种新的多模式匹配算法，称为CW算法，这个算法将AC算法和BM算法的思想结合起来，获得了更好的执行效率。沿着AC算法这条路线，Crochemore等人将AC算法和DAWG结合，获得了一种新的算法，称为DAWG-MATCH。实验结果表明，该算法比Comments-Walter的算法更有效率。此外，人们还提搬了其它一些多模式匹配算法。1994年，Sun Wu和Manber提出了第一个基于过滤思想的多模式匹配算法。这个算法将过滤思想和BM思想结合起来，在实际的应用中获得了极其高的效率。实验表明，在Sun Sparcl0上，他们的算法可以于10秒内完成在15.8M的文本中搜索10000个模式的工作。在WM算法的基础上，Sun Wu和Manber实现了一个用于模糊匹配的工具agrep和一个文本检索的工具glimpse，在实际的应用中都获得了良好的效率。1996年，Robert Muth和Udi Manber给出了一个快速的多模式模糊匹配算法，这个算法也是基于过滤的思想，同时采用了两级散列的技术，从而获得了极高的执行效率，实验数据表明，该算法能在小于1秒的时间内完成在1M文本中对1000个模式的搜索和模糊匹配的过程。但是不幸的是，该算法只允许模式和文本子串之间存在1个不同点，这样的约束限制了该算法在实际中的应用。1999年，在数据压缩和位操作的思想上，Sun Kim和Yanggon Kim设计出了一个新的多模式匹配算法，实验证明，该算法比Sun Wu和Manber的算法有更好的表现，特别是在小字符集上。目前对模式匹配算法的研究一部分还停留在单模式匹配算法，而对多模式匹配算法的研究主要集中在算法的综述、测试以及对现有算法的一些相应改进上。这些改进的算法虽然也取得一定的成果，但是总体效果都不是很理想，主要是算法速度受限于模式的数目或者实现算法需要的空间消耗的内存太大。字符串的模糊匹配是近年来倍受关注的领域，模糊匹配允许在搜索时搜索出与模式有一些差别的文本中的字符串。在这个领域，有四条主要的技术路线：动态规划算法；自动机算法；过滤算法；位并行算法。由于这不是本文研究的主要内容，故不做详细介绍。电子科技大学本科毕业设计- 3 -第2章 模式匹配算法模式匹配分为单模式匹配和多模式匹配，一次在文本串中查找一个模式串出现的过程，称为单模式匹配。同时查找一个模式串集合中的所有模式串的出现的过程称为多模式匹配。本章主要讨论几种典型的单模式匹配算法和多模式匹配算法。2.1模式匹配定义字符串的模式匹配问题的形式化定义如下：在字符集上，给定一个长度为N的文本字符串T1N，以及一个长度为M的模式 字符串 Pi1M。模式集数量用k来表示，模式集用P=pl，p2，pk来表示。如果对于l=S=N，存在TS+1S+M=Pi1M，则模式Pi在文本T的位置S处出现，即模式与文本匹配。字符串的模式匹配问题就是要寻找P在T中是否出现，以及出现的位置。例如：文本字符串T：Here is a beauterful picture模式字符串P：beauterful该例子显示需要在文本字符串T中搜索模式字符串P：“beauterful“，通过搜索我们发现模式字符串P：“beauterful”出现在文本字符串T中第1l位，那么我们称模式字符串P与文本字符串T匹配成功。2.2单模式匹配2.2.1BF算法BF算法即Brute Force算法的缩写。是蛮力算法的意思，实际上是原理和逻辑最简单的算法这个算法在字符申规模较小的时候，还是能够取得较好的效益。BF算法就是把模式串和文本串的所有窗口逐一进行比较。如果当前字符相同而且模式串结束则匹配成功如果字符相同而模式串未结束就比较下一个字符：如果字符不相同，则窗口向后移动一个字符位置，模式串和新窗口从开始字符重新比较。对于文本字符串TlTkTjTm-k-1Tn模式字符串PlPiPm算法描述：(1)P和T从左端对齐，使得Pl与T1对齐；(2)从左到右匹配P与T的字符，直到出现不匹配的情况或是P已被完全匹配：(3)如果出现不匹配的情况，则将P右移一个字符，重新开始匹配；电子科技大学本科毕业设计- 4 -(4)重复上述过程，直到P被完全匹配，或P移到T的右端。每次模式串和某个窗口比较次数应该是0(m)，而窗口的个数是0（nm)个。因此算法最坏情况的时问复杂度是O(mn)。最坏情况的例子之一是文本串是某一相同字符的字符串而模式串也是这一字符的字符串。这种算法的缺陷是匹配过程中带有回溯，准确地说是当匹配不成功的时候，之前进行的匹配完全变为无效的,所有的比较需要从模式串首字符重新开始。BF算法的优点是不需要预处理。辅助的空间是常量，即只需要几个变量的临时存储区域。模式串和某个窗口内匹配的顺序是任意的，向左或者向右都是可以的。2.2.2KMP算法KMP算法是Knuth等人在BF算法的基础上提出来的。从本质上讲，KMP算法就是出现不匹配情况下带有智能指针初始化的BF算法。为了在不匹配时重新定位指针，KMP算法需要进行预处理算出一个Shift表来。基本思想：KMP算法利用已匹配成功部分的信息，即前缀(模式字符串中存在的相同子串)，可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯。要点是：我们能够通过预先对模式的分析获得知识，即如果在模式的位置l或2匹配失败则移动1个位置，如果在模式的位置3匹配失败则移动2个位置，如果在模式的位置4匹配失败则移动3个位置，以此类推。算法描述 9：当模式匹配执行到比较字符Ti和Pi，其中l=i=n，l=j=m。(1)若Ti=Pj则继续往右作匹配检测，即对Ti+1和Pj+l；进行匹配检测。(2)若TiPj时则分两种情