We consider the problem of fingerprinting text by sets of symbols. Specifically, if S is a string, of length n, over a finite, ordered alphabet Σ, and S' is a substring of S, then the fingerprint of S' is the...
详细信息
The Pattern Matching problem with Swaps consists in finding all occurrences of a, pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one...
详细信息
ISBN:
(纸本)9783540958901
The Pattern Matching problem with Swaps consists in finding all occurrences of a, pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper, we present a new approach for solving both the Swap Matching problem and the Approximate Swap Matching problem in linear time, in the case of short, patterns. In particular, we devise a O(nm) general algorithm, named CROSS-SAMPLINGING, and show an efficient implementation of it, based on bit-parallelism, which achieves O(n) worst-case time and O(sigma)-space complexity, with patterns whose length is comparable to the word-size of the target machine.
作者：
Faro, SimoneUniv Catania
Dipartimento Matemat & Informat Viale Andrea Doria 6 I-95125 Catania Italy
The pattern matching problem with swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In this paper we introduce a new theoretical approach to th...
详细信息
ISBN:
(纸本)9788001053300
The pattern matching problem with swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In this paper we introduce a new theoretical approach to the problem based on a reactive automaton modeled after the pattern, and provide two efficient non standard simulations of the automaton, based on bit-parallelism. The first simulation can be implemented by at least 7 bitwise operations, while the second one involves only 2 bitwise operations to simulate the automaton behavior, when the input pattern satisfies particular conditions. The resulting algorithms achieve O(n) worst-case time complexity with patterns whose length is comparable to the word-size of the target machine.
The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text;T, when disjoint local swaps in the pattern are allowed. In this paper, we present a new efficient algorithm for the...
详细信息
ISBN:
(纸本)9783642102165
The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text;T, when disjoint local swaps in the pattern are allowed. In this paper, we present a new efficient algorithm for the Swap Matching problem with short patterns. In particular, we devise a O(nm(2)) general algorithm, named BACKWARD-CROSS-SAMPLING, and show an efficient implementation of it, based on bit-parallelism, which achieves O(nm) worst-case time and O(sigma)-space complexity, with patterns whose length m is comparable to the word-size of the target machine (n and sigma are respectively the size of the text and of the alphabet). From an extensive comparison with some of the most recent and effective algorithms for the swap matching problem, it turns out that our algorithm is very flexible and achieves very good results in practice.
暂无评论