Compressed String Dictionary Look-up with Edit Distance One (Contributo in atti di convegno)

Type
Label
  • Compressed String Dictionary Look-up with Edit Distance One (Contributo in atti di convegno) (literal)
Anno
  • 2012-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1007/978-3-642-31265-6_23 (literal)
Alternative label
  • Belazzougui D., Venturini R. (2012)
    Compressed String Dictionary Look-up with Edit Distance One
    in 23rd Annual Symposium on Combinatorial Pattern Matching, Helsinky, 1 Giugno 2012
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Belazzougui D., Venturini R. (literal)
Pagina inizio
  • 280 (literal)
Pagina fine
  • 292 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#titoloVolume
  • Lecture Notes in Computer Science (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#volumeInCollana
  • 7354 (literal)
Note
  • PuMa (literal)
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • LIAFA, University of Paris \"Diderot\", Paris, France; CNR-ISTI, Pisa (literal)
Titolo
  • Compressed String Dictionary Look-up with Edit Distance One (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn
  • 978-3-642-31264-9 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#curatoriVolume
  • K?§rkk?§inen, Juha and Stoye, Jens (literal)
Abstract
  • 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 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 (literal)
Editore
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Editore di
Insieme di parole chiave di
data.CNR.it