Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Algorithms on Extended (δ, γ)-Matching
verfasst von : Inbok Lee, Raphaël Clifford, Sung-Ryul Kim
Erschienen in: Computational Science and Its Applications - ICCSA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.