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

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

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

在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得到很大提高．同时对QWM算法和Wu-Manber算法进行了实验对比，无论模式串数量和最小长度怎么变化，性能都有较大提升．实验表明，改进的算法在对英文文本进行扫描时有4％～13％的提高．

近似串匹配过滤算法研究

近似串匹配在众多研究领域都有广泛的应用,如文本检索、生物信息学等。文中对基于过滤技术的Off-line模式近似串匹配算法进行了相关研究。首先介绍了串匹配的基础知识和近似串匹配技术的应用分类;然后阐述了Off-line模式近似串匹配算法常用的索引结构;接着详细介绍了近似串匹配过滤算法的研究现状,并阐述了几个经典过滤算法的过滤原理;最后在实验中对比了这些经典过滤算法的性能差异,实验数据显示提高过滤效率和减少过滤时间是加快过滤算法匹配速度所要解决的关键问题。研究表明,基于留空q-gram的过滤算法是近似串匹配未来研究的方向。

精确串匹配的并行算法研究与实现

围绕精确串匹配的并行算法展开研究.在基于分布存储的并行机群上,以串匹配的KR(Karp-Rabin)算法为理论基础,选择合适的Hash函数,设计KR的并行串匹配算法,改进了原有算法占机时间长的缺点,从计算时间复杂度和通信时间复杂度两个方面提高了效率.

基于GPU的精确串匹配算法综述

精确串匹配是计算机领域的一个经典问题。在大数据时代,海量的数据给串匹配问题带来巨大的挑战。当前,GPU的应用得到学术界和工业界的广泛关注,基于GPU的串匹配算法研究已成为学术界的焦点。为展示近年的研究,综述了基于GPU的精确串匹配技术,针对不同的算法和GPU架构介绍精确串匹配技术在GPU上的改进:不同算法的改进具有差异性,研究时需扩展具体算法,并比较上述算法的优缺点。最后对评测指标进行介绍,展望其发展趋势。

一种面向大规模URL过滤的多模式串匹配算法

对大量有害的URL进行过滤,是目前网络安全应用系统中所亟需的关键技术.使用经典的串匹配算法检测庞大的URL规则集,需要消耗大量的计算资源和存储资源,性能十分低下.该文设计了一种适合于大规模URL过滤的多模式串匹配算法——SOGOPT.该算法在经典的SOG算法基础上,针对URL规则的特点,提出了最优窗口选择、模式串分组规约这两种优化技术,大幅度提高了SOG算法的匹配速度,在大规模URL规则集上效果尤其显著.该文设计的算法非常适合于大规模(100万级)URL实时在线匹配的应用环境.

基于GPU的串匹配算法研究

BF算法是串匹配算法中最基础的算法,但它是串行算法,不适合图形处理器(GraphicProcessing Unit,GPU)的体系结构。结合GPU的特殊体系结构,通过数据存取方式和计算策略的改进,充分利用了GPU的并行处理能力,从而基于GPU实现了BF算法。实验结果表明基于GPU的并行算法能够取得较好的加速比,同时也给出了在现有GPU架构上有效实现通用计算的瓶颈。

利用串匹配技术实现网上新闻的主题提取(英文)

从文本中提取主题串是自然语言处理的重要基础之一.传统的提取方法主要是依据“词典加匹配”的模式.由于词典的更新速度无法同步于网上新闻中新词汇涌现的速度,而且词典的内容也无法完全涵盖网上新闻的范围, 因此这种方法不适用于网上新闻的主题提取.提出并实现了一种不用词典即可提取新闻主题的新方法.该方法利用网上新闻的特殊结构,在标题和正文间寻找重复的字串.经过简单地处理,这些字串能够较好地反映新闻的主题.实验结果显示该方法能够准确、有效地提取出绝大部分网上新闻的主题,满足新闻自动处理的需要.该方法同样适用于其它亚洲语言和西方语言.

