检索结果-内蒙古大学图书馆

An aggressive algorithm for multiple string matching

INFORMATION PROCESSING LETTERS 2009年第11期109卷 553-559页

作者： Dai, Liuling Beijing Inst Technol Sch Comp Sci Beijing Lab Intelligent Informat Technol Beijing 100081 Peoples R China

A new algorithm based on the Wu-Manber algorithm for multiple string matching is presented in this paper. The algorithm eliminates the functional overlap of the table HASH and SHIFT, and computes the shift distances in an aggressive manner. After each test, the algorithm examines the character next to the scan window to maximize the shift distance. This idea is consistent with that of the quick-search (QS) algorithm. Experimental results on four alphabets show that the new algorithm is more efficient than Wu-Manber and other recent algorithms, particularly on short pattern sets and large alphabet. (C) 2009 Elsevier B.V. All rights reserved.

关键词： string matching multiple string matching Wu-Manber algorithm Design of algorithms

来源：评论

学校读者我要写书评

暂无评论

Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm

引用

Science China(Information Sciences) 2011年第8期54卷 1562-1571页

作者： HU Yue 1,2, GAO QingShi 1,2 ,GUO Li 2 & WANG PeiFeng 1 1 School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China 2 Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China 1. School of Information Engineering University of Science and Technology Beijing Beijing 100083 China2. Institute of Computing Technology Chinese Academy of Sciences Beijing 100190 China

multiple string matching is often completed under the presence of U- or V-uncertain-strings,or combinations *** large numbers of strings with U-, V-,and U-V-uncertain-strings,including the interleaving of two or more uncertain strings,is important to thoroughly gathering useful information and detecting harmful *** paper proposes a complete automaton and its high-speed construction algorithm for large-scale U-, V-,and U-V-uncertain multiple strings,including two or more uncertain strings interlaced with one *** maximum number of parallel complete automation of the V-uncertain string is also *** paper reveals that there are two kinds of pretermissions,i.e.,similarly-connected and interlaced-string pretermissions,and that mistake may appear in the matching of the regular expressions,or states in the automaton may increase in number,if the intersection of the U-uncertain strings sets and the homologous subsequent special point in the U-uncertain strings sets are not eliminated from the whole system.

关键词： multiple string matching U-uncertain-strings V-uncertain-strings U-V-uncertain-strings complete automaton

来源：评论

学校读者我要写书评

暂无评论

A space efficient bit-parallel algorithm for the multiple string matching problem

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2006年第6期17卷 1235-1251页

作者： Cantone, Domenico Faro, Simone Univ Catania Dipartimento Matemat & Informat San Jose CA 95125 USA

Finite (nondeterministic) automata are very useful building blocks in the field of string matching. This is particularly true in the case of multiple pattern matching, where the use of factor-based automata can reduce substantially the number of computational steps when the patterns have large common factors. Direct simulation of nondeterministic automata can be performed very efficiently using the bit-parallelism technique, though this is not necessarily true for factor-based automata. In this paper we present an algorithm for the multiple string matching problem, based on the bit-parallel simulation of nondeterministic factor-based automata which satisfy a particular ordering condition. We also show how to enforce such condition by suitably modifying a minimal initial automaton, through equivalence preserving transformations. The resulting automaton turns out to be smaller than the corresponding maximal automata used by existing bit-parallel algorithms, as they do not take any advantage of common factors in patterns.

关键词： multiple string matching bit-parallelism text searching

来源：评论

学校读者我要写书评

暂无评论

A Factor-searching-based multiple string matching Algorithm for Intrusion Detection

A Factor-searching-based Multiple String Matching Algorithm ...

引用

IEEE International Conference on Communications (ICC)

作者： Liu, Yanbing Liu, Qingyun Liu, Ping Tan, Jianlong Guo, Li Chinese Acad Sci Inst Informat Engn Beijing Peoples R China

ISBN: (纸本)9781479920037

multiple string matching plays a fundamental role in network intrusion detection systems. Automata-based multiple string matching algorithms like AC, SBDM and SBOM are widely used in practice, but the huge memory usage of automata prevents them from being applied to a large-scale pattern set. Meanwhile, poor cache locality of huge automata degrades the matching speed of algorithms. Here we propose a space-efficient multiple string matching algorithm BVM, which makes use of bit-vector and succinct hash table to replace the automata used in factor-searching-based algorithms. Space complexity of the proposed algorithm is O(rm(2) + Sigma(p is an element of P)|p|), that is more spaceefficient than the classic automata-based algorithms. Experiments on datasets including Snort, ClamAV, URL blacklist and synthetic rules show that the proposed algorithm significantly reduces memory usage and still runs at a fast matching speed. Above all, BVM costs less than 0.75% of the memory usage of AC, and is capable of matching millions of patterns efficiently.

