Ultra-succinct representation of ordered trees with applications
From MaRDI portal
Publication:414928
DOI10.1016/j.jcss.2011.09.002zbMath1242.68083MaRDI QIDQ414928
Wing-Kin Sung, Jesper Jansson, Kunihiko Sadakane
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.09.002
05C05: Trees
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
Random Access to Grammar-Compressed Strings and Trees, Efficient computation of Lyapunov functions for Morse decompositions, Succinct dynamic cardinal trees, Simultaneous encodings for range and next/previous larger/smaller value queries, Compressed directed acyclic word graph with application in local alignment, Compact navigation and distance oracles for graphs with small treewidth, Simple and efficient fully-functional succinct trees, Lempel-Ziv factorization powered by space efficient suffix trees, Tree compression using string grammars, Improved range minimum queries, Parallel construction of succinct trees, Fully Functional Static and Dynamic Succinct Trees, Fast Compressed Tries through Path Decompositions, Succinct Representations of Ordinal Trees, Encoding range minima and range top-2 queries
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Representing trees of higher degree
- A simple optimal representation for balanced parentheses
- A simple storage scheme for strings achieving entropy bounds
- Binary trees having a given number of nodes with 0, 1, and 2 children
- Time-space trade-offs for compressed suffix arrays.
- Compressed suffix trees with full functionality
- Space Efficient Suffix Trees
- Low Redundancy in Static Dictionaries with Constant Query Time
- Succinct Representation of Balanced Parentheses and Static Trees
- Succinct ordinal trees with level-ancestor queries
- Compressing and indexing labeled trees, with applications
- A Uniform Approach Towards Succinct Representation of Trees
- Indexing compressed text
- Squeezing succinct data structures into entropy bounds
- Universal Succinct Representations of Trees?
- A Space-Economical Suffix Tree Construction Algorithm
- Algorithms on Strings, Trees and Sequences
- New text indexing functionalities of the compressed suffix arrays
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Balanced parentheses strike back
- Algorithms and Computation
- Orderly Spanning Trees with Applications
- Engineering a compressed suffix tree implementation
- Automata, Languages and Programming
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Computing and Combinatorics
