基于GPU的串匹配算法研究

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

基于统一计算设备架构的并行串匹配算法

BF算法是串匹配算法经典算法之一,但并不适合GPU这种并行体系结构.提出了基于统一计算设备架构(CUDA)架构的解决方案,通过对需要处理的数据增加一定比例的冗余信息,设计了适合CUDA计算数据的独立性特点的并行BF算法.实验结果表明,基于CUDA架构的并行串匹配算法比同等CPU算法获得约10倍的加速比.此外还对该算法性能的影响因子做了分析.     

DSP处理器上的高效串匹配实现

字符串匹配是生物识别、入侵检测的基础,也是大数据互联网时代的研究热点.随着现代信息技术的发展,日常工作生活中移动及手持小型化设备的使用越发普遍.这些设备的应用场景中包含大量有关串匹配的需求,如人脸识别、实时数据查询等.串匹配算法的实时和准确性决定了使用场景的范围,因此在DSP处理器等移动小型化设备的嵌入式处理器上实现高效串匹配算法的问题变得十分迫切.该文针对DSP处理器因缺乏逻辑判断与跳转指令,难以支持高效串匹配运算的问题,提出了一种基于DSP平台特点的改进串匹配算法.该算法采用位并行的思路,在DSP处理器上实现了串匹配算法的并行化.同时通过前序启动、基于VLIW的数学运算替代逻辑判断、Q-grams等优化手段,提高该算法对于DSP平台的适应性与执行效率,最终实现了一种基于HXDSP的高效串匹配算法VBNDM2.实验结果表明,本算法针对DSP平台,有效地提高了串匹配的效率,实现了算法的高效并行化.     

BM串匹配的一个改进算法

在分析BM算法和文献[12]的基础上，给出了BM串匹配的一个改进算法。该算法有以下重要的特点：1)最坏情况下，算法有效地减少了字符重复比较的次数，提高了匹配效率；2)匹配算法在二维匹配和不精确匹配中较易推广。     

基于GPU的位并行多模式串匹配研究

图形处理器(GPU)具有较强的单一运算能力及高度并行的体系结构。根据上述特点,选择基于位并行技术的多模式串匹配算法M-BNDM,将其移植到GPU上加以实现和优化。通过对需要处理的数据进行预处理,将串匹配的过程简化为更适合CUDA计算数据的位操作。对基于CUDA架构的并行串匹配算法的性能影响因子进行分析。实验结果表明,与同等CPU算法相比,该算法能够获得约十几倍的加速比。     

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

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

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

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

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

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

病毒特征检测中改进的多模式匹配算法

针对病毒特征检测中码串长度对模式匹配算法性能影响的问题,结合基于码串长度的特征集自适应分类思路,提出了两种改进的多模式精确匹配算法,即NAC_BM和NWM_QS。改进算法通过引入文本窗口的前缀字符块WB增加了跳跃距离,减少了匹配次数,加快了匹配效率。初步实验证明,改进算法在执行时间和速率上优于原算法。     

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

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

GPU-accelerated string matching for database applications

Implementations of relational operators on GPU processors have resulted in order of magnitude speedups compared to their multicore CPU counterparts. Here we focus on the efficient implementation of string matching operators common in SQL queries. Due to different architectural features the optimal algorithm for CPUs might be suboptimal for GPUs. GPUs achieve high memory bandwidth by running thousands of threads, so it is not feasible to keep the working set of all threads in the cache in a naive implementation. In GPUs the unit of execution is a group of threads and in the presence of loops and branches, threads in a group have to follow the same execution path; if some threads diverge, then different paths are serialized. We study the cache memory efficiency of single- and multi-pattern string matching algorithms for conventional and pivoted string layouts in the GPU memory. We evaluate the memory efficiency in terms of memory access pattern and achieved memory bandwidth for different parallelization methods. To reduce thread divergence, we split string matching into multiple steps. We evaluate the different matching algorithms in terms of average- and worst-case performance and compare them against state-of-the-art CPU and GPU libraries. Our experimental evaluation shows that thread and memory efficiency affect performance significantly and that our proposed methods outperform previous CPU and GPU algorithms in terms of raw performance and power efficiency. The Knuth–Morris–Pratt algorithm is a good choice for GPUs because its regular memory access pattern makes it amenable to several GPU optimizations.     

Approximate string matching for music analysis

Approximate pattern matching algorithms have become an important tool in computer assisted music analysis and information retrieval. The number of different problem formulations has greatly expanded in recent years, not least because of the subjective nature of measuring musical similarity. From an algorithmic perspective, the complexity of each problem depends crucially on the exact definition of the difference between two strings. We present an overview of advances in approximate string matching in this field focusing on new measures of approximation.     

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

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

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。     

Applying graphics hardware to achieve extremely fast geometric pattern matching in two and three dimensional transformation space

We present a GPU-based approach to geometric pattern matching. We reduce this problem to finding the depth (maximally covered point) of an arrangement of polytopes in transformation space and describe hardware assisted (GPU) algorithms which exploit the available set of graphics operations to perform a fast rasterized depth computation. We give two alternatives, one is for translation + scale and the other is for rigid transformations, both have 3-parameters transformation space. We give extensive experimental results showing the running time of our method and its dependence on various parameters.     

Engineering order‐preserving pattern matching with SIMD parallelism

The order‐preserving pattern matching problem has gained attention in recent years. It consists in finding all substrings in the text, which have the same length and relative order as the input pattern. Typically, the text and the pattern consist of numbers. Since recent times, there has been a tendency to utilize the ability of the word RAM model to increase the efficiency of string matching algorithms. This model works on computer words, reading and processing blocks of characters at once, so that usual arithmetic and logic operations on words can be performed in one unit of time. In this paper, we present a fast order‐preserving pattern matching algorithm, which uses specialized word‐size packed string matching instructions, grounded on the single instruction multiple data instruction set architecture. We show with experimental results that the new proposed algorithm is more efficient than the previous solutions. ©2016 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.     

串匹配算法的简单并行实现

结合BM模式匹配算法和并行计算的思想,提出了一种快速的串匹配并行实现策略,该策略将文本串划分成一定长度的子串,将子串分配到不同的处理器中,在各个处理器中分别并行执行BM模式匹配,即便是在最坏的情况下也能达到较好的时间复杂度。     

串匹配算法的简单并行实现

结合BM模式匹配算法和并行计算的思想,提出了一种快速的串匹配并行实现策略,该策略将文本串划分成一定长度的子串,将子串分配到不同的处理器中,在各个处理器中分别并行执行BM模式匹配,即便是在最坏的情况下也能达到较好的时间复杂度。