A simple storage scheme for strings achieving entropy bounds
DOI10.1016/J.TCS.2006.12.012zbMATH Open1110.68029OpenAlexW4240576586MaRDI QIDQ870846FDOQ870846
Authors: Paolo Ferragina, Rossano Venturini 
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
Recommendations
- A simple storage scheme for strings achieving entropy bounds
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- On the complexity of random strings
- Succinct randomized encodings and their applications
- An upper bound on the entropy of run-length coding (Corresp.)
- Simple Compression Code Supporting Random Access and Fast String Matching
- Random access to high-order entropy compressed text
- Limits on the computational power of random strings
- Limits on the Computational Power of Random Strings
Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- An analysis of the Burrows-Wheeler transform
- Indexing compressed text
- Compression of individual sequences via variable-rate coding
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Title not available (Why is that?)
- Succinct indexes for strings, binary relations and multi-labeled trees
- Title not available (Why is that?)
- Squeezing succinct data structures into entropy bounds
- New text indexing functionalities of the compressed suffix arrays
- Ultra-succinct representation of ordered trees
- Boosting textual compression in optimal linear time
- Optimal Lower Bounds for Rank and Select Indexes
Cited In (35)
- Fast compressed self-indexes with deterministic linear-time construction
- Optimal indexes for sparse bit vectors
- Robust transmission of unbounded strings using Fibonacci representations
- Colored range queries and document retrieval
- Ultra-succinct representation of ordered trees with applications
- Block trees
- Fast entropy-bounded string dictionary look-up with mismatches
- Access, rank, and select in grammar-compressed strings
- Compressed string dictionary search with edit distance one
- Bounds from a card trick
- Efficient fully-compressed sequence representations
- A space efficient direct access data structure
- Compressing dictionary matching index via sparsification technique
- Succinct 2D dictionary matching
- A simple storage scheme for strings achieving entropy bounds
- Dynamic rank/select structures with applications to run-length encoded texts
- Rank/select on dynamic compressed sequences and applications
- Rank and select revisited and extended
- Wee LCP
- Fast string dictionary lookup with one error
- Random access to high-order entropy compressed text
- On compact representations of all-pairs-shortest-path-distance matrices
- A framework for succinct labeled ordinal trees over large alphabets
- Can we locally compute sparse connected subgraphs?
- Range majorities and minorities in arrays
- Title not available (Why is that?)
- Accelerated partial decoding in wavelet trees
- Compressed dynamic range majority and minority data structures
- Compressed text indexing with wildcards
- On representing the degree sequences of sublogarithmic-degree Wheeler graphs
- Title not available (Why is that?)
- Succinct data structures for nearest colored node in a tree
- Dynamic relative compression, dynamic partial sums, and substring concatenation
- Path queries on functions
- Random access in persistent strings and segment selection
This page was built for publication: A simple storage scheme for strings achieving entropy bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870846)