关键词： intrusion detection multiple string matching automata space-efficient

来源：评论

学校读者我要写书评

暂无评论

A space efficient bit-parallel algorithm for the multiple string matching problem

A space efficient bit-parallel algorithm for the multiple st...

引用

Prague stringology Conference 2005

作者： Cantone, Domenico Faro, Simone Univ Catania Dipartimento Matemat & Informat San Jose CA 95125 USA

ISBN: (纸本)8001033074

关键词： multiple string matching bit-parallelism text searching

来源：评论

学校读者我要写书评

暂无评论

Towards a Very Fast multiple string matching Algorithm for Short Patterns

Towards a Very Fast Multiple String Matching Algorithm for S...

引用

8th Prague stringology Conference (PSC)

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat I-95124 Catania Italy TUBTAK Natl Res Inst Elect & Cryptol Gebze Turkey

ISBN: (纸本)9788001053300

multiple exact string matching is one of the fundamental problems in computer science and finds applications in many other fields, among which computational biology and intrusion detection. It turns out that short patterns appear in many instances of such problems and, in most cases, sensibly affect the performances of the algorithms. Recent solutions in the field of string matching try to exploit the power of the word RAM model to speed-up the performances of classical algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. This study presents a first preliminary attempt to develop a filter based exact multiple string matching algorithm for searching set of short patterns by taking benefit from Intel's SSE (streaming SIMD extensions) technology. Our experimental results on small, medium, and large alphabet text files show that the proposed algorithm is competitive in the case of short patterns against other efficient solutions, which are known to be among the fastest in practice.

关键词： multiple string matching experimental algorithms text-processing short patterns Streaming SIMD Extensions Technology SSE

来源：评论

学校读者我要写书评

暂无评论

A Parallel Algorithm of multiple string matching Based on Set-Partition in Multi-core Architecture

引用

INTERNATIONAL JOURNAL OF SECURITY AND ITS APPLICATIONS 2016年第4期10卷 267-278页

作者： Liu, Jiahui Li, Fangzhou Sun, Guanglu Harbin Univ Sci & Technol Coll Comp Sci & Technol Harbin Peoples R China Harbin Inst Technol Sch Comp Sci & Technol Harbin Peoples R China

With the coming of the big data era, the data processing in large scale comes out with a new challenge. However, string matching still plays an important role in the network security and information retrieval fields, because of the large size of pattern set with the overhead of memory and access memory time. Improving the string matching algorithm to adapt to the large scale tasks is desirable and meaningful. In this paper, we present and implement a parallel algorithm of multiple string matching based on multi-core platform. In addition, this work focuses on the partition of pattern set by using genetic algorithm through the internal relation of the patterns to reduce the memory overhead and execution performance. Compared with the classical ones, our experiments on both high and low hit-rate data demonstrate that the performance of algorithm enhances about on average by 20%-40% in general. Besides, the proposed algorithm reduces the memory cost on average by 4%-20%.

关键词： Parallel multiple string matching multi-core genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Increased bit-parallelism for approximate and multiple string matching

引用

ACM Journal of Experimental Algorithmics 2005年 10卷 2.6–es页

作者： Hyyrö, Heikki Fredriksson, Kimmo Navarro, Gonzalo University of Joensuu Finland Department of Computer Sciences University of Tampere Kanslerinrinne 1 FIN-33014 Finland Department of Computer Science and Statistics P.O. Box 111 Joensuu FI-80101 Finland Department of Computer Science University of Chile Blanco Encalada 2120 Santiago Chile

