Abstract
Approximate pattern matching plays an important role in various applications, such as bioinformatics, computer-aided music analysis and computer vision. We focus on (δ, γ)-matching. Given a text T of length n, a pattern P of length m,and two parameters δ and γ, the aim is to find all the substring T[i, i+m–1] such that (a) ∀ 1 ≤ j ≤ m, |T[i+j–1] – P[j]| ≤ δ (δ-matching) , and (b) ∑1 ≤ j ≤ m |T[i+j–1] – P[j]| ≤ γ (γ-matching). In this paper we consider three variations of (δ, γ)-matching: amplified matching, transposition-invariant matching, and amplified transposition-invariant matching. For each problem we propose a simple and efficient algorithm which is easy to implement.
This research was supported by the MIC(Ministry of Information and Communication), Korea, under the ITRC(Information Technology Research Center) support program supervised by the IITA(Institute of Information Technology Assessment).
| Translated title of the contribution | Algorithms on Extended (delta, gamma)-Matching |
|---|---|
| Original language | English |
| Title of host publication | Computational Science and Its Applications - ICCSA 2006 |
| Subtitle of host publication | International Conference, Glasgow, UK, May 8-11, 2006. Proceedings, Part II |
| Publisher | Springer |
| Pages | 1137-1142 |
| Number of pages | 6 |
| ISBN (Electronic) | 9783540340744 |
| ISBN (Print) | 9783540340720 |
| DOIs | |
| Publication status | Published - 2006 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 3981 |
| ISSN (Print) | 0302-9743 |
Bibliographical note
ISBN: 03029743Publisher: Springer Berlin/Heidelberg
Name and Venue of Conference: International Conference on Computational Science and its Applications (ICCSA 2006)
Other identifier: 2000603