IEICE TRANSACTIONS on Fundamentals
Indexed Swap Matching for Short Patterns
Summary :
Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet. The Pattern Matching with Swaps problem is to find all occurrences of P in T if adjacent pattern characters can be swapped. 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 provide the first off-line solution for the swap matching problem and the approximate pattern matching problem with swaps. We present a new data-structure called a Swap-transforming Tree. And we give a precise upper-bond of the number of the swapped versions of a pattern. By using the swap-transforming tree, we can solve both problems in time O(λmlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E95-A No.1 pp.362-366
- Publication Date
- 2012/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E95.A.362
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hua ZHAO, Songfeng LU, "Indexed Swap Matching for Short Patterns" in IEICE TRANSACTIONS on Fundamentals,
vol. E95-A, no. 1, pp. 362-366, January 2012, doi: 10.1587/transfun.E95.A.362.
Abstract: Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet. The Pattern Matching with Swaps problem is to find all occurrences of P in T if adjacent pattern characters can be swapped. 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 provide the first off-line solution for the swap matching problem and the approximate pattern matching problem with swaps. We present a new data-structure called a Swap-transforming Tree. And we give a precise upper-bond of the number of the swapped versions of a pattern. By using the swap-transforming tree, we can solve both problems in time O(λmlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E95.A.362/_p
Copy
@ARTICLE{e95-a_1_362,
author={Hua ZHAO, Songfeng LU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Indexed Swap Matching for Short Patterns},
year={2012},
volume={E95-A},
number={1},
pages={362-366},
abstract={Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet. The Pattern Matching with Swaps problem is to find all occurrences of P in T if adjacent pattern characters can be swapped. 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 provide the first off-line solution for the swap matching problem and the approximate pattern matching problem with swaps. We present a new data-structure called a Swap-transforming Tree. And we give a precise upper-bond of the number of the swapped versions of a pattern. By using the swap-transforming tree, we can solve both problems in time O(λmlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.},
keywords={},
doi={10.1587/transfun.E95.A.362},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Indexed Swap Matching for Short Patterns
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 362
EP - 366
AU - Hua ZHAO
AU - Songfeng LU
PY - 2012
DO - 10.1587/transfun.E95.A.362
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E95-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2012
AB - Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet. The Pattern Matching with Swaps problem is to find all occurrences of P in T if adjacent pattern characters can be swapped. 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 provide the first off-line solution for the swap matching problem and the approximate pattern matching problem with swaps. We present a new data-structure called a Swap-transforming Tree. And we give a precise upper-bond of the number of the swapped versions of a pattern. By using the swap-transforming tree, we can solve both problems in time O(λmlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.
ER -
English
