AC多模式匹配算法研究

AC算法的内存空间开销大,不利于硬件实现。为此,提出AC多模式匹配算法。分析AC算法的特点,使用位图存储技术和压缩处理技术对其进行改进。从模式串长度和模式串数目角度出发进行实验,结果表明,该算法能缩短扫描时间,提高模式匹配速度和访问速度。     

基于多线程技术的d-BM改进算法

在分析基于压缩的DNA模式匹配算法d-BM的基础上,采用多线程技术,设计并实现MultipleOF-dBM算法和DoubleOF-dBM算法。实验结果表明,新算法的匹配速度比d-BM算法有所提高。     

基于多线程技术的d BM改进算法*

在分析基于压缩的DNA模式匹配算法dBM的基础上,采用多线程技术,设计并实现MultipleOFdBM算法和DoubleOFdBM算法。实验结果表明,新算法的匹配速度比dBM算法有所提高。     

基于WM算法的多模式匹配改进算法WMN

入侵检测系统中有部分时间用来进行模式匹配,因此提高模式匹配算法的处理速度具有重要的意义。从两个方面改进了目前公认效率较高的多模式匹配算法WM,设计出WMN算法,并对该算法进行了性能测试和分析。实验证明该文提出的WMN算法能够有效提高模式匹配的处理速度。     

模式匹配算法性能测试

模式匹配算法在防火墙、入侵检测等系统中,有十分重要的应用价值.对两个经典的多模式匹配算法、六个知名的单模式精确匹配算法和一个单模式模糊匹配算法进行了性能测试,并分析了它们的特点及适用场合,为应用系统开发者选择模式匹配算法提供了有益的参考.     

BM模式匹配改进算法

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

一种单模式匹配算法

本文在介绍经典模式匹配算法BM算法及其改进算法BMH算法的基础上,提出了一种单模式匹配算法。实验表明,该算法有效的加快了模式匹配的速度,提高了匹配效率。     

改进的KMP算法在生物序列模式自动识别中的应用

介绍了改进后的KMP算法在生物序列模式自动识别中的应用以及关于生物序列中模式的概念和表示方法，并对生物序列中有关模式匹配的知识作了介绍，阐述了如何将生物序列转换为字符串，以及如何编程实现此算法，成功地对KMP算法作了一些改进，实现了生物序列中模式的自动识别，实验结果表明，该算法具有较好的可行性。     

入侵检测系统中模式匹配算法研究

分析了BF,KMP,BM模式匹配算法,在此算法的基础上提出了一种改进的模式匹配算法(FBM),该算法的思想是时BM 算法中滑动距离函数dist右移模式距离大小进行改进,并且定义了两个新的滑动距离函数,在不同的条件下,分别调用不同的滑动距离函数,更好地拉制模式匹配过程.实验结果表明,该算法比BF,KMP和BM算法显著减少...     

一种面向入侵检测的Wu-Manber算法研究

模式匹配算法是入侵防御系统中检测引擎的核心算法,模式匹配算法的效率决定了入侵防御系统的性能。本文对模式匹配算法进行了研究,重点分析了多模式匹配算法Wu-Manber算法,并针对Wu-Manber算法存在的不足,提出了Wu-Manber算法的改进算法。     

基于HASH-TCAM算法的高速模式匹配研究*

针对基于硬件的模式匹配算法处理长模式串时吞吐率不高的问题,提出了基于将哈希压缩与TCAM查表相结合的算法——HASH-TCAM算法。通过哈希算法将待匹配的关键字预处理,减少其长度,解决了40 Gbps线速下的长模式串匹配问题,并通过40 Gbps测试仪验证了该算法的可行性。分析表明,该算法在查询的固定关键字长度为72 Byte,模式集数目为5000,哈希压缩后地址的编码宽度为46 bit时,模式识别模块以牺牲冲突的代价实现了51.2 Gbps的吞吐率,可以满足40 Gbps链路中DPI算法的逐包线速的需求     

基于特征点界标过滤的时间序列模式匹配方法

