Please use this identifier to cite or link to this item:
Title: Compressed indexes for approximate string matching
Authors: Chan, H.-L.
Lam, T.-W.
Sung, W.-K. 
Tam, S.-L.
Wong, S.-S. 
Keywords: Approximate string matching
Compressed index
Issue Date: 2010
Citation: Chan, H.-L., Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, S.-S. (2010). Compressed indexes for approximate string matching. Algorithmica (New York) 58 (2) : 263-281. ScholarBank@NUS Repository.
Abstract: We revisit the problem of indexing a string S[1..n] to support finding 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, 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∈nlog∈log∈n) time. The previously best solution achieving this time complexity requires an index of O(nlog∈n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog∈nlog∈log∈n+occ) time, and k-error matching, for any k>2, in O(m k-1log∈nlog∈log∈n+occ) time. © 2008 Springer Science+Business Media, LLC.
Source Title: Algorithmica (New York)
ISSN: 01784617
DOI: 10.1007/s00453-008-9263-2
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 20, 2019


checked on Feb 20, 2019

Page view(s)

checked on Jan 13, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.