Bit-parallelism permits executing several operations simultaneously over a set of bits or numbers stored in a single computer word. This technique permits searching for the approximate occurrences of a pattern of length m in a text of length n in time O(⌈m/w⌉n), where w is the number of bits in the computer word. Although this is asymptotically the optimal bit-parallel speedup over the basic O(mn) time algorithm, it wastes bit-parallelism's power in the common case where m is much smaller than w, since w - m bits in the computer words are unused. In this paper, we explore different ways to increase the bit-parallelism when the search pattern is short. First, we show how multiple patterns can be packed into a single computer word so as to search for all them simultaneously. Instead of spending O(rn) time to search for r patterns of length m ≤ w/2, we need O(⌈rm/w⌉n) time. Second, we show how the mechanism permits boosting the search for a single pattern of length m ≤ w/2, which can be searched for in O(⌈n/⌊w/m⌋⌉) bit-parallel steps instead of O(n). Third, we show how to extend these algorithms so that the time bounds essentially depend on k instead of m, where k is the maximum number of differences permitted. Finally, we show how the ideas can be applied to other problems such as multiple exact string matching and one-against-all computation of edit distance and longest common subsequences. Our experimental results show that the new algorithms work well in practice, obtaining significant speedups over the best existing alternatives, especially on short patterns and moderate number of differences allowed. This work fills an important gap in the field, where little work has focused on very short patterns. © 2005 ACM.

关键词： Approximate string matching Bit-parallelism multiple string matching

来源：评论

学校读者我要写书评

暂无评论

The WM-q multiple exact string matching algorithm for DNA sequences

引用

COMPUTERS IN BIOLOGY AND MEDICINE 2021年 136卷 104656-104656页

作者： Karcioglu, Abdullah Ammar Bulut, Hasan Ege Univ Dept Comp Engn Izmir Turkey

The string matching algorithms are among the essential fields in computer science, such as text search, intrusion detection systems, fraud detection, sequence search in bioinformatics. The exact string matching algorithms are divided into two parts: single and multiple. multiple string matching algorithms involve finding elements of the pattern set P in a given input text T. string matching processes should be done in a time-efficient manner for DNA sequences. As the volume of the text T increases and the number of search patterns increases, the total runtime increases. Efficient algorithms should be selected to perform these search operations as soon as possible. In this study, the Wu-Manber algorithm, one of the multiple exact string matching algorithms, is improved. Although the Wu-Manber algorithm is effective, it has some limitations, such as hash collisions. In this study, the WM-q algorithm, a version of the Wu-Manber algorithm based on the perfect hash function for DNA sequences, is proposed. string matching is performed using different block lengths provided by the perfect hash function instead of using the fixed block length as in the traditional Wu-Manber algorithm. The proposed approach has been compared with E. Coli and Human Chromosome1 datasets, frequently used in the literature, using multiple exact string matching algorithms. The proposed algorithm gives better results for performance metrics such as the average runtime, the average number of characters and hash comparisons.

关键词： multiple string matching DNA Sequences Sequence analysis Hash function Wu manber algorithm

来源：评论

学校读者我要写书评

暂无评论

Average-optimal single and multiple approximate string matching

引用

ACM Journal of Experimental Algorithmics 2004年 9卷 1.4–es页

作者： Fredriksson, Kimmo Navarro, Gonzalo Department of Computer Science University of Joensuu P.O. Box 111 Joensuu FI- 80101 Finland Department of Computer Science University of Chile Blanco Encalada 2120 Santiago Chile

We present a new algorithm for multiple approximate string matching. It is based on reading backwards enough ℓ-grams from text windows so as to prove that no occurrence can contain the part of the window read, and then shifting the window. We show analytically that our algorithm is optimal on average. Hence our first contribution is to fill an important gap in the area, since no average-optimal algorithm existed for multiple approximate string matching. We consider several variants and practical improvements to our algorithm, and show experimentally that they are resistant to the number of patterns and the fastest for low difference ratios, displacing the long-standing best algorithms. Hence our second contribution is to give a practical algorithm for this problem, by far better than any existing alternative in many cases of interest. On real-life texts, our algorithm is especially interesting for computational biology applications. In particular, we show that our algorithm can be successfully used to search for one pattern, where many more competing algorithms exist. Our algorithm is also average-optimal in this case, being the second after that of Chang and Marr. However, our algorithm permits higher difference ratios than Chang and Marr, and this is our third contribution. In practice, our algorithm is competitive in this scenario too, being the fastest for low difference ratios and moderate alphabet sizes. This is our fourth contribution, which also answers affirmatively the question of whether a practical average-optimal approximate string-matching algorithm existed. © 2004 ACM.

关键词： Algorithms Approximate string matching Biological sequences F.2.2 [analysis of algorithms and problem complexity]: nonnumerical algorithms and problems-pattern matching, computations on discrete structures H.3.3 [information storage and retrieval]: information search and retrieval-search process multiple string matching Optimality Theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：