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|
|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|
|Number of pages||6|
|Publication status||Published - 2006|
|Name||Lecture Notes in Computer Science|
Bibliographical noteISBN: 03029743
Publisher: Springer Berlin/Heidelberg
Name and Venue of Conference: International Conference on Computational Science and its Applications (ICCSA 2006)
Other identifier: 2000603