About
Contact
Help
Sending publications
How to publish
Advanced Search
View Item 
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse byCommunities and CollectionsDateAuthorsTitlesSubjectsThis CollectionDateAuthorsTitlesSubjects

My Account

Login to my accountRegister
Biblioteca Digital - Universidad de Chile
Revistas Chilenas
Repositorios Latinoamericanos
Tesis LatinoAmericanas
Tesis chilenas
Related linksRegistry of Open Access RepositoriesOpenDOARGoogle scholarCOREBASE
My Account
Login to my accountRegister

Statistical encoding of succinct data structures

Artículo
Thumbnail
Open/Download
IconGonzalez_Rodrigo.pdf (506.1Kb)
Publication date
2006
Metadata
Show full item record
Cómo citar
González González, Rodrigo
Cómo citar
Statistical encoding of succinct data structures
.
Copiar
Cerrar

Author
  • González González, Rodrigo;
  • Navarro, Gonzalo;
Abstract
In recent work, Sadakane and Grossi [SODA 2006] introduced a scheme to represent any sequence S = s(1)s(2)...s(n), over an alphabet of size sigma, using nH(k)(S) + O(log(sigma)n/n (k log sigma + log log n)) bits of space, log, n where H-k(S) is the k-th order empirical entropy of S. The representation permits extracting any substring of size Theta(log(sigma) n) in constant time, and thus it completely replaces S under the RAM model. This is extremely important because it permits converting any succinct data structure requiring o(vertical bar S vertical bar) = o(n log sigma) bits in addition to S, into another requiring nH(k)(S) + o(n log sigma) (overall) for any k = o(log(sigma) n). They achieve this result by using Ziv-Lempel compression, and. conjecture that the result can in particular be useful to implement compressed full-text indexes. In this paper we extend their result, by obtaining the same space and time complexities using a simpler scheme based on statistical encoding. We show that the scheme supports appending symbols in constant amortized time. In addition, we prove some results on the applicability of the scheme for full-text self-indexing.
Identifier
URI: https://repositorio.uchile.cl/handle/2250/124879
ISSN: 0302-9743
Quote Item
COMBINATORIAL PATTERN MATCHING, PROCEEDINGS Book Series: LECTURE NOTES IN COMPUTER SCIENCE Volume: 4009 Pages: 294-305 Published: 2006
Collections
  • Artículos de revistas
xmlui.footer.title
31 participating institutions
More than 73,000 publications
More than 110,000 topics
More than 75,000 authors
Published in the repository
  • How to publish
  • Definitions
  • Copyright
  • Frequent questions
Documents
  • Dating Guide
  • Thesis authorization
  • Document authorization
  • How to prepare a thesis (PDF)
Services
  • Digital library
  • Chilean academic journals portal
  • Latin American Repository Network
  • Latin American theses
  • Chilean theses
Dirección de Servicios de Información y Bibliotecas (SISIB)
Universidad de Chile

© 2020 DSpace
  • Access my account