A simple storage scheme for strings achieving entropy bounds

DOI10.1016/j.tcs.2006.12.012zbMath1110.68029OpenAlexW4240576586MaRDI QIDQ870846

Rossano Venturini, Paolo Ferragina

Publication date: 15 March 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://eprints.adm.unipi.it/2162/1/TR%2D06%2D09.pdf.gz

zbMATH Keywords

data compressiondata structures for strings

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (33)

Compressed string dictionary search with edit distance one ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Succinct 2D dictionary matching ⋮ A space efficient direct access data structure ⋮ Can we locally compute sparse connected subgraphs? ⋮ Fast String Dictionary Lookup with One Error ⋮ Compressed dynamic range majority and minority data structures ⋮ Colored range queries and document retrieval ⋮ On representing the degree sequences of sublogarithmic-degree Wheeler graphs ⋮ Ultra-succinct representation of ordered trees with applications ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Compressed text indexing with wildcards ⋮ Succinct data structures for nearest colored node in a tree ⋮ Unnamed Item ⋮ Block trees ⋮ Efficient fully-compressed sequence representations ⋮ Optimal indexes for sparse bit vectors ⋮ A framework for succinct labeled ordinal trees over large alphabets ⋮ Path queries on functions ⋮ Rank and select revisited and extended ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Unnamed Item ⋮ Wee LCP ⋮ Range majorities and minorities in arrays ⋮ Dynamic rank/select structures with applications to run-length encoded texts ⋮ Rank/select on dynamic compressed sequences and applications ⋮ Accelerated partial decoding in wavelet trees ⋮ Fast and compact planar embeddings ⋮ Random Access to High-Order Entropy Compressed Text ⋮ Compressing dictionary matching index via sparsification technique

Cites Work

• An analysis of the Burrows—Wheeler transform
• Boosting textual compression in optimal linear time
• Indexing compressed text
• Squeezing succinct data structures into entropy bounds
• Optimal Lower Bounds for Rank and Select Indexes
• Compression of individual sequences via variable-rate coding
• New text indexing functionalities of the compressed suffix arrays
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A simple storage scheme for strings achieving entropy bounds