Ultra-succinct representation of ordered trees with applications

DOI10.1016/j.jcss.2011.09.002zbMath1242.68083MaRDI QIDQ414928

Kunihiko Sadakane, Jesper Jansson, Wing-Kin Sung

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

zbMATH Keywords

succinct data structure; compressed suffix tree; ordered tree; tree degree entropy; xbw

Mathematics Subject Classification ID

05C05: Trees

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

68P05: Data structures

Related Items

Compressed Multiple Pattern Matching, Random Access to Grammar-Compressed Strings and Trees, Unnamed Item, Generation matrix: an embeddable matrix representation for hierarchical 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, High-order entropy compressed bit vectors with rank/select, Tree compression using string grammars, Adaptive succinctness, Improved range minimum queries, Parallel construction of succinct trees, Succinct data structure for dynamic trees with faster queries, Representation of ordered trees with a given degree distribution, Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number, 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

• PATRICIA

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