多字符串匹配

多字符串匹配（精选6篇）

多字符串匹配 篇1

摘要：本文介绍了常用的SVM多分类器的构造思路,并且分析比较了各种思路的优缺点。针对二叉树决策法中强制分类存在的误判情况,提出了基于字符匹配度的SVM多分类器设计方案。通过实验对比各种多分类器的分类器数量、平均分类次数、训练和判断时间、识别正确率,证明了该构造方案的优越性。

关键词：SVM多分类器,字符识别,二叉树决策

1引言

字符识别(OCR,Optical Character Recognition)的核心在于特征的提取与识别。支持向量机(SVM,Support Vector Machine)作为一种机器学习的二分类器 ,以其识别速度快、识别率高、计算量小等优点,广泛应用于字符识别和其他模式识别领域。实际应用中,待识别的字符样本往往不仅两类。因此如何利用SVM设计多分类器, 并使其保持SVM良好的分类特性, 已成为了一个被广泛研究的课题。

2SVM 多分类器原理及分类

SVM的基本原理是将样本向量映射到多维空间中,通过求解最优超平面将样本划分为两类。距离最优超平面距离最近的样本称为支持向量,最优超平面要确保距离支持向量的距离最远。

利用SVM解决多分类问题, 一种思路是直接进行多类分类,另一种方法是将多类分类转化为多个二分类问题。

2.1 直接构造多分类器

基本思路是将多分类问题转化为统一的凸规划问题,最优化问题求解过程中引入投票机制。

这种方法优点是只需要1个分类器,缺点是算法过于复杂,实际应用效果一般。

2.2 间接构造多分类器

多分类器转化为多个二分类器的方法较多,基本的思路有三种。

2.2.1 one against one

每次从K类中任取两类划分,共需K(K-1)/2个分类器,同时引入投票机制。

该方法优点是训练样本集只需2/K个, 算法简单, 缺点是需要K(K-1)/2个分类器,效果一般。

2.2.2 one against all

K个二分类器依次判断样本是否属于对应的类 ,决策函数认定样本属于指标函数最大的类。

该方法优点是可充分利用全体样本, 不存在盲区, 缺点在于计算量大,效果一般。

2.2.3二叉树决策法

将所有样本分为两个子类, 每个子类再分为两部分,依次循环,当所有子类为单一分类时结束。

该方法的优点是理论上需要K-1个分类器,训练样本在逐步减小,同时有效地避免了投票机制,实际中应用效果较好。

该方法的缺点在于同一决策树不适用不同样本,同一样本可对应多种决策树。算法的好坏主要依赖所选样本和所选决策树。

3基于字符匹配度的 SVM 多分类器

本文针对样本(0…9,A…Z)设计多分类器,评价标准第一是识别的正确率,第二是识别速度(取决于分类器的数量和算法复杂程度)。

3.1 设计思路

分类过程先粗分,再细分。相似字符在粗分类过程中可归为同类,在细分类中再分为单类。将相似的字符初步归为一类, 就能避免二叉树分类过程中的强制分类,极大地降低了误分误判的可能性。

字符识别中的样本是有限的,通过分析有限样本相互之间的字符匹配度, 对比字符匹配度和经验阈值,即可以构造出优化的SVM多分类器。

基于字符匹配度优化的SVM多分类器, 构建了K-1个分类器, 同时在确保最佳识别正确率的前提下 , 尽可能减少了样本地总体分类次数。

本文以字符0-7为例,首先计算字符匹配度。

依据字符的匹配度,分成两类K1和K2。K1和K2继续划分子类,直到最终的子类只含有一个样本。K1和K2划分要同时考虑以下三个条件:

以上公式表示,K1和K2各自类内的样本平均匹配度最高,同时K1和K2类间的样本平均匹配度最低。将三个公式进行合并:

这样就转化成为了约束条件下的最优化问题,存在最优解,但可能不唯一。

根据推导公式进行逐步分类,得到最后的分类结构图如图5所示。

3.2 对照实验

分别采用四种方法对字符库中随机选择的400个字符经行识别,实验结果统计如表2。

4结束语

本文综合分析了SVM多分类器的构造思路及其优缺点,提出了基于字符匹配度的SVM多分类器设计方法。在实验中通过对比自身方法和其他方法对于随机给定字符识别的训练时间、识别时间、识别准确率、漏识率,证明在样本分类有限且可预判的情况下,依据字符匹配度来粗划分, 能够有效兼顾识别正确率和识别效率。

本文目前研究的是字符模板匹配的相似度,进一步改善的空间在于可以基于字符不同的特征来确定相似度,可以进一步减少计算量。

浅谈字符串模式匹配的常用算法 篇2

随着计算机技术的日新月异, 计算机的应用早已不限于数值计算, 而是更多的用于非数值计算的处理, 而非数值计算处理的对象很多都是字符串数据。字符串作为一种数据类型出现在更多的程序设计语言中, 同时也产生了一系列字符串相关的操作。字符串简称为串。在一些常见的应用程序中, 如学生的姓名和性别以及学生的民族、籍贯等一般都是作为字符串处理的, 合理的设计和应用字符串的各种操作变得尤为重要。子串定位操作是字符串串处理中最重要的运算之一, 而且字符串的模式匹配算法在计算机领域一直都是一个研究热点。

1 基本概念

字符串的定位操作亦被称为串的模式匹配。什么是模式匹配呢?模式匹配就是判断某个串, 亦称为模式串是否是其它给定串的子串。若是给定串的子串, 则返回该子串的起始位置, 即该串的第一个字符在给定字符串的数组的下标的位置。若不是, 则给出匹配不成功或不是子串的信息 (0或假) 。模式匹配的现实应用非常广, 例如在信息检索程序、文字编辑及翻译系统、实时对答系统、搜索引擎、特征码匹配以及DNA匹配等应用中, 都要用到串匹配操作。

2 模式匹配的基本算法

首先介绍一种最基本最简单的模式匹配算法, 它是一种回溯的匹配算法。也称为BF算法 (Brute-Force, 最基本的字符串匹配算法) , BF算法基本思路很简单:设置计数指针i和j分别指示主串S和子串即模式串T中目前正待比较的字符的位置。从主串S的首个字符开始和子串的第一个字符进行对比, 如果相等, 则继续逐一比较后面的每一个字符;若不相等则回溯, 从主串的当前与比较字符的下一个字符起重新和子串的第一个字符进行对比, 以此类推, 直到子串T中的每个字符都与主串S中的一个连续的字符串序列相等, 此时匹配成功, 函数返回值为与模式串T中的首个字符相等的字符在主串S中的数组下标的位置, 否则返回匹配不成功的信息。例如模式串T=”abcac”, 主串S=”ababcabcacb”, 函数返回值应该为6。

