Please use this identifier to cite or link to this item:
|Title:||Compressed indexes for approximate string matching|
|Keywords:||Approximate string matching|
|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. https://doi.org/10.1007/s00453-008-9263-2|
|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)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 12, 2018
WEB OF SCIENCETM
checked on Sep 4, 2018
checked on Jun 30, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.