Advertisement
Published in:
2006 | OriginalPaper | Chapter
Compressed Indexes for Approximate String Matching
Authors : Ho-Leung Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, Swee-Seong Wong
Published in: Algorithms – ESA 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.