Please use this identifier to cite or link to this item:
|Title:||Improved approximate string matching using compressed suffix data structures||Authors:||Lam, T.-W.
|Issue Date:||2005||Citation:||Lam, T.-W.,Sung, W.-K.,Wong, S.-S. (2005). Improved approximate string matching using compressed suffix data structures. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3827 LNCS : 339-348. ScholarBank@NUS Repository. https://doi.org/10.1007/11602613_35||Abstract:||Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over a fixed alphabet A, we can preprocess T and give an O(n√log n)-bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(m log log n +occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(n log 2 n) bits. The space of our data structure can be further reduced to O(n) if we can afford a slow down factor of log εn, for 0 < ε ≤ 1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A| km k(k + log log n) + occ) and O(log ε n(|A| km k(k + log log n) + occ)) query time using an O(n√log n)-bit and an O(n)-bit indexing data structures, respectively. © Springer-Verlag Berlin Heidelberg 2005.||Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)||URI:||http://scholarbank.nus.edu.sg/handle/10635/41170||ISBN:||3540309357||ISSN:||03029743||DOI:||10.1007/11602613_35|
|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.