Ultra-succinct representation of ordered trees with applications

DOI10.1016/j.jcss.2011.09.002zbMath1242.68083OpenAlexW1973883768MaRDI 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 structurecompressed suffix treeordered treetree degree entropyxbw

Mathematics Subject Classification ID

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

Related Items (23)

Simultaneous encodings for range and next/previous larger/smaller value queries ⋮ Improved range minimum queries ⋮ Representation of ordered trees with a given degree distribution ⋮ Compressed directed acyclic word graph with application in local alignment ⋮ Parallel construction of succinct trees ⋮ Generation matrix: an embeddable matrix representation for hierarchical trees ⋮ Succinct data structure for dynamic trees with faster queries ⋮ Encoding range minima and range top-2 queries ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Unnamed Item ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ High-order entropy compressed bit vectors with rank/select ⋮ Tree compression using string grammars ⋮ Simple and efficient fully-functional succinct trees ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Compressed Multiple Pattern Matching ⋮ Fast Compressed Tries through Path Decompositions ⋮ Succinct Representations of Ordinal Trees ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Efficient computation of Lyapunov functions for Morse decompositions ⋮ Adaptive succinctness ⋮ Succinct dynamic cardinal trees

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

This page was built for publication: Ultra-succinct representation of ordered trees with applications