一种按字长匹配的Wu-Manber多模式匹配算法

多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40％.当最短模式串长度为2和3时,搜索时间缩短了60％以上.     

一种面向大规模短特征集的字符串匹配技术

面向大规模特征集的字符串匹配技术在病毒检测、内容过滤等问题上的应用愈加广泛,而短模式串一直是阻碍性能提升的重要瓶颈。针对短模式串进行分析讨论,基于跳跃算法优化,采用了动态块大小和动态Hash处理以及Hash函数设计场景化的策略,同时探讨了多核处理器与多线程设计之间的关系。实验数据证明改进的算法策略具有支撑百万级特征集字符串匹配的能力。     

一种改进的BM字符串匹配算法

经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的,在主串中存在大量子串与模式串前缀或者后缀相同时效率较低,并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法,有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算,增大了模式串的移动距离。实验结果表明,改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数,达到了提高算法效率的目的。     

面向比特流的分组快速搜索匹配算法

在比特流的模式匹配中,由于目标串和模式串字符集简单,匹配过程中匹配窗口平均跳跃长度短,导致快速搜索(QS)匹配算法效率不高。为此,分析QS算法坏字符启发规则匹配效率与字符集大小的关系,借鉴编码QS算法的编码思想,提出一种对模式串进行分组预处理并使用字符组计算跳跃集的分组QS算法,给出坏字符组启发规则与最佳分组长度的计算方法。实验结果表明,与不分组的算法相比,该算法能够增加比特流模式串匹配中匹配窗口的平均跳跃长度,提高计算效率。     

基于存储优化的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术之一.自动机的存储空间大小和Cache性能是影响多模式串匹配算法速度的关键因素.随着模式串规模的扩大,自动机的巨大存储开销导致现有的串匹配算法性能大幅度下降.从压缩存储空间以提高Cache命中率的思想出发,提出了一种对经典SBOM算法的优化策略,它用Suffix Tree代替SBOM算法中的Factor Oracle结构,同时用剪枝的方法将Suffix Tree降低为近似线性的空间复杂度,然后用双数组Trie表示之,以压缩存储空间.与SBOM算法相比,改进算法不仅能够有效地节省存储空间,而且显著地提高了串匹配的速度,非常适合于在线高速匹配的应用环境.     

一种基于子串识别的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术。巨大的存储空间开销是制约多模式匹配串算法应用的瓶颈之一。提出一种基于子串识别的多模式匹配算法—HashBOM,该算法利用位哈希表存储模式串的子串信息以大幅度减少存储空间,利用递归哈希函数计算字符串的哈希值以实现快速匹配。理论分析表明,该算法的空间复杂度为O(rm~2),优于基于子串识别的匹配算法BOM的空间复杂度O(mr|∑|log_2mr);该算法搜索匹配过程的平均时间复杂度为O(nlog|∑|)mr/m,与BOM算法相同(其中m为最短模式串的长度,r为模式串的个数,n为待匹配文本的长度,|∑|为字母表的大小)。在随机数据集和真实数据集上的实验表明,该算法的存储空间远远低于BOM算法,而匹配速度与BOM算法相当,非常适合在线实时匹配的应用环境。     

面向移动终端的URL过滤方法

在移动终端内容安全检测中,“黑名单”过滤是一种常用的手段,但有限的存储空间制约了它的应用。根据“黑名单”过滤特点研究了一种多串匹配算法的改进,以Aho-Corasick算法为例,采用两种启发式策略从不等长的URL串中提取具有代表性的、等长的模式子串,并使用双数组进一步压缩。在Nokia 5230上的测试表明,该算法的存储空间是经典AC算法的0.7%,而速度可达到95%以上。     

基于网络处理器的多模式串匹配研究

深度数据包检查是网络入侵检测系统的性能瓶颈。该文分析入侵规则集中模式串的分布特点,对多模式匹配算法FNP进行改进,研究在多核多线程体系结构的网络处理器上高效实现模式串匹配的方法。在Intel IXP2800网络处理器上的仿真实验结果表明,改进算法在规模为10 K的模式串集合上能达到6 Gb/s的吞吐量,具有几乎线性的加速比。     

一种基于有限自动机的快速串匹配算法

串匹配是字符串的基本操作之一,因此为它设计一个高效算法具有一定意义.文中基于有限自动机理论,在对经典的K.M.P.算法进行分析的基础上,提出了一种快速的串匹配算法.该算法利用自动机的状态转换表实现串匹配,避免了扫描字符串时的失败链回溯,从而加快了算法的运行速度.理论分析与实验结果均表明,在正文串比较长,模式串中局部匹配失败时失败链反馈较多的情况下,该算法在速度上明显优于K.M.P.算法.但在空间复杂度上,该算法需要较多的存储空间.     

一种改进的多模式串匹配算法

