Contributo in atti di convegno, 2012, ENG, 10.1007/978-3-642-31265-6_23

Compressed String Dictionary Look-up with Edit Distance One

Belazzougui D., Venturini R.

LIAFA, University of Paris "Diderot", Paris, France; CNR-ISTI, Pisa

In this paper we present dierent 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

23rd Annual Symposium on Combinatorial Pattern Matching, pp. 280–292, Helsinky, 1 Giugno 2012

Keywords

Compressed Data Structures, DATA STRUCTURES

CNR authors

Venturini Rossano

CNR institutes

ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"

ID: 275991

Year: 2012

Type: Contributo in atti di convegno

Creation: 2014-01-08 18:53:07.000

Last update: 2015-02-23 09:49:54.000

External links

OAI-PMH: Dublin Core

OAI-PMH: Mods

OAI-PMH: RDF

DOI: 10.1007/978-3-642-31265-6_23

External IDs

CNR OAI-PMH: oai:it.cnr:prodotti:275991

DOI: 10.1007/978-3-642-31265-6_23

Scopus: 2-s2.0-84863109054

PUMA: 2012-A2-075