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

Space-efficient construction of LZ-index

Artículo
Thumbnail
Open/Download
IconArroyuelo D.pdf (269.4Kb)
Publication date
2005
Metadata
Show full item record
Cómo citar
Arroyuelo Billiardi, Diego
Cómo citar
Space-efficient construction of LZ-index
.
Copiar
Cerrar

Author
  • Arroyuelo Billiardi, Diego;
  • Navarro, Gonzalo;
Abstract
A compressed full-text self-index is a data structure that replaces a text and in addition gives indexed access to it, while taking space proportional to the compressed text size. The LZ-index, in particular, requires 4uH(k)(1 + o(1)) bits of space, where u is the text length in characters and H-k is its k-th order empirical entropy, Although in practice the LZ-index needs 1.0-1.5 times the text size, its construction requires Much more main memory (around 5 times the text size), which limits its applicability to large texts. In this paper we present a practical space-efficient algorithm to construct LZ-index, requiring (4 + is an element of)uH(k) + o(u) bits of space, for any constant 0 < epsilon < 1, and O(sigma u) time, being sigma the alphabet size. Our experimental results show that our method is efficient in practice, needing an amount of memory close to that of the final index.
Identifier
URI: https://repositorio.uchile.cl/handle/2250/124504
ISSN: 0302-9743
Quote Item
ALGORITHMS AND COMPUTATION LECTURE NOTES IN COMPUTER SCIENCE 3827: 1143-1152 2005
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