在对著名的SunWu多模式串匹配算法进行分析之后,结合QS算法的优点,设计了一种较高效的多模式串匹配算法QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果.     

一种用于大规模规则库的快速包分类算法

网络应用的发展，要求路由器必须有能力支持防火墙、入侵检测、提供QoS、流量计费等一系列功能，这些功能都要求路由器对IP包进行分类来完成对数据包的不同处理。目前的包分类算法不适用于火规模的规则数据库。该文在现有的一种基于位串的包分类算法上做了两个改进，位串的聚合和过滤规则的重排列。从而生成了一种新的包分类机制-AVA（Aggregated Bit Vector).通过评测可看出这种新的算法可以很好地应用在大规模规则数据库上，性能比原先有很大提升。     

KR字符串匹配算法的研究与实现

字符串匹配是判断模式串(短串)是否是文本串(长串)的子串。KR算法是一种随机串匹配算法,详细介绍KR串匹配算法的算法描述及代码实现过程,并对该算法进行测试,讨论该算法的实现效率。     

基于自动机并操作的多目标AC-BM算法

AC-BM算法的优点在于能同时进行多个模式串的匹配搜索,且文本串的移位得到优化,但一次只能在一个文本串中进行搜索.为了实现一次可以同时在多个文本串中进行搜索,设计了多目标AC-BM算法.利用自动机并操作技术构造多目标多模式树自动机,借助BM算法的坏字符跳转技术来计算文本串集移位.在Snort系统中分别实现2-目标AC-BM算法和3-目标AC-BM算法.实验结果表明,新算法如果在多个文本串中找到模式串就停止(表示检测到攻击行为),其在时间性能上就明显优于AC-BM算法.     

一种改进的字符串匹配模型研究

字符串匹配技术作为数据分析的基础和核心,已经被广泛应用于各个领域.通过分析字符串匹配算法的局限性和矛盾性,设计提出一种改进的字符串匹配模型.模型充分利用Tuned BM算法和Zhu-Takaoka算法正特征的显著优势,克服其性能缺点,保证字符串匹配过程中模式串每次都能移动最大安全距离,实现减少字符比较次数和增大模式串移...     

WCCS环境下连续r位串匹配算法及其并行化研究

通过将免疫系统中连续r位匹配规则引入到串匹配算法中,在传统KMP串匹配算法的基础上提出了r-KMP算法,该算法使用匹配闽值r来控制文本串与模式串的匹配程度.然后在WCCS(Windows compute cluster server)平台下部署了并行化的r-KMP算法,通过实验分析了算法的性能和时间复杂度.实验结果表明,该算法能有效的控制串匹配程度,它的并行化减少了执行时的运算时间,提高了串匹配效率.     

一种改进的字符串模式匹配算法

提出一种改进的字符串模式匹配算法。该算法对文本串进行预处理,即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记,再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数。发生匹配失败时,将模式串直接滑动到标记了的出现次数最少的字符处。通过实验证明,该算法的移动次数和比较次数有较大减少,耗费的额外空间的大小也不超过模式串的长度,进一步提高模式匹配的效率。     

基于统计和浅层语言分析的维吾尔文语义串快速抽取

该文提出了一种基于统计和浅层语言分析的维吾尔文语义串快速抽取方法,采用一种多层动态索引结构为大规模文本建词索引,结合维吾尔文词间关联规则采用一种改进的n元递增算法进行词串扩展并发现文本中的可信频繁模式,最终依次判断频繁模式串结构完整性从而得到语义串。通过在不同规模的语料上实验发现,该方法可行有效, 能够应用到维吾尔文文本挖掘多个领域。     

基于双语URL匹配模式可信度的平行网页识别研究

平行语料是自然语言处理中一项重要的基础资源,在双语平行网页中大量存在。该文首先介绍双语URL匹配模式的可信度计算方法,然后提出基于局部可信度的双语平行网页识别算法,再依据匹配模式的全局可信度,提出两种优化方法: 即利用全局可信度,救回因低于局部可信度阈值而被初始算法滤掉的匹配模式;通过全局可信度和网页检测方法,挖出深层网页。进一步,结合网站双语可信度、链接关系,侦测出种子网站周边更多较具可信度的双语网站。除了双语URL匹配模式自动识别,还利用搜索引擎,依据少数高可信度的匹配模式快速识别双语网页。为了提高以上五种方法识别候选双语网页对的准确率,计算了候选双语网页对的双语相似度,并设置阈值过滤非双语网页对。通过实验验证了所提方法的有效性。     

一种基于尾匹配q-gram的近似串匹配算法

近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。     

一种高效的多目标串匹配算法

本文通过引入右对齐位置标识方式解决了Boyer-Moore算法思想用于多串匹配的串长不等的问题，提出用于多模式串的高效匹配算法MP_BM。该算法的特点主要在于能够直接处理长度不等的多模式串匹配，同时又能获得很高的匹配效率。