PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Belazzougui D., Venturini R. Compressed string dictionary search with edit distance one. In: Algorithmica, vol. 74 (3) pp. 1099 - 1122. Springer, 2016.
 
 
Abstract
(English)
In this paper we present different 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 first 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. A second solution further improves this space complexity at the cost of increasing the query time. Finally, we propose randomized solutions (Monte Carlo and Las Vegas) which achieve simultaneously the time complexity of the first solution and the space complexity of the second one.
URL: http://link.springer.com/article/10.1007/s00453-015-9990-0
DOI: 10.1007/s00453-015-9990-0
Subject Compressed data structure
Pattern matching
Approximate search
H.3.3 INFORMATION STORAGE AND RETRIEVAL. Information Search and Retrieval


Icona documento 1) 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