3 模式匹配的改进算法之KMP算法

这种由Knuth和Pratt以及Morris同时研究发现的改进的模式匹配算法, 简称KMP算法。算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。它是一种在一个字符串中定位另一个串的高效算法, 简单匹配算法的时间复杂度为O (m*n) ;而KMP匹配算法, 可以证明它的时间复杂度为O (m+n) , 即算法可以基于时间复杂度O (m+n) 完成字符串的模式匹配操作。其改进之处主要表现在:当某一趟匹配过程中出现字符比较不匹配的时候, 不需要位置指针i进行回溯, 而是利用已经得到的“部分匹配”的信息将模式向右移动尽可能长的一段距离后, 继续进行下一次比较。

KMP算法的基本思路是:主串设为S, 模式串设为T, 通常的的做法即我们的期望的是某一趟匹配过程中, S[i]和T[j]匹配失败, 指针i不回溯, 模式串T向右移动至某个特定的位置上, 使得T[k]对应于S[i]继续向右进行匹配。很明显, 现在我们要解决的关键问题是串T移动到哪个位置上?假设此位置为k, 即S[i]和T[j]匹配失败后, 指针i不动, 模式串T向右移动, 使T[k]和S[i]对应上并继续向右进行比较, 这里把主串表示为S=s1s2s3…sn, 模式串表示为T=t1t2…tm。要满足这一假设, 就要有如下表达式成立:

式子左边是tk前的k-1个字符, 右边是si前的k-1个字符。而本趟匹配失败是在si和tj之处, 从此次匹配可得到的部分匹配结果是:

由于k

式3左边是tj前的k-1个字符, 右边是si前的k-1个字符, 通过 (式1) 和 (式3) 得到关系:

可得出结论:某一趟匹配在si和tj匹配失败后, 如果模式串中有满足关系4的子串存在, 就是说模式串中的前k-1个字符与模式串中tj字符前面的k-1个字符相等时, 模式串T就可以向右移动从而令tk和si对应上, 从而继续向右进行比较即可。求得模式的next函数之后, 匹配操作可继续进行:假设以指针i和j分别指示主串和模式串中的比较字符, 令i的初值为pos, j的初值为1。若在匹配过程中si≠tj, 则i和j分别增1, 若si≠tj匹配失败后, 则i不变, j退到next[j]位置再比较, 若相等, 则指针各自增1, 否则j再退到下一个next值的位置, 依此类推。直至下列两种情况:一种是j退到某个next值时字符比较相等, 则i和j分别增1继续进行匹配;另一种是j退到值为零 (即模式串的第一个字符) , 则此时i和j也要分别增1, 表明从主串的下一个字符起和模式串重新开始匹配。

模式匹配的KMP算法是一种改进的模式匹配算法, 之所以要改进, 是因为它较以前模式匹配的朴素算法有更高的效率和完整性, 更适合实际程序开发的需要。在实际应用中, 根据具体应用要求的不同, 可以自己设计更合理的结构, 基于结构设计出更适合自己应用需要的模式匹配算法, 不要过分拘泥于固有的形式和算法。

参考文献

[1]郝春梅.数据结构 (C语言版) [M].北京:清华大学出版社, 2010

[2]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版, 2008

多字符串匹配 篇3

当今时代,计算机技术早已普及并迅猛发展,而这一学科中最经典、研究最广泛的问题之一就是字符串匹配,它已经是众多领域中不可或缺的应用手段。精确匹配领域是早期的研究目标,提出的算法主要有单模式匹配算法和多模式匹配算法。近些年来,人们越来越发现对近似字符串匹配问题的研究更是非常必要的,它虽然经历了不短的时间历程,但是绝大多数主要是将DNA等小型字符集或英文等中等大小字符集作为研究对象,而对于汉字乃至亚洲语音等大型字符集的研究却仍然不多。提出的基于拼音输入法的中文字符串近似匹配查询技术就可以解决这样的问题。

2 字符串近似匹配技术概况

许多解决近似字符串匹配问题的经典求解算法都以动态规划算法为基础,随后又涌现出了一些改进的近似字符串匹配算法。对这些技术进行分析和归类,总体上包括:动态规划技术(Dynamic Programming)、自动机技术(Automaton)、文本分片技术、过滤方法(Filters)技术等。各种技术又都有其优缺点。在实际中,位并行技术通常需结合动态规划技术或自动机技术才能充分发挥效率。

3 中文字符串近似匹配查询

近似字符串匹配问题的研究虽然已经经历了不短的时间历程,其相应的研究资料也很多,但是其中的研究对象绝大多数主要是针对DNA等小型字符集或针对英文等中等大小字符集,而对于汉字乃至亚洲语音等大型字符集的研究却仍然不多。主要介绍了基于拼音输入法的中文字符串近似匹配查询技术的研究。

在使用拼音输入法输入汉字时,每个汉字都有其对应的键盘序列,可以理解为一个汉字字符串与一个拼音字符串相对应。比如:“新闻”-->“xinwen”。但是中国汉语丰富多彩,同时也存在音同字不同的情况,比如:“xinwen”同时也可以对应“新文”,“欣闻”,“新汶”(“新汶川”的子串)等字符串。基于这种情况,当在中文字符集中要搜索某个感兴趣的关键汉字串(查询串Q),并想查找出拼音与之近似的其他中文字符串时,就可以根据其音同字不同或音似字不同的特点来满足要求。研究目标就是基于q-gram的思想,针对拼音输入法来查找出中文字符串的近似串。

为了便于理解,下面先对提出的基于拼音输入法的中文字符串近似匹配查询技术进行总体说明。描述过程如图1所示。

3.1 汉字转拼音

将汉字字符集转换成拼音字符集,即将字符集中的汉字串逐句转换成拼音串。转换的原因是由于查找汉字串近似串的方式是基于拼音输入法的,故将汉字串转换为拼音串为进一步使用q-gram方法做好准备工作。

在完成上述工作的同时,还创新建立了拼音汉字对照字典。此字典包括某汉字在其汉字句串中的偏移位置以及此汉字对应拼音的首字母在其拼音句串中的偏移位置。这样做的目的是为了后期与面向拼音串的候选集联合使用,找出近似串的有效拼音字符位置。

