Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.

Spectral matching based remote sensing identification of two main crop rotation patterns in a large irrigation district

The rapid identification of planting patterns for major crops in a large irrigated district has vital importance for irrigation management,water fee collection,and crop yield estimation.In this study,the OTSU algorithm and Mean-Shift algorithm were employed to automatically determine threshold values for mapping two main rotated crop patterns at the pixel scale.A time series analysis was conducted to extract the spatial distribution of rice-wheat and wheat-maize rotations in the Chuanhang irrigation district from 2016 to 2020.The results demonstrate that both threshold segmentation algorithms are reliable in extracting the spatial distribution of the crops,with an overall accuracy exceeding 80%.Additionally,both Kappa coefficients surpass 0.7,indicating better performance by OTSU method.Over the period from 2016 to 2020,the area occupied by rice-wheat rotation cropping ranged from 12500 to 14400 hm 2;whereas wheat-maize rotation cropping exhibited smaller and more variable areas ranging from 19730 to 34070 hm 2.These findings highlight how remote sensing-based approaches can provide reliable support for rapidly and accurately identifying the spatial distribution of main crop rotation patterns within a large irrigation district.

A Fast Pattern Matching Algorithm Using Changing Consecutive Characters

Pattern matching is a very important algorithm used in many applications such as search engine and DNA analysis. They are aiming to find a pattern in a text. This paper proposes a Pattern Matching Algorithm Using Changing Consecutive Characters (PMCCC) to make the searching pro- cess of the algorithm faster. PMCCC enhances the shift process that determines how the pattern moves in case of the occurrence of the mismatch between the pattern and the text. It enhances the Berry Ravindran (BR) shift function by using m consecutive characters where m is the pattern length. The formal basis and the algorithms are presented. The experimental results show that PMCCC made enhancements in searching process by reducing the number of comparisons and the number of attempts. Comparing the results of PMCCC with other related algorithms has shown significant enhancements in average number of comparisons and average number of attempts.

面向入侵检测的改进BMHS模式匹配算法

模式匹配算法是入侵检测系统中使用较多的一种算法。分析几种常用模式匹配算法,提出一种基于BMHS的改进算法——N-BMHS算法。该算法对字符串进行双向模式匹配,引入一个新的数组s记录模式串中字符的出现次数,次数为1时可以利用已匹配的信息来辅助得到模式串的最大移动距离。实验结果表明,改进的模式匹配算法能减少比较次数,有效提高匹配速度。

一种改进的BMH模式匹配算法

分析了目前网络上最流行的BM算法及其改进算法BMH,在此基础上提出了BMH算法的改进算法BMH2。考虑了模式串自身的特征,在原有移动距离数组的基础上增加一个新的移动数组,从而充分利用模式串特征进行更大距离的移动,使算法获得更高的效率。实验证明,改进后的算法能够增加"坏字符"方法的右移量,有效地提高匹配速率。

入侵检测系统中改进的AC_BMH算法

提出一种改进的AC_BMH算法。该算法利用双字符进行跳跃,可以在增大模式串失配概率的同时跳过更大的距离,通过结合QS算法进一步增加模式串匹配失败时的跳跃距离,并借助压缩存储机制降低内存的使用量。实验结果表明,相比原AC_BMH算法,改进算法的字符串匹配速度提高了29%～52%,在模式串较多时,内存使用量可减少90%。

一种改进的BMHS模式匹配算法

模式匹配在计算机应用中扮演着很重要的角色。通过分析BM,BMH和BMHS算法及相关改进算法,提出BMHS算法的改进算法(DBMHS)。该算法(DBMHS)充分利用模式串两端字符,通过比较模式串两端字符的跳转距离来实现更大距离的跳转。实验证明,改进后的算法显著增加了匹配窗口的跳转距离,有效地提高了匹配效率。

BMH2C单模匹配算法的研究与改进

BMH2C算法综合BMH和BMHS算法,利用当前窗口字符t[k]及其下一字符t[k+1]组成的双字符串来决定模式串右移量,具有比BM算法、BMH算法、BMHS算法更优的性能。但对于双字符串在模式串中出现一次及以上的情况。BMH2C算法中的模式串右移量仍有待进一步增大,从而减少当前窗口右移次数,提高BMH2C算法的匹配效率。为此,在BMH2C算法的基础上提出一种改进算法,该算法考虑双字符串舭t[k]t[k+1]在模式串中出现的次数,以及该双字符串在模式串中对应位置的后继字符与字符t[k+2]的相等关系。改进算法利用2个右移数组和1个模式串预处理数组,在匹配过程中通过判断字符t[k+2]与模式串预处理数组中相应字符是否相等,从而选择2个右移数组之一的对应值作为当前窗口的右移量。实验结果显示,在相同条件下,对于当前窗口移动次数和匹配所耗时间,BMH2C改进算法比BMH2C算法分别平均减少11.33%和9.40%,有效提高了匹配效率。

