We explore the benefits of parallelizing 7 state-of-the-art string matching algorithms. Using SIMD and multi-threading techniques we achieve a significant performance improvement of up to 43.3x over reference implemen...
详细信息
ISBN:
(纸本)9783319589435;9783319589428
We explore the benefits of parallelizing 7 state-of-the-art string matching algorithms. Using SIMD and multi-threading techniques we achieve a significant performance improvement of up to 43.3x over reference implementations and a speedup of up to 16.7x over the string matching program grep. We evaluate our implementations on the smart-corpora and the full human genome data set. We show scalability over number of threads and impact of pattern length.
We use a simple observation about the locations of critical factorizations to derive a real-time variation of the Crochemore-Perrin constant-space string matching algorithm. The real-time variation has a simple and ef...
详细信息
ISBN:
(纸本)9783642214585
We use a simple observation about the locations of critical factorizations to derive a real-time variation of the Crochemore-Perrin constant-space string matching algorithm. The real-time variation has a simple and efficient control structure.
This paper presents a taxonomy of some exact, right-to-left, string-matching algorithms. The taxonomy is based on results obtained by using logic program transformation over a naive and nondeterministic specification....
详细信息
ISBN:
(纸本)9783642119989
This paper presents a taxonomy of some exact, right-to-left, string-matching algorithms. The taxonomy is based on results obtained by using logic program transformation over a naive and nondeterministic specification. A derivation of the search part and some notes about the preprocessing part of each algorithm is presented. The derivations show several design decisions behind each algorithm, and allow us to organize the algorithms within a taxonomic tree, giving us a better understanding of these algorithms and possible mechanical procedures to derive them.
string matching is a fundamental problem in algorithm. This study examines the development and construction of two reversible string-matching algorithms: a naive string-matching algorithm and the Rabin-Karp algorithm....
详细信息
string matching is a fundamental problem in algorithm. This study examines the development and construction of two reversible string-matching algorithms: a naive string-matching algorithm and the Rabin-Karp algorithm. The algorithms are used to introduce reversible computing concepts, beginning from basic reversible programming techniques to more advanced considerations about the injectivization of the polynomial hash-update function employed by the Rabin-Karp algorithm. The results are two clean input-preserving reversible algorithms that require no additional space and have the same asymptotic time complexity as their classic irreversible originals. This study aims to contribute to the body of reversible algorithms and to the discipline of reversible programming.
This paper presents a real-time randomized streaming string matching algorithm that uses O(log m) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrenc...
详细信息
ISBN:
(纸本)9783642214585
This paper presents a real-time randomized streaming string matching algorithm that uses O(log m) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the pattern, but never misses an actual occurrence.
The Internet is suffering caused by the lacking of security. One of the most promising ways to provide security is Intrusion Detection Systems (IDSs). The heart of almost every IDSs is a string matching algorithm, whi...
详细信息
ISBN:
(纸本)9781424419678
The Internet is suffering caused by the lacking of security. One of the most promising ways to provide security is Intrusion Detection Systems (IDSs). The heart of almost every IDSs is a string matching algorithm, which is a very computational intensive task. Network Processors (NPs), a specialized multiprocessor, can provide flexibility and high performance for string matching. This paper evaluates several key string matching algorithms using a comprehensive simulation framework. Starting from a uniprocessor profiling, the framework constructs task graphs for string matching algorithms. Then task graphs are mapped onto NPs together with other network applications. The system throughput is determined by the analytical performance model. With this framework, we can evaluate the performance of different string matching algorithms on NPs. Our results show that shift table based algorithms (SFKSearch and Wu-Manber) and finite automaton based Aho-Corasick are complementary: SFKSearch and Wu-Manber do better job in NPs for good packet and larger pattern length due to better inter-task parallelism and shifting;Aho-Corasick does not depend on minimal pattern length and shows relative small processing cost variation between bad and good packets.
stringsearching is at the core of many security and network applications like search engines, intrusion detection systems, virus scanners and spam filters. The growing size of on-line content and the increasing wire ...
详细信息
string or pattern matching is an essential part of most computer applications that are widely used in text processors, Internet-based search engines and computer security. A key concept of string matching is identifyi...
详细信息
In this paper we show that combining some of the good features of the existing popular algorithms can be even more efficient. This new algorithm is hybrid as it employs features from Boyer-Moore-Horspool, Rabin-Karp a...
详细信息
There are numerous exact string matching algorithms that have similar performance characteristics. Which algorithm is best depends on the length of the pattern being searched for, the number of letters in the alphabet...
详细信息
暂无评论