Please use this identifier to cite or link to this item:
|Title:||A linear size index for approximate pattern matching|
|Keywords:||Approximate pattern matching|
Full text indexing
Indexing with errors
|Source:||Chan, H.-L.,Lam, T.-W.,Sung, W.-K.,Tam, S.-L.,Wong, S.-S. (2011). A linear size index for approximate pattern matching. Journal of Discrete Algorithms 9 (4) : 358-364. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jda.2011.04.004|
|Abstract:||This paper revisits the problem of indexing a text S[1.n] for pattern matching with up to k errors. A naive solution either has a worst-case matching time complexity of Ω(m k) or requires Ω(n k) space, where m is the length of the pattern. Devising a solution with better performance has been a challenge until Cole et al. (2004)  showed an O(n log kn)-space index that can support k-error matching in O(m + occ + log knloglogn) time, where occ is the number of occurrences. Motivated by the indexing of long sequences like DNA, we have investigated the feasibility of devising a linear-size index that still has a time complexity linear in pattern length. This paper in particular presents an O(n)-space index that supports k-error matching in O(m+occ+(logn) k(k+1)loglogn) worst-case time. This index can be further compressed from O(n) words into O(n) bits with a slight increase in the time complexity. © 2011 Elsevier B.V. All rights reserved.|
|Source Title:||Journal of Discrete Algorithms|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 11, 2017
checked on Dec 16, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.