Please use this identifier to cite or link to this item:
Title: Approximate string matching using compressed suffix arrays
Authors: Huynh, T.N.D.
Hon, W.-K.
Lam, T.-W.
Sung, W.-K. 
Issue Date: 2006
Source: Huynh, T.N.D.,Hon, W.-K.,Lam, T.-W.,Sung, W.-K. (2006). Approximate string matching using compressed suffix arrays. Theoretical Computer Science 352 (1-3) : 240-249. ScholarBank@NUS Repository.
Abstract: Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k-difference (k-mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster. We give a solution using an O(nlogn) bits indexing data structure with O(|A|kmk·max(k,logn) +occ) query time, where occ is the number of occurrences. The best previous result requires O(nlogn) bits indexing data structure and gives O(|A|kmk+2+occ) query time. Our solution also allows us to exploit compressed suffix arrays to reduce the indexing space to O(n) bits, while increasing the query time by an O(logn) factor only. © 2005 Elsevier B.V. All right reserved.
Source Title: Theoretical Computer Science
ISSN: 03043975
DOI: 10.1016/j.tcs.2005.11.022
Appears in Collections:Staff Publications

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


checked on Dec 12, 2017

Page view(s)

checked on Dec 15, 2017

Google ScholarTM



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