Random Access to Grammar-Compressed Strings and Trees

DOI10.1137/130936889zbMath1329.68084OpenAlexW2171532727MaRDI QIDQ5255003

Srinivasa Rao Satti, Kunihiko Sadakane, Philip Bille, Rajeev Raman, Gad M. Landau, Oren Weimann

Publication date: 11 June 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://orbit.dtu.dk/en/publications/797f32fc-cb0b-4f9f-857d-2f60545f52bb

zbMATH Keywords

approximate string matchingtree compressiongrammar-based compressionstraight-line program

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Data structures (68P05) Algorithms on strings (68W32)

Related Items

Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts, A separation between RLSLPs and LZ77, Access, Rank, and Select in Grammar-compressed Strings, Document listing on repetitive collections with guaranteed performance, An LMS-based grammar self-index with local consistency properties, Grammar compressed sequences with rank/select support, Grammar-compressed indexes with logarithmic search time, Balancing run-length straight-line programs, Random access in persistent strings and segment selection, The nearest colored node in a tree, Unnamed Item, Block trees, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression, Tree compression using string grammars, Constant-time tree traversal and subtree equality check for grammar-compressed trees, Compressed range minimum queries, Approximate pattern matching on elastic-degenerate text, Online algorithms for constructing linear-size suffix trie, Optimal rank and select queries on dictionary-compressed text, Top tree compression of tries, Finger search in grammar-compressed strings, Constant delay traversal of grammar-compressed graphs with bounded rank, Random Access to High-Order Entropy Compressed Text, Succinct Representations of Ordinal Trees, Balancing straight-line programs for strings and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ultra-succinct representation of ordered trees with applications
• An improved algorithm for computing the edit distance of run-length coded strings
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Nearly optimal binary search trees
• Surpassing the information theoretic bound with fusion trees
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Biased skip lists
• Edit distance of run-length encoded strings.
• Collage system: A unifying framework for compressed pattern matching.
• Optimum binary search trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Approximate String Matching: A Simpler Faster Algorithm
• Self-indexed Text Compression Using Straight-Line Programs
• Fast Algorithms for Finding Nearest Common Ancestors
• Window Subsequence Problems for Compressed Texts
• Compressing and indexing labeled trees, with applications
• Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
• Processing Compressed Texts: A Tractability Border
• The Smallest Grammar Problem
• On Cartesian Trees and Range Minimum Queries
• Biased Search Trees
• The theory and computation of evolutionary distances: Pattern recognition
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Fast parallel and serial approximate string matching
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Universal lossless compression via multilevel pattern matching
• Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
• Grammar-based codes: a new class of universal lossless source codes
• Faster algorithms for string matching with k mismatches
• Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
• Automata, Languages and Programming
• Database Programming Languages