Please use this identifier to cite or link to this item:
https://doi.org/10.1007/s00453-008-9263-2
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. 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) | URI: | http://scholarbank.nus.edu.sg/handle/10635/38987 | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.