3.2 构造面向拼音串的候选集

基于q-gram思想将上一步中转换好的拼音字符集划分成若干个gram,并创新建立双元素倒排索引。这种倒排索引与以往倒排索引的区别在于,它不仅包括某个gram在其拼音句串中的偏移位置ID,还将此拼音句串的ID号做了标记。这样做的原因是因为:q-gram思想的原型是基于英文单词,长度较短;而文中使用的对象将是若干个拼音句串,长度较长。所以,使用双元素倒排索引不仅可以确定相似串所在的拼音句串,还可以找到相似串在拼音句串中的可能出现位置。

3.3 构造中文字符集的候选集

利用上一步确定的拼音句串中近似串的可能出现位置和拼音汉字对照字典找出备选汉字相似串,然后计算出该备选汉字串的拼音串与查询串对应拼音串的编辑距离ED,以及计算每一个ED不超过阈值k的汉字备选串与查询串Q的汉字编辑距离ED,最后按照设定的基于拼音的近似汉字串衡量标准输出前top-k’个近似结果。

4 结语

字符串的精确匹配是计算机科学的基本研究问题之一,一般可分为两种算法,即单模式匹配算法和多模式匹配算法。而字符串近似匹配问题则是它的扩充,并且因为有着重要的应用价值而被许多领域广泛关注。因此,研究和设计高效的字符串近似匹配算法具有重要的实际意义和理论价值。

摘要：字符串匹配是计算机科学中最经典、研究最广泛的问题之一,并且已经被应用到了众多领域当中。近似字符串匹配问题的研究虽然经历了不短的时间历程,但是其中的研究对象绝大多数主要是针对DNA等小型字符集或针对英文等中等大小字符集,而对于汉字乃至亚洲语音等大型字符集的研究却仍然不多。因此,研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。

关键词：中文字符串,近似匹配,过滤,q-gram技术

参考文献

[1]Navarro G,Raffinot M.柔性字符串匹配[M].北京:电子工业出版社,2007.

[2]Smith T F and Waterman M S.Identification of common molecular sebsequences[J].Journal of Molecular Biology,1981,Vol.147:195-197.

多字符串匹配 篇4

实现Word操作的考核评分主要有两种途径[1]:第一种是通过记录并分析考生的操作步骤来实现阅卷评分;第二种是通过分析考生实际操作的结果文档来实现阅卷评分。目前,一般使用基于第二种途径的考核评分方法。

第二种途径的考核评分方法有:(1)读取Word的文件格式,然后根据文件内容进行评分[2,3]。但由于微软只公布了RTF的文档格式,这种方法受到很大的限制。(2)使用微软Office的VBA(Visual Basic for Applications)技术获取文档内容与属性以实现评分[1,4,5,6,7]。VBA技术对各种版本的Office应用兼容性好且容易实现,所以第二种方法得到了广泛的应用。

1 Word自动阅卷系统设计

1.1 设计思想

Word自动阅卷系统总体设计思想是:利用VBA技术,打开Word文档并通过VBA提供的接口调用一系列方法,设置或提取所打开的Word文档属性实现自动阅卷。一次自动阅卷的过程如下:根据测试题目,预先设置好Word测试的标准答案文档,预先设计评分点;同时打开标准答案文档与考生操作的结果文档,并根据评分点进行比较评分[4]。基于上述思路,一个Word自动阅卷系统的设计主要考虑如下工作:(1)确定有关Word操作可能考核的项目,列出全部评分点,并对每个评分点进行定义,形成规则;(2)根据自动阅卷思想,设计自动阅卷系统的逻辑框架,并对各个功能模块进行设计;(3)根据评分规则,确定所采用的匹配算法计算分数。

1.2 评分规则

根据Word软件的常用操作,将Word的属性整理成评分点,整理有[1]:文字录入、文档页面、文字格式、段落格式、页眉、页脚、边框、底纹、首字下沉、分栏、图片、艺术字、表格。在这些评分点下面,还根据具体情况分为几个小的评分点,如文档页面分为:页边距、页面方向等项目。

为了解决评分点规则设置问题,本文采用多级方式对Word题目评分点进行设置。将整理的评分点从1开始编号,评分点下面的小项也从1开始编号,中间采用“.”好隔开,比如文档页面编号为2,而它的子规则页边距编号为2.1,页边距的子规则上页边距编号为2.1.1。规则表结构见表1:

这种多级编号的评分点设置有利于阅卷系统的扩展,如果将来Word阅卷系统增加新的功能,只需增加规则的编号,无需对整个系统进行改变。

1.3 匹配算法

Word自动阅卷系统在设计过程中还要更多的考虑容错性的问题。例如,题目要求设置第三段的字体格式。但是,如果考试在第三段前面加了若干回车符,使之变成了第四段,或者误删了第二段,使之成为第二段。这些误操作都可能会影响到Word自动阅卷对对象定位的准确率。

另外,在Word操作中,一段文字中字符格式不一致,该段落的格式是没有定义的。如果在考试过程中同时要求设置一段文字格式和段落当中个别几个字符格式,采用整个段落匹配的方式与实际考试要求内容有所偏差。

所以,我们在进行Word自动改卷系统实现时有两种方案:(1)在题目设计的过程中,要周密的考虑,消除这些影响;(2)采用字符串匹配方式查找评分点的位置,而不是采用段落的方式查找。同时,在匹配过程中采用按字符方式匹配格式,消除个别字符对段落的影响。明显第二种方式使得系统具有很强的容错能力。在Word自动阅卷系统设计采用了第二种方式。

2 Word自动阅卷系统实现

2.1 系统环境

本文采用了VBA技术实现Word自动阅卷系统。选择Microsoft Visual Studio 2008+My Sql4.1+VSTO(Visual Studio Tools for the Microsoft Office System)作为开发环境。VSTO是Office 2003和Visual Studio.NET结合的工具,是VBA技术的.NET平台化,VSTO的解决方案具有更高的安全性和更丰富的部署模式[8]。

2.2 系统框图

Word自动阅卷系统分为两个部分:设置评分规则模块和自动阅卷模块。前者将标准文档的评分点抽取出来并进行评分点设置,将评分规则存入规则库中。后者根据规则库里面的内容对测试文档进行比较,最终得到考试成绩。Word文档的评分点抽取和比较都通过VBA提取出来。系统的框图如图1所示:

3 规则匹配算法实现

