PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Belazzougui D., Venturini R. Compressed String Dictionary Look-up with Edit Distance One. In: CPM 2012 - 23rd Annual Symposium on Combinatorial Pattern Matching (Helsinky, 1 Giugno 2012). Proceedings, pp. 280 - 292. Kärkkäinen, Juha and Stoye, Jens (eds.). (Lecture Notes in Computer Science, vol. 7354). Springer New York, 2012.
 
 
Abstract
(English)
In this paper we present di erent solutions for the problem of indexing a dictionary of strings in compressed space. Given a pattern P, the index has to report all the strings in the dictionary having edit distance at most one with P. Our rst solution is able to solve queries in (almost optimal) O(|P|+occ) time where occ is the number of strings in the dictionary having edit distance at most one with P. The space complexity of this solution is bounded in terms of the k-th order entropy of the indexed dictionary. Our second solution further improves this space complexity at the cost of increasing the query time
DOI: 10.1007/978-3-642-31265-6_23
Subject Compressed Data Structures
E.1 DATA STRUCTURES


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional