Please use this identifier to cite or link to this item:
|Title:||Compressed indexes for approximate string matching|
|Citation:||Chan, H.-L.,Lam, T.-W.,Sung, W.-K.,Tam, S.-L.,Wong, S.-S. (2006). Compressed indexes for approximate string matching. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4168 LNCS : 208-219. ScholarBank@NUS Repository.|
|Abstract:||We revisit the problem of indexing a string 5[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+lognloglogn) 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 log log n + occ) time. © Springer-Verlag Berlin Heidelberg 2006.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 22, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.