为了提高系统容错能力,将Word的评分规则分为两类,一类是固定位置属性评分规则,如页面属性、图片属性等等,这些对象是固定的,他们的属性比较只需要直接读取,然后比较。第二类是位置可变属性评分规则,比如:段落属性、字体属性等等,这些属性与文章内容相关,需要定位之后读取,才可以比较。所以规则匹配算法分为两类。

3.1 算法描述

固定位置属性评分规则匹配算法A1:

(1)VBA读取Word测试文件属性;

(2)读取Word标准文件评分规则表;

(3)比较两个属性是否一致,一致得分,不一致不得分;

(4)退出。

位置可变属性评分规则匹配算法采用字符串匹配算法实现,算法的实现参考文献[9],主要思路是通过字符串匹配算法,计算出评分规则对象所在位置,然后读取对象属性进行比较。

位置可变属性评分规则匹配算法A2:

(1)读取Word标准文件规则对应的字符串S;

(2)模糊查找S所在Word测试文件所在位置[9]如果没有找到,调用算法A1,找到进入(3);

(3)确定S对应与Word测试文件字符串S1;

(4)确定S字符串每一个文字的属性与S1中对应的文字属性是否一致,并记录相同个数n;

(5)计算模糊匹配公式P=n/S.length,如果P的值大于某一个数字F,得分,否则不得分;

(6)退出。

这里S.length是字符串S的长度。F代表规则匹配的程度,值在0到1之间,值越大,表明要求匹配的程度越高,一般取F=0.8时匹配效果最好。

3.2 算法的复杂度

算法A1是时间复杂度是常数,算法A2主要是步骤(2)与(4)花费时间。步骤(2)花费时间[9]是O(S.length*L),L是文章的长度,一般有L>>S.length。步骤(4)花费时间是O(S.length),总的花费时间是:O(S.length*L)+O(S.length)=O(L)。

一般测试的Word文档的文字长度是不长的,匹配算法耗时很短。与没有增加字符串匹配的规则比较算法相比改卷速度没有太大变化,但具有很强的容错能力。

4 实验设计和结果

目前关于Word操作题的自动阅卷系统还没有完整的测试例库,因此从海南省2008年起的计算机统考试题中随机抽取4道Word操作题作为测试题目,由2个班90多名学生测试后提交的测试文档作为测试样例。同时由教师进行手工改卷,两个结果分别比较。Word的操作结果匹配到达了100%,改卷时间也大为缩短。

5 结束语

本文利用VBA技术设计开发了一套完整的Word操作题自动阅卷系统。并提出评分规则设置编号,和采用模块化设计方案,方便了系统的维护和扩展功能。同时为了解决Word改卷规则匹配的问题,提出了基于字符串模糊匹配的规则匹配算法,实现了具有很强容错性的Word操作题自动阅卷系统,对同类型的系统设计有借鉴意义。

参考文献

[1]汤克明,陈崚.Word自动阅卷系统的设计与实现[J].计算机工程与应用,2008,44(35):69-71.

[2]Zhu Qiao-ming,Chen Que,Zhai Jie.Design and implementation of anautomatic examination paper marking system[J].Computer Engineeringand Science,1999,21(3):66-70.

[3]Zhu Qiao-ming,Zhai Jie,Zhao Xing-tao.Design of document interpreterof Word 7.0 Chinese edition[J].Mini-MicroSystems,1999,20(11):876-880.