Four Sliding Windows Pattern Matching Algorithm (FSW)

This paper presents an efficient pattern matching algorithm (FSW). FSW improves the searching process for a pattern in a text. It scans the text with the help of four sliding windows. The windows are equal to the length of the pattern, allowing multiple alignments in the searching process. The text is divided into two parts;each part is scanned from both sides simultaneously using two sliding windows. The four windows slide in parallel in both parts of the text. The comparisons done between the text and the pattern are done from both of the pattern sides in parallel. The conducted experiments show that FSW achieves the best overall results in the number of attempts and the number of character comparisons compared to the pattern matching algorithms: Two Sliding Windows (TSW), Enhanced Two Sliding Windows algorithm (ETSW) and Berry-Ravindran algorithm (BR). The best time case is calculated and found to be??while the average case time complexity is??.

Enhancing ERS-A Algorithm for Pattern Matching (EERS-A)

Pattern matching is a very important topic in computer science. It has been used in various applications such as information retrieval, virus scanning, DNA sequence analysis, data mining, machine learning, network security and pattern recognition. This paper has presented a new pattern matching algorithm—Enhanced ERS-A, which is an improvement over ERS-S algorithm. In ERS-A, two sliding windows are used to scan the text from the left and the right simultaneously. The proposed algorithm also scans the text from the left and the right simultaneously as well as making comparisons with the pattern from both sides simultaneously. The comparisons done between the text and the pattern are done from both sides in parallel. The shift technique used in the Enhanced ERS-A is the four consecutive characters in the text immediately following the pattern window. The experimental results show that the Enhanced ERS-A has enhanced the process of pattern matching by reducing the number of comparisons performed.

A Tree Pattern Matching Algorithm for XML Queries with Structural Preferences

In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD—Document Type Definition, Schema, etc.) increases the risk of obtaining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as “*”). The reason is that in both cases, users write queries according to the document model they have in mind;this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evaluations. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results;moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the proposed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.

一种基于改进BMHS的基因序列匹配算法

基因序列匹配是生物信息学中一个重要的问题,基因序列在计算机处理中通常被看作是由有限的字符集组成的文本字符串,故可将基因序列匹配问题归结为字符串匹配问题。本文在对传统的BMHS字符串匹配算法的分析的基础上,提出了一种更为高效的基因序列匹配算法——BMHS_M算法。该算法充分利用已匹配部分的信息、移动窗口末尾的字符下一位字符与首字符的关系,并采取预判机制进行融合跳跃,最大移动步数可达到2m+2。实验结果表明,改进后的BMHS_M算法有效提高了基因序列的匹配速度。

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

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

BM模式匹配改进算法

字符串模式匹配在实际生活中被广泛的应用,它也是计算机基础科学的一个重要部分,现在比较著名的模式匹配算法有BF算法、KMP算法、RK算法和BM算法。讨论了一种基于BM模式匹配算法及其算法的改进。

基于双字符序检测的BM模式匹配改进算法

BM算法是一类效率较高的单模式匹配算法,通常改进的BM算法往往从提高字符首次不匹配概率和匹配窗口的最大移动距离入手,但为实现此目的所带来的高访存开销使算法实际效率受到影响。DCSBM算法以适当减小关键步长为代价,在利用双字符序检测提高首次匹配失败概率的同时,对匹配窗口移动关键步长字符距离所需的查表次数和访存次数进行优化。经测试,DCSBM算法显著提高了匹配窗口的平均移动距离。在文本或模式串相对较长情况下,该算法实际测试效率优于BM、BMHS、BMN等算法。

一种改进的BM模式匹配算法

首先介绍了目前最常用的BM模式匹配算法,以及其改进算法Boyer-Moore-Horspool(BMH)算法,在此基础上提出了另一种改进的BM算法,该算法减少了匹配次数,有效的加快模式匹配的速度。

一种面向入侵检测的BM模式匹配改进算法

在分析了目前常用的模式匹配算法的基础上,提出了一种改进的BM算法。实验结果表明改进的模式匹配算法能减少比较次数,有效地提高了匹配速度。

BM算法的研究与改进

随着网络的迅速发展,网络安全问题日益突出,入侵检测技术也成为当今社会关注的焦点.对于基于规则的入侵检测来说,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能.文中介绍了KM P和BM算法,对BM算法的改进进行了研究,并提出一种改进的BM算法,改进后的算法极大地提高了匹配速度.

一种BM模式匹配算法的改进

模式匹配算法是入侵检测系统中使用较多的一种重要算法。在分析了BM算法以及相关算法的基础上,提出了一种新的改进算法——BMI算法。该算法借鉴了BM算法的思想,并利用了下一字符和末字符的单一性和组合性,有效地提高了最大位移出现的概率。实验测试结果表明该算法能够有效提高匹配过程的效率。

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

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