共查询到20条相似文献,搜索用时 156 毫秒
1.
2.
改进的多模式匹配算法 总被引:29,自引:2,他引:29
在有限自动机的多模式匹配算法(DFSA算法)的基础上,结合Quick Search算法的优点,提出了一个快速的多模式字符串匹配算法,之后在算法中以连续跳跃的思想,给出了另一个更加有效的改进,在一般情况下,这两个算法不需要匹配目标文本串中的每个字符,并充分利用了匹配过程是本次匹配不成功的信息,跳过尽可能多的字符,在模式串较长和较短的情况下,算法都有很好的性能,实验表明,在模式串较短时,所提出的算法需要的匹配时间仅为DFSA算法的1/2到1/5,在模式串较长时,所需时间为DFSA算法的1/3至1/7。 相似文献
3.
Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态。为此,提出一种快速多模式匹配算法。该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率。算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息。实验结果表明,该算法匹配精确、效率高,且支持在线操作。 相似文献
4.
双向AC算法及其在入侵检测系统中应用 总被引:1,自引:0,他引:1
在经典的多模式字符串匹配算法-AC算法的基础上,提出了双向AC算法.该算法在预处理阶段构造正向和反向两个有限状态自动机,匹配时使用正向有限自动机从文本串中间位置向右扫描,同时依据反向有限状态自动机从中间位置向左扫描.将该算法应用于开放源码的入侵检测系统Snort中,实验结果表明较BM算法、WM算法和AC算法本算法有更好... 相似文献
5.
6.
基于有序二叉树的多模式匹配算法 总被引:4,自引:0,他引:4
一、简介在一个文本串中查找用户指定的模式串在信息抽取和文本编辑中有着广泛的应用。当前,有限状态自动机(DFSA)算法是解决多模式匹配问题的常用方法。DFSA算法在匹配前对模式串集合进行预处理,转换成树型有限状态自动机,然后只需对文本串进行一次扫描就可找出所有模式串,其查找时间复杂度是O(n)。后来,在这个算法的基础上又有一些改进,实现了跳跃式查找。基于树型结构的有限自动机特别适 相似文献
7.
一种基于有限自动机的快速串匹配算法 总被引:1,自引:1,他引:0
陈倩 《计算机技术与发展》2009,19(1)
串匹配是字符串的基本操作之一,因此为它设计一个高效算法具有一定意义.文中基于有限自动机理论,在对经典的K.M.P.算法进行分析的基础上,提出了一种快速的串匹配算法.该算法利用自动机的状态转换表实现串匹配,避免了扫描字符串时的失败链回溯,从而加快了算法的运行速度.理论分析与实验结果均表明,在正文串比较长,模式串中局部匹配失败时失败链反馈较多的情况下,该算法在速度上明显优于K.M.P.算法.但在空间复杂度上,该算法需要较多的存储空间. 相似文献
8.
本文提出了一种对XML 文本进行快速串匹配的算法- XMatch。在对于XML 文本的含路径信息的模式串匹配中,由于XML 文本的结构化特点,使得传统的串匹配算法不能直接有效的使用;而现有的大部分XML 内容筛选方法都是基于SAX 分析的事件驱动过程,效率普遍较低。XMatch 在对XML 文本的结构-schema 进行分析的同时,结合模式串的路径信息,建立一个扫描自动机的有限状态自动机;此外,算法还支持带循环引用路径信息的模式串匹配。XMatch 容易扩展,可以支持普通的结构化文本的串匹配。实验结果显示,本算法的效率比使用SAX事件驱动的方法有明显的提高。 相似文献
9.
10.
11.
Aoe Junichi Yamamoto Yoneo Shimada Ryosaku 《IEEE transactions on pattern analysis and machine intelligence》1984,(1):116-120
This correspondence describes an efficient string pattern matching machine to locate all occurrences of any of a finite number of keywords and phrases in an arbitrary text string. Some conditions are defined on the states of the machine in order to improve the speed and size of the machine by Aho and Corasick [1]. The pattern matching algorithm is partitioned into various cases by combining these conditions. Finally, the correspondence illustrates the proposed approach by applying it to the analysis of the machines for a simple search. 相似文献
12.
一种优化的并行汉字/字符串匹配算法 总被引:1,自引:1,他引:0
字符串检索指在一个文本Text=t1…tn中找出一个字符串Pat=p1…pm的所有出现。本文给出了在CREW/CRCW PRAM机器模型上并行检索汉字/字符串的算法, 它使用n/m。个处理机, 预处理时间为O(m+|∑|, 并行执行时间为O(m)。 相似文献
13.
By reducing an array matching problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms may be applied to arrays. In this paper, based on the ideas due to Baker, an application of the two-dimensional on-line tessellation acceptor (2-dota) is presented for very rapid on-line detection of occurrences of a fixed set of keyarrays as embedded subarrays in a text array. The main part of the algorithm described in this paper consists of constructing two finite state pattern (string) matching machines from the keyarrays. By combining these two finite state pattern matching machines, we construct the 2-dota which, given an m × n text array, solves the two-dimensional pattern matching problem in m + n?1 steps. 相似文献
14.
模式匹配算法是入侵检测系统(IDS) 中非常重要的一种算法. 在研究和分析几种常用模式匹配算法的基础 上, 提出一种快速的基于BM(Boyer-Moore) 模式匹配的改进算法—–IBM 算法. 该算法充分利用模式串的末字符和 末字符所对应的文本串的后两字符的唯一性, 同时参考文本串本身的信息来提高模式串的移动量, 使得每次失配后, 在保证不丢失匹配成功可能性的前提下尽可能多地向后跳跃. 实验结果表明, 该算法相比其他模式匹配算法, 在检测 性能和匹配效率上均具有很大优势, 并且能够有效地提高IDS 的检测效率和性能.
相似文献15.
Partha Pratim Roy Umapada Pal Josep Lladós 《International Journal on Document Analysis and Recognition》2014,17(4):343-358
Word searching in non-structural layout such as graphical documents is a difficult task due to arbitrary orientations of text words and the presence of graphical symbols. This paper presents an efficient approach for word searching in documents of non-structural layout using an efficient indexing and retrieval approach. The proposed indexing scheme stores spatial information of text characters of a document using a character spatial feature table (CSFT). The spatial feature of text component is derived from the neighbor component information. The character labeling of a multi-scaled and multi-oriented component is performed using support vector machines. For searching purpose, the positional information of characters is obtained from the query string by splitting it into possible combinations of character pairs. Each of these character pairs searches the position of corresponding text in document with the help of CSFT. Next, the searched text components are joined and formed into sequence by spatial information matching. String matching algorithm is performed to match the query word with the character pair sequence in documents. The experimental results are presented on two different datasets of graphical documents: maps dataset and seal/logo image dataset. The results show that the method is efficient to search query word from unconstrained document layouts of arbitrary orientation. 相似文献
16.
Gerald Tripp 《Journal in Computer Virology》2006,2(1):21-34
This paper describes a finite state machine approach to string matching for an intrusion detection system. To obtain high performance, we typically need to be able to operate on input data that is several bytes wide. However, finite state machine designs become more complex when operating on large input data words, partly because of needing to match the starts and ends of a string that may occur part way through an input data word. Here we use finite state machines that each operate on only a single byte wide data input. We then provide a separate finite state machine for each byte wide data path from a multi-byte wide input data word. By splitting the search strings into multiple interleaved substrings and by combining the outputs from the individual finite state machines in an appropriate way we can perform string matching in parallel across multiple finite state machines. A hardware design for a parallel string matching engine has been generated, built for implementation in a Xilinx Field Programmable Gate Array and tested by simulation. The design is capable of operating at a search rate of 4.7 Gbps with a 32-bit input word size. 相似文献
17.
18.
An efficient algorithm for matching multiple patterns 总被引:6,自引:0,他引:6
An efficient algorithm for performing multiple pattern match in a string is described. The match algorithm combines the concept of deterministic finite state automata (DFSA) and the Boyer-Moore algorithm to achieve better performance. Experimental results indicate that in the average case, the algorithm is able to perform pattern match operations sublinearly, i.e. it does not need to inspect every character of the string to perform pattern match operations. The analysis shows that the number of characters to be inspected decreases as the length of patterns increases, and increases slightly as the total number of patterns increases. To match an eight-character pattern in an English string using the algorithm, only about 17% of all characters of the strong and 33% of all characters of the string, when the number of patterns is seven, are inspected. In an actual testing, the algorithm running on SUN 3/160 takes only 3.7 s to search seven eight-character patterns in a 1.4-Mbyte English text file 相似文献
19.
20.
一种改进的字符串模式匹配算法 总被引:1,自引:0,他引:1
提出一种改进的字符串模式匹配算法。该算法对文本串进行预处理,即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记,再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数。发生匹配失败时,将模式串直接滑动到标记了的出现次数最少的字符处。通过实验证明,该算法的移动次数和比较次数有较大减少,耗费的额外空间的大小也不超过模式串的长度,进一步提高模式匹配的效率。 相似文献