动态时间弯曲距离能度量不等长的时间序列、且具有较高的匹配精度,因此广泛应用在时间序列模式匹配中。但其计算复杂度较高,制约了在大规模数据集上的应用。为了实现时间序列模式度量结果和计算复杂度的平衡,提出一种基于特征点界标过滤的时间序列模式匹配方法。首先,提出一种特征点界标过滤的特征提取方法,保留时间序列主要特征,压缩时间维度;然后,利用动态时间弯曲距离对特征序列进行相似性度量;最后,在应用数据集上对所提方法进行有效性验证。实验结果表明,所提方法在保证高精度的前提下,能有效降低计算复杂度。     

基于奇异事件特征的时间序列相似模式匹配

现有的时间序列特征提取方法多为单尺度方法，导致特征点的时间定位不准确，从而影响模式发现的质量。该文基于小波奇异检测理论，提出了一种多尺度时间序列特征提取方法，利用奇异特征将时间序列压缩为事件序列表示，定义了事件序列动态时间弯曲相似度量，给出了基于事件序列相似模式匹配算法。实验表明，该方法具有较高的匹配精度和较低的计算代价。     

Inplace run-length 2d compressed search

The recent explosion in the amount of stored data has necessitated the storage and transmission of data in compressed form. The need to quickly access this data has given rise to a new paradigm in searching, that of compressed matching (Proc. Data Compression Conf., Snow Bird, UT, 1992, pp. 279–288; Proc. 8th Annu. Symp. on Combinatorial Pattern Matching (CPM 97), Lecture Notes in Computer Science, Vol. 1264, Springer, Berlin, 1997, pp. 40–51; Proc. 7th Annu. Symp. on Combinatorial Pattern Matching (CPM 96), Lecture Notes in Computer Science, Vol. 1075, Springer, Berlin, 1996, pp. 39–49). The goal of the compressed pattern matching problem is to find a pattern in a text without decompressing the text.

The criterion of extra space is very relevant to compressed searching. An algorithm is called inplace if the amount of extra space used is proportional to the input size of the pattern. In this paper we present a 2d compressed matching algorithm that is inplace. Let compressed(T) and compressed(P) denote the compressed text and pattern, respectively. The algorithm presented in this paper runs in time O(|compressed(T)|+|P|log σ) where σ is min(|P|,|Σ|), and Σ is the alphabet, for all patterns that have no trivial rows (rows consisting of a single repeating symbol). The amount of space used is O(|compressed(P)|). The compression used is the 2d run-length compression, used in FAX transmission.     

Accelerating Boyer–Moore searches on binary texts

The Boyer and Moore (BM) pattern matching algorithm is considered as one of the best, but its performance is reduced on binary data. Yet, searching in binary texts has important applications, such as compressed matching. The paper shows how, by means of some pre-computed tables, one may implement the BM algorithm also for the binary case without referring to bits, and processing only entire blocks such as bytes or words, thereby significantly reducing the number of comparisons. Empirical comparisons show that the new variant performs better than regular binary BM and even than BDM.     

关联规则挖掘AprioriTid算法的改进

提出了一种将AprioriTid算法与事务压缩和项目压缩相结合的改进算法。该算法中候选项目集及支持度计算是在每条事务压缩后通过联接产生,候选项目集采用关键字识别,省去了AprioriTid算法中的剪枝和字符串模式匹配步骤。实验结果表明,改进的算法执行效率明显优于AprioriTid算法。     

Optimal matching by the transiently chaotic neural network

Dynamic programming matching (DPM) is a technique that finds an optimal match between two sequences of feature vectors allowing for stretched and compressed sections of the sequence. The purpose of this study is to formulate the matching problem as an optimization task and carry out this optimization problem by means of a chaotic neural network. The proposed method uses TCNN, a Hopfield neural network with decaying self-feedback, to find the best-matching (i.e., the lowest global distance) path between an input and a template. Experimental results show a very good performance for the proposed algorithm in pattern recognition tasks.