Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Compressed Indexes for Approximate String Matching
verfasst von : Ho-Leung Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, Swee-Seong Wong
Erschienen in: Algorithms – ESA 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
We revisit the problem of indexing a string
S
[1..
n
] to support searching all substrings in
S
that match a given pattern
P
[1..
m
] with at most
k
errors. Previous solutions either require an index of size exponential in
k
or need Ω(
m
k
) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only
O
(
n
) space. For
k
= 1, we give an index to support matching in
O
(
m
+
occ
+ log
n
loglog
n
) time. The previously best solution achieving this time complexity requires an index of size
O
(
n
log
n
). This new index can be used to improve existing indexes for
k
≥2 errors. Among others, it can support matching with
k
=2 errors in
O
(
m
log
n
loglog
n
+
occ
) time.