一种适用于大规模特征集的快速匹配算法

提出了一种适用于大规模特征集的快速匹配算法——SRS算法,该算法性能优异,在特征集达到100 000条时,匹配速度比经典算法快10倍以上。该算法适用于内容过滤、防病毒、反垃圾邮件、短信过滤、网络入侵检测和防御等众多领域。     

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

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

字符串匹配的技术研究与实现

字符串匹配算法在文本挖掘有着重要的应用。本文首先介绍了常见的BF、BM、KMP、QuickSearch等字符串vt配算法,最后通过具体的实验数据给出了几种匹配算法的测试结果,并分析了这几种算法的性能及影响这些性能的因素。     

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

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

几种字符串匹配算法的分析和比较

字符串匹配技术在许多领域里被广泛应用。分析了BF、KMP、BM算法以及一些重要的改进算法,并对其性能进行了测试,为不同的应用领域采用适当的算法提供了思路。     

一种中文字符串近似匹配查询技术研究

字符串匹配是计算机科学中最经典、研究最广泛的问题之一,并且已经被应用到了众多领域当中。近似字符串匹配问题的研究虽然经历了不短的时间历程,但是其中的研究对象绝大多数主要是针对DNA等小型字符集或针对英文等中等大小字符集,而对于汉字乃至亚洲语音等大型字符集的研究却仍然不多。因此,研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。     

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

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

字符串模糊匹配算法的探讨

字符串模糊匹配问题在计算机中有着广泛的应用．尝试探讨一种无论从算法时间复杂度上讲还是编程复杂度上都比较优秀的一种模糊匹配算法。     

一种基于分段匹配的字符串匹配算法

针对已有算法对文本和模式的相关性依赖较大,提出一种基于分段的字符串匹配算法——SM。该算法利用特殊字符将文本先分段再匹配,且匹配过程对模式内容和长度不敏感。通过将SM算法与经典算法进行分析和实验对比,证明SM算法性能稳定,特别是在多模式字符串匹配情况下,SM算法具有比Wu-Manber算法更快的速度和更小的空间消耗。     

一种快速的字符串匹配算法

字符串匹配技术在许多领域里广泛应用，本文在分析了BF、BM算法以及一些重要的改进算法的基础上，提出了一种新的改进算法——BMH2C，该算法利用两个字符计算右移量并保存在二维数组里，使右移量增大，比较次数减少，有效地提高了匹配速度．最后本文还给出了几种匹配算法的测试结果。     

Simple algorithms for partial point set pattern matching under rigid motion

This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (n?k), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined ε-neighborhood region around some point in P. The proposed algorithm for the exact matching needs O(n²) space and preprocessing time. The existence of a match for a given query set Q can be checked in time in the worst-case, where α is the maximum number of equidistant pairs of point in P. For a set of n points, α may be O(n^4/3) in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the ε-neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are and O(n), respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition.     

BM串匹配的一个改进算法

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

邻间关系匹配算法研究

对于26个字母的全排,它们的邻间关系是唯一的。文中根据这个特性,针对子串长度较长的(大于26)字符串匹配问题,提出了一种基于邻间关系的匹配算法。该算法把字符串的邻间关系转化为十进制的数值,并利用这一数值实现字符串的快速匹配。该算法时间复杂度为О(m-n),且算法简便,容易实现。     

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

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

Efficient implementation of Aho–Corasick pattern matching automata using Unicode

We study different efficient implementations of an Aho–Corasick pattern matching automaton when searching for patterns in Unicode text. Much of the previous research has been based on the assumption of a relatively small alphabet, for example the 7‐bit ASCII. Our aim is to examine the differences in performance arising from the use of a large alphabet, such as Unicode that is widely used today. The main concern is the representation of the transition function of the pattern matching automaton. We examine and compare array, linked list, hashing, balanced tree, perfect hashing, hybrid, triple‐array, and double‐array representations. For perfect hashing, we present an algorithm that constructs the hash tables in expected linear time and linear space. We implement the Aho–Corasick automaton in Java using the different transition function representations, and we evaluate their performance. Triple‐array and double‐array performed best in our experiments, with perfect hashing, hashing, and balanced tree coming next. We discovered that the array implementation has a slow preprocessing time when using the Unicode alphabet. It seems that the use of a large alphabet can slow down the preprocessing time of the automaton considerably depending on the transition function representation used. Copyright © 2006 John Wiley & Sons, Ltd.     

一种用于内容过滤和检测的快速多关键词识别算法

基于字符串匹配的检测方法是内容过滤和检测系统中一类很重要的分析方法,首先分析了现有的几种快速字符串匹配算法,然后提出了一种新的多模式字符串匹配算法,并简单分析了算法的复杂性,算法在设计的过程中吸取了BM算法中跳跃的特性,采用了后缀树算法得到了最大跳跃值,采用AC算法的匹配自动机原理从而避免对搜索树内每一个字符的匹配,最后,通过具体的实验数据验证了这些算法的性能,通过实验可以看出,新算法使得检测速度有很大提高,并有效屏蔽了关键词数量的增加对检测速度的影响。     

一种基于模式最长前缀正文分割的串匹配新算法

字符串的模式匹配问题是计算机科学的基本问题之一，本文提出了基于模式最长前缀正文分割的匹配新算法(Text Divided Algorithm，以下简称TD算法)．首先在模式P中寻找最长的前缀子串subp，使其末字符在subp中只出现一次；然后根据subp末字符的特点，将正文T进行分段，按段对模式P进行匹配．新算法有以下重要的特点：1．最坏情况下，本算法有效地减少了字符重复比较的次数，从而提高了算法的匹配效率；2．匹配算法在二维匹配和不精确匹配中较易推广；3．匹配过程近似于直接算法，便于接受和理解。     

短规则有效的快速多模式匹配算法

随着网络技术快速发展,多模式匹配算法所处理的模式集合数目呈爆炸式增长且模式长度不统一,传统的多模式匹配算法已无法有效适应新的模式集合：不同的模式集合,同一算法呈现的性能差异明显。针对模式长度不等且分布不均匀的模式集合,提出一种改进WM的多模式匹配算法（MWM）,将模式集合分为长短两个集合并构造各自的长短SHIFT表,辅助WM算法原有SHIFT表验证匹配效果,匹配过程由单一线程完成。该算法不仅减少了模式验证次数,而且提高了算法的平均跳转距离。实验结果表明,所提出的多模式匹配算法（MWM）在模式长度不等且分布不均匀的模式集合下表现出更优的性能,随着模式集合的数目增多,性能提升越明显。在模式集合数目达到100 000时,相比WM算法,该算法性能提升达到了40%。