| Title: |
Approximate string matching using compressed suffix arrays |
| Authors: |
Huynh, TND; Hon, WK; Lam, TW; Sung, WK |
| Publisher Information: |
//www.elsevier.com/locate/tcs; Netherlands |
| Publication Year: |
2006 |
| Collection: |
University of Hong Kong: HKU Scholars Hub |
| Description: |
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. ; link_to_subscribed_fulltext |
| Document Type: |
article in journal/newspaper |
| Language: |
English |
| Relation: |
Theoretical Computer Science; http://www.scopus.com/mlt/select.url?eid=2-s2.0-32644436921&selection=ref&src=s&origin=recordpage; 249; 130777; WOS:000235826900018; 240; https://hub.hku.hk/handle/10722/152330; 352 |
| DOI: |
10.1016/j.tcs.2005.11.022 |
| Availability: |
https://hub.hku.hk/handle/10722/152330; https://doi.org/10.1016/j.tcs.2005.11.022 |
| Accession Number: |
edsbas.E3CB4AF |
| Database: |
BASE |