[4]宗德才.操作题自动评分系统的设计与实现[J|.计算机工程与设计,2010,31(5):1156-1160.

[5]Zhu Jiang,Xie Shen-quan.The implementation of auto checking testpaper for word operations[J].Natural Science Journal of XiangtanUniversity,2002,24(3):49-51.

[6]Zhang Liang,Zhan Guo-hua.The design and implementation of openand intelligent marking system for computer operation test[J].ComputerEngineering and Application,2001,37(20):108-110.

[7]Ye Zhi-min,Yang Jian,Yin Xin-chun.Manipulate word using Delphiprogram[J].Journal of Yangzhou University,Natural Science Edition,1998,1(4):67-70.

[8]Brian A Randall.Visual Studio Tools for the Microsoft Office System[EB/OL].http://www.microsoft.com/china/msdn/library/office/office/VSToolOfficesys.mspx,2004-12-1.

多字符串匹配 篇5

1 检测算法和检测系统模型

字符串匹配检测算法主要有:布鲁姆算法[1]、KMP算法[2,3]、BM(Boyer-Moore)算法[4]、BMH(Boyer-Moore-Horspool)算法、QS(Quick Search)算法、AC(Aho-Corasick)算法、MWM(Modified Wu-Manber)算法[2,5]等。字符串匹配检测部分可分为布鲁姆过滤器和哈希表两部分。

硬件检测系统使用Altera公司的Cyclone Ⅱ EP2C35F672C6 FPGA,它由一块含4 096个存储单元和2个读/写端口的RAM构成一个标准布鲁姆过滤器的存储数组。设定一个标准布鲁姆过滤器含有2个哈希函数。

为了降低查询错误率,使用5个标准布鲁姆过滤器处理同一组预定义字符串,这时,理论的查询错误率为;在查询字符串阶段,当5个标准布鲁姆过滤器同时输出字符串匹配信号时,字符串匹配检测部分将输出当前检测的字符串给哈希表进行验证。由5个BF组成的结构称为微型布鲁姆过滤器(MBF)。为了处理更多的预定义字符串,使用4个MBF来构成一个大布鲁姆过滤器(LBF),且采用MBF做选择器来选择其中的MBF。它能处理5 000个预定义字符串。

一个LBF结构能够处理一个固定长度的字符串,为了能够处理不同长度的预定义字符串,需要在字符串匹配检测部分中使用多个LBF,这种结构称之为检测引擎。为了加大吞吐率,将多个检测引擎并行使用,构成检测引擎组。如图1所示,各个检测引擎分别将各自的结果输出。接着设计出了标准布鲁姆过滤器、MBF、LBF的算法。使用它们来建立布鲁姆过滤器字符串匹配检测部分,本设计中设定引擎处理的字符串的长度为4 bit。

在向硬件移植时,为了能够处理任意长度的字符串,需要在上述部件的外部设置一个字符串处理部分,将接收到的<4 bit的字符串补成4 bit的长度,同时为了区分由不同长度的字符串补成的4 bit的字符串,需要在补充部分添加相应的标志位;对于长度>4 bit的字符串,可以将其拆分成多个4 bit的字符串分别进行处理。

2 字符串匹配检测系统的实现

2.1 模型的C语言实现

完成字符串匹配检测系统的C语言程序后,得到标准布鲁姆过滤器、MBF和LBF的查询错误率随预定义字符串数目增长的变化曲线,并将标准布鲁姆过滤器的查询错误率随预定义字符串数目增长的变化曲线与理论曲线进行比较,验证其功能。

标准布鲁姆过滤器、MBF、LBF、哈希表的工作流程相同,如图2所示。

哈希函数是布鲁姆过滤器的核心部分,它计算出来的哈希地址用于将输入的字符串映射到布鲁姆过滤器的存储数组中。哈希地址计算需要多个计算步骤,其程序流程,如图3所示。其中产生的哈希序列是一个长度为32的向量,该向量的值是输入字符串(4 bit)的32 bit中的值。

观察标准布鲁姆过滤器的查询错误率随预定义字符串数目增长的变化曲线,并将其与理论曲线进行比较,测试得出的结果,如图4所示。从图4中可以看出,标准布鲁姆过滤器的功能达到了理论要求。

然后,将3个模型的查询错误率随预定义字符串数目增长的变化曲线相比较,得到图5的结果。从图5中可以看出,MBF的查询错误率比标准布鲁姆过滤器的查询错误率明显下降,当预定义字符串数目过多,布鲁姆过滤器的存储数组已经基本全部被置为1时,二者的查询错误率才开始接近。LBF中有4个MBF,由于MBF选择器的作用,使输入到每个MBF中的预定义字符串的数目减少,这保证了LBF的查询错误率相对于MBF保持在一个很低的水平上。经过测试,验证了标准布鲁姆过滤器、MBF和LBF的C语言程序的功能,在哈希表部分和字符串匹配检测系统的测试中没有错误出现。

2.2 模型的Verilog语言实现

字符串匹配检测部分的Verilog模型同样分为Bloom Filter部分和哈希表部分。在测试中使用对应C语言程序的数据,以保证软件和硬件设计功能完全相同。

按照标准布鲁姆过滤器、MBF、LBF和哈希表字符串匹配检测系统的测试流程进行测试后得到各部分功能仿真波形,如图6～图10所示。

3 逻辑综合和时序仿真

3.1 字符串匹配检测系统的逻辑综合

使用Quartus 6.0完成字符串匹配检测系统各部分的逻辑综合。由于布鲁姆过滤器的存储数组可能占用过多的FPGA片上逻辑单元,所以改用FPGA内部的RAM来实现。

本设计中的RAM,写入时钟为25 MHz,采用Altera公司自带的MegaWizard Plug-In进行自动设计,按照FPGA的物理结构来配置RAM的参数。在Altera Cyclone Ⅱ EP2C35F672C6 FPGA中一块,RAM有2个读/写端口,所以设计的RAM的端口有2组,每组含有1个数据输入端口,1个数据输出端口,1个地址输入端口和1个写使能端;由于布鲁姆过滤器所处理的字符串为32 bit,所以RAM的输入、输出端口宽度都为32位;由于FPGA片上RAM的深度为4 kB,所以设计的RAM深度为4 kB,根据RAM的深度和RAM的输入输出端口宽度可以确定RAM中有128个地址空间,每个地址空间为32位,需7位地址来寻址,所以输入地址端口的宽度为7位。

在逻辑综合中,分别选择标准布鲁姆过滤器、检测单元(MBF)、LBF和哈希表作为顶层模块,在Quartus 6.0中选择Altera Cyclone Ⅱ EP2C35F672C6 FPGA来完成逻辑综合,同时为了能够对系统的关键模块进行时序仿真,使Quartus 6.0在完成逻辑综合后导出相应的网表和延时文件供ModelSimSE 6.0使用。

3.1.1 标准布鲁姆过滤器的逻辑综合结果

标准布鲁姆过滤器的逻辑综合结果显示该结构使用了FPGA片上1 030个逻辑单元,占总逻辑单元的3%;整个结构由851个寄存器组成;标准布鲁姆过滤器占用了45个管脚,占总管脚数的9%;共使用4 kB的FPGA片上RAM;整个逻辑综合在25 MHz的时钟频率下完成。

标准布鲁姆过滤器的子模块为哈希函数模块和RAM模块。

(1) 哈希函数模块。

用于计算输入字符串的哈希地址,哈希函数模块的输入端口有4个:时钟输入端,用于输入时钟;输入端hash,用于控制向哈希函数模块输入计算哈希地址时使用的转换矩阵;输入端reset,用于控制哈希函数模块的复位;数据输入端口在hash被置1时向哈希函数模块输入计算哈希地址时使用的转换矩阵,在查询字符串阶段向哈希函数模块输入待检测的字符串。哈希函数模块的输出端口在查询字符串阶段分别输出2个哈希地址。哈希函数模块的模型,如图11所示。

(2) 存储器模块。

用于存储布鲁姆过滤器的存储数组。RAM模块的输入端口有6个:时钟输入端,用于输入时钟;输入端wren_a和wren_b为写使能端,其高电平时为写使能,低电平时为读使能;输入端address_a和address_b为地址输入端;输入端data_a为数据输入端口,在wren_a置1时,向RAM模块输入布鲁姆过滤器的存储数组中的值。RAM模块的输出端口为2个数据输出端,在查询字符串阶段,这两个端口分别输出2个不同地址上的数据。存储器的模型,如图12所示。

3.1.2 哈希表的逻辑综合结果

使用Quartus 6.0中的Cyclone Ⅱ EP2C35F672C6 FPGA完成哈希表的逻辑综合。综合结果显示使用了FPGA片上606个逻辑单元,占总逻辑单元的2%;模型由460个寄存器组成,一共使用85个管脚,占总管脚数的18%,整个逻辑综合在25 MHz的时钟频率下完成。

(1) 字符串比较器模块。

判断输入的字符串与哈希存储表中存储的字符串是否相等。它的输入端口有2个,数据输入端口inputdata输入待查询字符串;数据输入端口element输入哈希存储表中哈希地址对应单元中的值。字符串比较器模块的输出端口有2个,二者用于表示输入的待检测字符串是否与哈希存储表中存储的字符串相同。match高电平有效,当输出高电平时,表示待查询的字符串与哈希表中存储的字符串匹配;none高电平有效,当输出高电平时,表示待查询的字符串不存在于哈希表中。字符串比较器模块,如图13所示。

(2) 控制模块。

用于控制哈希表的工作流程。它的输入端口有5个,时钟输入端,用于输入时钟;输入端match和none用于标识该次字符串查询中是否找到了存在于预定义字符串中的字符串,控制模块将根据二者的值调整哈希表的运行状态;输入端query,用于控制哈希表进入查询字符串阶段,其高电平时有效;输入端reset,用于控制自身进行复位。控制模块的输出端口有4个,在查询字符串阶段,端口getdata用于控制从Testbench中读入哈希存储表中相应位置的值,并使Testbench暂停输入待检测字符串;端口counter和full用于控制偏移地址计算模块产生偏移地址,counter为当次需要对1进行左移的位数,full为控制信号,当full为高电平时,偏移地址计算模块将产生偏移地址;端口f为高电平时表示输入的待查询字符串在哈希表中,该信号将被反馈给Testbench。控制模块,如图14所示。

(3) 偏移地址计算模块。

用于产生开放地址法中使用的偏移地址。它的输入端口有2个,输入端口full高电平有效,当其为高电平时,偏移地址计算模块产生偏移地址;从输入端口counter中输入计算偏移地址所需对1进行左移位的位数。偏移地址计算模块的输出端口输出偏移地址。偏移地址计算模块的模型,如图15所示。

(4) 寻址地址计算模块。

用于产生哈希存储表中的地址。它的输入端口有2个,输入端口offset输入偏移地址;输入端口hashAddress输入哈希地址。寻址地址计算模块的输出端口输出用于哈希存储表中的地址。寻址地址计算模块,如图16所示。

(5) 哈希地址计算模块。

用于计算输入字符串的哈希地址。其输入端口有4个,输入端clk输入时钟;输入端hash高电平有效,控制向哈希地址计算模块输入计算哈希地址所需的转换矩阵;输入端口reset控制模块的复位,其高电平有效;输入端口inputdata在hash置1时向哈希地址计算模块输入转换矩阵中的值,在查询字符串阶段向模块输入待检测的字符串。输出端输出哈希地址。哈希地址计算模块,如图17所示。

3.1.3 检测单元MBF的逻辑综合结果

使用Quartus 6.0中的Cyclone Ⅱ EP2C35F672C6 FPGA完成MBF的逻辑综合。逻辑综合结果显示使用了FPGA片上5 475个逻辑单元,占总逻辑单元的16%;模型由4383个寄存器构成,一共使用45个管脚,占总管脚数的9%,占用了FPGA片上RAM的20 480 bit。整个逻辑综合在时钟频率25 MHz下完成。在MBF中有5个标准布鲁姆过滤器模块和相应的控制逻辑。

3.1.4 LBF的逻辑综合结果

使用Quartus 6.0中的Cyclone Ⅱ EP2C35F672C6 FPGA完成LBF的逻辑综合。逻辑综合结果显示使用了FPGA片上23 375个逻辑单元,占总逻辑单元的68%;模型由17 998个寄存器构成,占用了FPGA片上RAM 81 920 bit。整个逻辑综合在时钟频率25 MHz下完成。在LBF中有4个标准布鲁姆过滤器模块和相应的控制逻辑。

综上所述,在逻辑综合完成后,从字符串匹配检测系统各部分的RTL图中可以看出,所综合出来的结构与所设计的模块结构完全相同,通过逻辑综合完成了Verilog RTL级代码到FPGA的硬件结构之间的映射。

3.2 字符串匹配检测系统的时序仿真

在字符串匹配检测系统各部分的逻辑综合完成后,使用逻辑综合得到的网表和延时文件对标准布鲁姆过滤器、哈希表分别进行时序仿真,验证逻辑综合结果是否满足时序要求。

模块在时序仿真中使用的Testbench与其功能仿真时使用的Testbench保持一致,测试激励也相同,使用综合后得到的网表文件替换功能仿真时使用的设计文件,将延时文件添加到工程中。由于在Quartus 6.0中选择了Cyclone Ⅱ EP2C35F672C6 FPGA进行逻辑综合,所以必须添加库cycloneii_atoms.v到工程中,它包含了Altera Cyclone Ⅱ EP2C35F672C6 FPGA的相关信息。

3.2.1 标准布鲁姆过滤器的时序仿真

标准布鲁姆过滤器的输出端口为f,在待测字符串的查询阶段,当它出现高电平时,则表明当前检测的字符串在预定义字符串中。

标准布鲁姆过滤器的时序仿真波形,如图18所示。从图10可以看出,标准布鲁姆过滤器进入了字符串查询阶段,在功能仿真时,f的上升沿在clk的上升沿时出现。从图18可以看出,在时序仿真时,f的上升沿在clk的上升沿来到时并没有出现,而是在时钟的上升沿过去一小段时间之后才出现。

经过测试,标准布鲁姆过滤器的逻辑功能在逻辑综合后没有发生改变,其输出信号的变化要比功能仿真时晚出现11.987 ns。测试结果显示标准布鲁姆过滤器可以稳定工作在25 MHz的时钟频率下,吞吐率为200 MB·s-1(8 bit/cycle)。

3.2.2 哈希表的时序仿真

哈希表有输出端口f和getdata,在查询字符串阶段,Testbench根据getdata的值改变query信号的值,进而控制查询的进程;当f出现高电平时,表明当前输入的待查字符串存在于哈希表中。哈希表的时序仿真波形,如图19所示,此时哈希表已经进入字符串查询阶段。在图19的哈希表功能仿真波形中,哈希表的反馈信号f的上升沿在时钟上升沿时出现。query信号受getdata信号的控制被置1或者清零。在图19的哈希表时序仿真波形中,由于query信号的置1和清零都受到哈希表的反馈信号getdata的控制,而哈希表模块输出信号getdata延时变化,所以query信号的置1和清零都发生延迟;哈希表的反馈信号f的上升沿在时钟上升沿来到时没有出现,而在时钟上升沿来到后一段时间出现。

经过测试,哈希表的逻辑功能在逻辑综合后没有发生改变,哈希表模块的输出信号变化要比功能仿真时 晚出现6.979 ns。测试结果显示哈希表模块可以稳定工作在25 MHz的时钟频率下,吞吐率为200 Mbps。

4 结束语

文中采用布鲁姆过滤器与哈希表相结合的方案,设计了硬件字符串匹配检测系统的结构;使用C语言程序描述字符串匹配检测系统的功能,并通过测试结果与理论推导的结果进行比较,得出了C语言程序功能正确的结论;完成了系统的Verilog RTL级描述,利用C语言程序的数据进行了功能仿真,验证了Verilog程序的正确性;最后,面向Altera Cyclone Ⅱ EP2C35F672C6 FPGA器件,完成了系统的逻辑综合,并完成2个子模块(标准布鲁姆过滤器、哈希表)的时序仿真。结果表明,上述2个子模块的吞吐率为200 MB·s-1。本设计的硬件字符串匹配检测系统在数据库检索、网络入侵检测等方面具有一定的实用价值。

参考文献

[1]Bloom B.Space/time Tradeoff in Hash Coding with Allowa-ble Errors[J].Communications of the ACM,1970,13(7):422-426.

[2]张胤.模式匹配型入侵检测系统改进[D].秦皇岛:燕山大学,2006.

[3]潘群娜.基于模式匹配KMP算法的探讨[J].科技信息,2007(13):335-337.

[4]Rafig A N M E,El-Kharashi M W,Gebali F.A Fast String Search Algorithm for Deep Packet Classification[J].Computer Communications,2004,27(15):1524-1538.

多字符串匹配 篇6

目前, 字符串匹配算法的串行研究相对较为成熟, 对并行字符串算法的研究是学术界和工业界的研究热点[1]。为获得更高的性能, 需要根据运行平台的不同对程序进行改进, 以牺牲通用性为代价来获得性能的提高[2]。可编程图像处理器单元 (Graphic Processing Unit, GPU) 现已成为计算主力, 利用通用图形处理器做高强度高并行的通用科学计算 (General-Purpose Computing on, GPU) 已成为提高算法效率切实可行的手段, 其并行线程执行模式和线程同步技术为大规模并行计算提供了一种崭新的实现解决方案[3,4]。由于字符串匹配算法在各个应用领域需要处理海量信息。因此, 用图形处理器做字符串匹配算法的高性能计算成为可行的方法。字符串匹配加速算法早期致力于研究更高性能的软件算法, 然而, 基于软件的方法已经难以实现匹配效率上的大幅提升[5], 无法满足现实需求。为达到更快的匹配速度, 研究者提出了基于专有硬件的解决方案, 而现场可编程门阵列[6,7] (Field Programmable Gate Array, FPGA) 作为一种资源可重用器件, 可以用基本的逻辑门电路, 比如AND、OR、XOR、NOT等来实现字符的比较, 其处理速度快, 也在字符串匹配算法方面得到重视。

本文针对不同的实验平台, 对字符串匹配算法做了不同的实现, 主要从CPU、GPU及FPGA 3个方面进行了验证, 得到不同平台上的测试结果。

1相关研究

在字符串匹配算法中, 朴素串匹配算法 (Brute Force, BF) 是最为基础的算法, 是指在文本中检测模式可能出现匹配的任何地方, 从左向右逐次扫描文本。朴素串匹配算法在长度为N的文本中查找长度为M的模式需要约N&apos;M次比较, 虽然在串行的比较机制中处理速度较慢, 但其优点在于无需进行模式字符串的预处理操作, 且需要额外的空间也是固定的, 在具体的应用中, BF算法的性能比改进的KMP算法、BM算法等具有更大的优势。BF算法在CPU中的实现机制较为简单, 且有较强大理论与实践背景。

然而, 处理机为了得到性能的大幅提高, 致力于研究多核、纵核以及阵列机等并行机制。近年来GPU已具备了实现大规模快速计算的编程能力, NVIDIA公司提出的计算统一设备结构 (Compute Unified Device Architecture, CUDA) 技术就是这方面的杰出代表。CUDA编程带给人们一种新的理念, 可将GPU高速并行处理能力广泛应用在科学计算中。GPU是实现类似于单指令多数据流 (Single Instruction Multiple Data, SIMD) 的体系结构, 由于其拥有大量的计算部件单元而使得GPU适合处理字符串匹配算法中的重复性匹配操作。FPGA由于其所特有的逻辑电路, 使得字符串匹配算法也易在FPGA里实现。借助FPGA实现字符串匹配算法, 可充分利用FPGA中的查找表以及寄存器等逻辑单元, 可增强字符串匹配算法的实际应用能力。

鉴于BF算法无需进行额外字符预处理操作, 且其属于数据级并行运算, 易于在GPU和FPGA上实现, 因此本文采用BF算法来实现字符串匹配。

2字符串匹配算法的实现

字符串匹配的定义:假设文本是一个长度为n的数组T[1…n], 模式是一个长度为m￡n的数组P[1…m], 且P和T都是属于有限字母表∑中的字符, 即在T中找到所有包含P的子串。

BF算法的匹配过程可形象的看成一个包含模式的“模板”P沿文本T移动, 同时每次位移注意模板上的字符是否与文本中的相应字符相等, 如图1所示。

实验平台的详细参数。

CPU:采用英特尔Core i7-4770k, 该CPU核数为4;最大时钟频率是3.5 GHz;内存为16 MB;系统为Ubuntu 12.04。

GPU:采用NVIDIA Ge Force GTX 650的GPU, 该GPU含有384个流处理器;显存容量为1 GB;显存位宽为128位;CUDA版本为5.5, GPU时钟频率为1.03 GHz。

FPGA:测试平台是Xilinx ML605开发板, 该开发板上包含Xilinx Vertex-6 XC6VLX240T-1FFG1156FPGA芯片。该芯片的最大时钟频率为200 MHz, 芯片中含有的逻辑单元为10万个。

2.1 CPU的实现

字符串匹配算法在CPU上的实现, 即串行执行。BF算法在CPU上执行的伪代码描述为

由伪代码描述可知, 由于该算法要作n-m+1次位移, 而每次模式的比较最多需要m次, 因此在最坏的情况下, BF算法的串行执行时间复杂度为O ( (nm+1) m) 。然而, 由于BF算法没有预处理过程, 因此整个算法的运行时间等于它的匹配时间。

2.2 GPU的实现

GPU强大的并行能力使GPU比CPU具有更好的计算能力。CUDA作为GPU计算的开发环境, 它是一个全新的软硬件架构, 可将GPU视为一个并行数据计算的设备, 对所完成的计算进行分配和管理。GPU的特点是处理数据密集型和并行数据的计算, 因此CUDA适合需要大规模并行计算的领域, 本文基于GPU的字符串匹配算法就是采用CUDA编程方法。

CUDA的执行模型是并行线程执行模型 (Parallel Threads Execution, PTX) , CUDA线程的执行方式是基于SIMD方式, 即一个多处理器上的每个线程在任何时间执行的指令均相同。在CUDA中由多个线程组成线程块 (Threads Block) , 多个线程块进一步组成线程格 (Threads Grid) , 如图2所示。CUDA中线程块的线程最大值依赖于GPU的性能参数, 比如共享内存大小, 寄存器数量等[8]。

CUDA线程在物理上独立的设备上执行, 此类设备作为运行C语言程序主机的协同处理器, 内核程序在GPU上执行, 而C语言程序在CPU上执行。即串行代码在主机上执行, 而并行代码在设备上执行, CUDA的编程模型如图3所示。

为在GPU中实现字符串匹配算法, 对BF算法的串行结构进行了分析, 可以得到, 如果文本数据量较大时, 能够利用GPU的多线程, 将文本存入全局存储中, 然后将文本信息分配给线程进行处理, 这样就能充分利用GPU的并行计算能力, 得到匹配结果。字符串匹配在GPU中执行的伪代码描述如下:

1 (CPU) 获取数据, 将文本和模式从RAM传入GPU的global mem:

2 (GPU) 各个Block开始执行Kernel函数:

3初始化GPU分配的内存

4将模式载入到shared mem

5 while文本没有结束do

6载入文本, 从global mem的到shared mem:

7for文本中的字符串do

8BM查找算法

9 end for

10 end while

11 (CPU) 从GPU回传结果到CPU。

2.3 FPGA的实现

BF算法在FPGA中的实现, 能够充分利用FPGA的逻辑资源[9], 比如查找表 (Look Up Table, LUT) , 由于FPGA内部处理是并行的, 因此, 根据匹配需要的文本及模式的大小, 能够确定具体使用逻辑资源的多少, 字符串匹配的FPGA实现结构, 如图4所示。

图4所示为文本长度为w, 模式长度为i的匹配结构。检测窗口主要将待检测文本字符通过BF检测, 然后对处理结果做仲裁, 得到模式能否被该文本匹配。

字符串匹配算法的FPGA实现采用Verilog HDL语言描述, 设计工具为Xilinx ISE 13.2, 开发板型号为Xilinx ML605, 该开发板上包含Xilinx Vertex-6XC6VL240T-1FFG1156 FPGA芯片。字符串匹配算法在FPGA中的设计是将待匹配的运算分配到FPGA内部大量的逻辑单元中, 因此处理速度较快, 最快情况下, 1个时钟周期内就可以将数据处理完。

3性能分析

对于3种不同方式实现的字符串匹配算法, 使用最新的Snort 2.9.6规则库[10]作为模式, 采用随机数生成不同长度的数据作为测试文本, 对其性能进行了测试验证。测试方法为:对每组不同长度的模式和文本做100次匹配运算, 得到每组数据处理的平均值, 如表1所示, 其CPU和GPU的时钟周期是由匹配时间与对应时钟频率的乘积。

时钟周期

由表1的对比数据可以得到, CPU的串行处理时间与文本和模式乘积成正比, 随着数据任务量的增加, CPU的执行时间也相应增加。在GPU中, 由于16 MB数据的任务量还没有达到GPU的满载工作状态, 因而此时GPU的匹配速度较快, 而当数据任务量为64 MB时, 已经使GPU达到满载状态, 因此GPU的任务量为64 MB能够充分利用GPU的计算单元, 此时GPU与CPU的加速比大于任务量为16 MB时的加速比。然而当任务量进一步增加到128 MB时, 超过了GPU所拥有的计算单元, 相较于64 MB与CPU的加速比, 此时的加速比降低。GPU相较CPU的实现, 匹配速度能够提高6个数量级以上。FPGA由于具有较强的灵活性, 可编程性以及大量的逻辑运算单元, 因此FPGA的处理速度是最快的。而当任务量增加到128 MB时, FPGA的处理速度有所降低, 这是因为FPGA的逻辑运算单元已经处于超满载状态, 因此处理速度会相应降低, 如表2所示, 为XC6VL240T-1FFG1156 FPGA芯片在不同测试数据情况下的资源消耗情况。该芯片中所包含的逻辑资源为:寄存器数目301 440个, 查找表为150 720, 存储数目为58 400。

因此, 通过在CPU、GPU及FPGA中对BF算法的测试可以得到, FPGA的处理速度最快, 比GPU的处理速度快10倍;GPU相较CPU的实现方案, 匹配速度能够提高6个数量级以上;CPU的串行处理速度最慢。但FPGA的资源消耗最多, GPU次之, CPU的资源消耗最少, 且实现更为简单。

4结束语

针对计算机科学研究广泛的算法—字符串匹配算法进行了研究与分析, 分别在CPU、GPU及FPGA上完成了BF算法的设计。对BF算法的3种实现在Snort规则下进行了分析比较, GPU充分利用其SIMD架构对串行BF算法做并行优化, FPGA可以利用内部大量的逻辑运算单元, 对BF算法进行快速处理。在同等测试条件下, 得到FPGA的处理速度最快, GPU相较CPU的实现方案, 匹配速度能够提高6个数量级以上;CPU的串行处理速度最慢。

参考文献

[1]LEFOHN A, KNISS J, OWENS J.Implementing efficient parallel data structures on GPUs[J].GPU Gems, 2005 (2) :521-545.

[2]PHARR M, FERNANDO R.GPU gems 2:programming techniques for high-performance graphics and general-purpose computation[M].New York:Addison-Wesley Professional, 2005.

[3]LIN K J, HUANG Y H, LIN C Y.Efficient parallel knuthmorris-pratt algorithm for multi-GPUs with CUDA:Advances in Intelligent Systems and Applications-Volume 2[M].Berlin Heidelberg:Springer, 2013.

[4]ZHA X, SAHNI S.GPU-to-GPU and host-to-host multipattern string matching on a GPU[J].IEEE Transactions on Computers, 2013, 62 (6) :1156-1169.

[5]李伟男, 鄂跃鹏, 葛敬国, 等.多模式匹配算法及硬件实现[J].软件学报, 2006, 17 (12) :2403-2415.

[6]AHMED G F, KHARE N.Hardware based string matching algorithms:A survey[J].International Journal of Computer Applications, 2014, 88 (11) :16-19.

[7]杨海涛, 苏涛, 巫幪.基于FPGA的SDRAM控制器的设计和实现[J].电子科技, 2007 (1) :8-12.

[8]OWENS J D, LUEBKE D, GOVINDARAJU N, et al.A survey of general-purpose computation on graphics hardware[J].Computer Graphics Forum, 2007, 26 (1) :80-113.