一种时间复杂度最优的精确串匹配算法

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m?1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(logσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.

串匹配算法中模式串与文本之间关系的研究

经典的串匹配算法设计和分析中假设"字符互相独立并且等概率出现",这与实际应用环境差异很大,导致出现很多问题.考虑了字符的概率分布和上下文的关联,同时兼顾应用的方便,提出了命中密度的概念.在给出基本定义和扩展定义后,通过对4种类型的代表性算法的理论和实验分析,给出了命中密度与算法性能之间的关系.同时,在对命中密度的分析中得出一些极具价值的结论.对命中密度概念的多角度理解以及对它与算法性能关系的深入剖析都说明,命中密度作为一个特征量,可以从一个侧面刻画模式串和文本之间的相关性,它对算法的设计和分析以及串匹配领域研究工作的扩展都具有指导意义.

融合像素串匹配的AVS2全色度屏幕与混合内容视频编码算法

新一代主流云计算与信息处理模式及平台中的一个主要问题是客户端与云服务器端(或客户端)之间的数据传输瓶颈问题,屏幕与混合内容编码技术以带宽最省、安全性高等优势,成为解决该问题的核心技术之一.该文在我国第二代数字音视频编解码技术标准(AVS2)的屏幕与混合内容编码(SMCC)扩展版中,提出了一种融合像素串匹配的全色度屏幕与混合内容编码技术,该技术已经被AVS2-SMCC扩展版工作草案稿采纳.针对目前AVS2不支持全色度4∶4∶4格式的特点,作者设计与实现了一种融合4∶4∶4格式的像素串匹配编码算法和4∶2∶0格式的帧内、帧间预测编码算法的全色度屏幕混合内容编解码框架与算法.在此框架下,首先提出了一种4∶2∶0格式的帧内、帧间编码算法与4∶4∶4格式的串匹配编码算法的率失真代价值计算方式;然后给出了一种改进的像素串匹配算法及其关键技术,包括最佳参考串确定算法、基于N元组的快速哈希表搜索算法、基于分段截断二进制码的长度参数编码方案和基于N元组的位移参数编码方案.实验结果表明,对于AVS2-SMCC通用测试序列中的移动的文字和图形类别,提出的算法与AVS2-P2基准算法集成了色度上、下采样后支持YUV4∶4∶4格式的编解码器相比,在编码复杂度增加较少的情况下,对于有损全帧内(AI)配置Y分量、U分量、V分量平均BD-rate降低率分别可达56.1%,97.2%,99.2%;对于有损低延迟P(LDP)配置Y分量、U分量、V分量平均BD-rate降低率分别可达41.8%,70.9%,72.9%,能大幅提高屏幕与混合内容的编码效率.

一种串匹配的快速Boyer-Moore算法

在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃中获得更大的跳跃距离,从而使算法具有更高的效率。在真实语料上的实验结果表明,QBM算法的效率较显著地高于原始的BM算法及其改进算法Improved Boyer-Moore(IBM)。

分布式存储的并行串匹配算法的设计与分析

并行串匹配算法的研究大都集中在 PRAM(parallel random access machine)模型上 ,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多 .该文采用将最优串行算法并行化的技术 ,利用模式串的周期性质 ,巧妙地将改进的 KMP(Knuth- Morris- Pratt)算法并行化 ,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法 ,其计算复杂度为 O(n/ p+m) ,通信复杂度为 O(ulogp) ,其中 n为文本串长 ,m为模式串长 ,u为模式串最小周期长 ,p为处理器数 .

HashTrie:一种空间高效的多模式串匹配算法

经典的多模式串匹配算法AC的内存开销巨大,已经无法满足当前高速网络环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种空间高效的多模式串匹配算法—Hash Trie。该算法运用递归散列函数,将模式串集合的信息存储在位向量中,以取代状态转移表来减少空间消耗,并利用Rank操作进行快速匹配校验。理论分析表明,Hash Trie算法的空间复杂度为O(|P|),与模式串集合的规模|P|线性相关,与字符集大小σ无关,优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|)。在随机数据集和真实数据集(Snort、Clam AV和URL)上的测试结果表明,Hash Trie算法比AC算法节约高达99.6%的存储空间,匹配速度约为AC算法的一半左右。Hash Trie算法适合于模式串集合规模较大、模式串长度较短的多模式串匹配问题,是一种空间高效的多模式串匹配算法。

对BM串匹配算法的一个改进

在对著名的Boyer -Moore串匹配算法进行分析后 ,对BM算法中的尝试位置移动处理部分进行改进 ,提出了IBM算法。该算法将好后缀移动与坏字符移动合并进行处理 ,从而尽量利用已有信息进行更大的尝试位置移动 ,使算法具有更高的效率。对IBM算法进行复杂度分析 ,对BM算法、KMP算法和IBM算法进行实际性能比较 ,结果表明IBM算法的平均运行时间明显优于BM算法与KMP算法。

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

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

基于模式串匹配的Ethernet协议识别算法研究

协议识别是网络安全与对抗领域中的一项关键技术。简要介绍了网络协议识别的重要性,分析了Ethernet类协议的特征,构建了协议识别的系统模型,依据Ethernet类协议的特征,提出了一种新的基于模式串匹配的协议识别算法NEWMATCH,并对该算法的性能进行了分析,并与传统模式串匹配算法(如:BF、KMP、BM等)进行了比较。该算法在Ethernet类协议识别方面具有一定的适用性。

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用a(m+1)个处理器和O(n/a+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,+<11mna.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.

一种高速精确单模式串匹配算法

串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法.

FilterFA:一种基于字符集规约的模式串匹配算法

多模式串匹配技术是入侵检测系统的核心技术之一,Aho-Corasick算法广泛应用于其中。针对AC自动机内存开销巨大影响算法性能的问题,提出一种基于字符集规约的改进算法——FilterFA。利用字符集映射函数将原字符集压缩为多个像字符集,针对像字符集构造新的自动机FilterFA,将空间复杂度降至O(P|Σ′|)。在随机数据集和真实数据集ClamAV上的测试结果表明,当像字符集大小为8,且保证误识别率小于2%时,FilterFA算法消耗的存储空间仅为AC算法的3%左右。