Source-linked AI summary
Random Access to Grammar Compressed Strings
Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, Oren Weimann
TL;DR
Grammar-compressed strings and trees need efficient queries without expanding the compressed representation. The paper introduces grammar representations based on heavy paths and biased search structures, achieving logarithmic access and substring operations with linear or near-linear preprocessing, and extends the framework to approximate matching and tree navigation.
Problem
Compressed databases require direct, efficient queries and answer retrieval because full decompression can require substantially more space than the compressed data.
Method
The paper combines heavy-path representations with predecessor and biased weighted-ancestor data structures for grammar-compressed strings and balanced-parenthesis tree encodings.
Results
The representations support O(log N) random access, O(m + log N) substring decompression, and efficient approximate matching and ordered-tree navigation without full decompression.
Takeaways & Limitations
Grammar compression can support core string and tree queries directly, with O(n) RAM preprocessing or O(n·α_k(n)) pointer-machine preprocessing for the stated operations.
Takeaways & Limitations
The stated bounds assume log N-bit memory cells and distinguish pointer-machine from RAM models.
Abstract
from arXiv · showhide
Grammar based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular compression schemes. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$ achieving $O(\log N)$ random access time, and either $O(n\cdot α_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $α_k(n)$ is the inverse of the $k^{th}$ row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k, k^4 + |P|\} + \log N) + occ)$, where $occ$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two "biased" weighted ancestor data structures, and a compact representation of heavy paths in grammars.
1 Introduction
The paper addresses random access, substring decompression, approximate matching, and tree navigation directly on grammar-compressed data. It introduces representations and techniques achieving logarithmic query times with linear or near-linear construction space, avoiding full decompression.
- Problem setting: Grammar compression replaces long strings with small straight-line programs that capture schemes including Lempel-Ziv, Sequitur, run-length encoding, and Re-Pair.The grammar generates exactly one string, with rules containing either two variables or one terminal.
- String operations: O(log N) random access and O(m + log N) substring decompression are supported with O(n·α_k(n)) pointer-machine or O(n) RAM preprocessing and space.These bounds apply to an SLP of size n representing a string of length N, with a substring of length m.
- Tree operations: O(log N) navigation operations are supported on ordered trees represented by SLP-compressed balanced-parenthesis sequences.The representation uses O(n·α_k(n)) words and preprocessing on pointer machines, or O(n) words and preprocessing on RAM.
- Motivation: Naive derivation-tree traversal can take Ω(n) time, while balancing an SLP can increase its size to O(n log N).Earlier succinct representations reduced space but could still require O(h log n) query time, motivating the paper’s new representations.
- Approximate matching: O(n(min{|P|k, k^4 + |P|} + log N) + occ) time finds approximate pattern occurrences in grammar-compressed strings using suitable uncompressed matching algorithms.The corresponding pointer-machine space is O(n·α_k(n) + |P| + occ) for the stated Landau-Vishkin or Cole-Hariharan instantiations.
- Techniques: The main technical approach combines heavy-path decompositions with predecessor and biased weighted-ancestor structures.Biased searches make the total predecessor-query cost O(log N), while the RAM construction uses biased skip trees and succinct trees.
2 Fast Random Access in Linear Space
The representation partitions an SLP’s parse tree into heavy paths and stores compact predecessor information, enabling random access through top-down searches without expanding the full string.
- Heavy path representation: Heavy paths classify children by subtree leaf counts, with each internal node selecting a maximum-size heavy child and the remaining children light.For SLPs, node size is the generated substring length, so the decomposition is defined directly on grammar variables.
- Stored search information: Each heavy path suffix stores its string length, a distinguished leaf position and character, and predecessor structures for left and right size sequences.The sequences accumulate one plus the sizes of the corresponding left, right, and light children along the suffix.
- Search procedure: A top-down query compares the target position with the distinguished leaf and either returns its character or descends into a light child using a predecessor result.For positions below the stored leaf, the search uses the left sequence; for positions above it, it uses the right sequence and adjusted position.
- Heavy path representation: O(n) space represents the SLP’s heavy paths through a heavy path forest, avoiding independent treatment of all O(n^2) heavy path suffixes.The forest connects each node to its heavy child and uses left and right edge weights for light-subtree sizes.
- Performance: O(log N log log N) random access follows from reducing predecessor searches on heavy-path sequences to weighted ancestor queries on the forest.The construction uses O(n) preprocessing time and space.
3 Interval-Biased Search Trees
Interval-biased search trees make predecessor queries faster when the query interval is small, allowing the O(log N) searches along a heavy path to telescope to O(log N) total time. They can be constructed in linear time, yielding O(log N) random access with quadratic preprocessing in the initial application.
- Interval-biased predecessor queries: O(log(U/x)) predecessor queries replace O(log log N) searches, where x is the successor–predecessor interval length.This interval-sensitive bound is what enables the query costs along heavy paths to telescope.
- Initial application: O(log N) random access is obtained after O(n^2) preprocessing and space when the interval-biased tree is applied independently to heavy path suffixes.This is the direct lemma before the later space reductions.
- Linear-time construction: O(n̂) construction time and space are achieved by doubling searches from both ends before each binary search.This avoids unbalanced recursive partitions causing O(n log n) total construction time.
- Linear-time construction: O(n̂) total binary-search work follows from the recurrence T(n̂) = T(d) + T(n̂ − d) + log d for d ≤ n̂/2.The recurrence bounds the sum of all recursive construction searches by O(n̂).
- Search refinement: The tree supports a reduced search start when p is known to exceed a stored endpoint, using lowest-common-ancestor information.This allows the search to begin near the relevant portion of the interval-biased tree.
4 Closing the Time-Space Tradeoffs for Random Access
A heavy-path decomposition of the suffix forest, followed by a light representation and recursive tree decompositions, reduces the preprocessing and space needed for O(log N) random access. The resulting bounds are O(n log n), then near-linear recursive bounds, and finally O(n·α_k(n)) on the pointer machine.
- Heavy-path representation: O(n) space supports the heavy-path suffix forest and its left and right weighted sequences, forming the basis for weighted ancestor queries.The forest is compact because its nodes are the grammar variables, and its weighted structure can be computed in O(n) time.
- Light representation: O(log N) random access follows after O(n log n) preprocessing and space using interval-biased trees on heavy paths of the suffix forest.The light representation translates the remaining navigation problem into weighted ancestor queries.
- Recursive decomposition: O(n/log n) top-tree leaves permit interval-biased structures on each top-tree root-to-leaf path, while bottom trees are handled recursively.Bottom-tree branching representations reduce each recursive instance to O(log n) nodes.
- Recursive decomposition: O(n log log n) and then O(n log log log n) preprocessing arise from recursively applying the weighted-ancestor structure to branching representations.Continuing the recursion yields O(n log∗n) preprocessing while preserving O(log N) random access.
- Final bound: O(n·α_k(n)) preprocessing and space support O(log N) random access on the pointer machine for any fixed k.Choosing recursive sizes more carefully reduces the log∗n factor to α_k(n).
5 Biased Skip Trees
The section develops biased skip trees and colored-ancestor support for navigating heavy paths efficiently. It establishes linear-time color assignment and constant-time within-block colored-ancestor queries as components of the compressed-string representation.
- Biased Skip Trees: The structure links nodes on each leaf-to-root path by color-c pointers, generalizing static biased skip lists to trees.Pointers can be followed in O(1) time.
- Color Assignment: cmax ≤ 1 + log2 N, while the maximum color on a path from v is at most 1 + log2 Wv.The color construction starts from each node’s rank and increments it when necessary to preserve the ancestor-color invariant.
- Biased Search: O(log(Wv/wu) + 1) time supports biased searches from v to u in the heavy-path forest.Here wu is the light-child size and Wu is the node weight.
- Color Assignment: O(n) time suffices to compute all node colors in the heavy-path forest.A preorder traversal maintains a word-sized counter encoding relevant ancestor colors.
- Colored Ancestors: O(n) preprocessing and O(n) words support nca and additional navigation queries in the word-RAM setting.The method partitions the balanced-parentheses sequence into blocks and uses representatives for inter-block navigation.
- Colored Ancestors: O(1) time supports nca queries within a block after reducing its colors to at most b distinct values.The block structure stores reduced colors and auxiliary information for constant-time queries.
6 Substring Decompression
The representation extends random access to substring decompression by collecting subtrees adjacent to the endpoint search paths. Only two endpoint accesses are needed, with additional time linear in the output length.
- Substring Decompression: Two random access computations plus O(m) additional time decompress a substring of length m.This improves over independently performing m random access computations.
- Substring Decompression: Constant-factor extra pointers identify descendant nodes adjacent to heavy-path suffixes on both sides.These pointers are computed during heavy-path decomposition without increasing asymptotic construction complexity.
- Substring Decompression: The algorithm finds the lowest common ancestor of the endpoint search paths and collects neighboring subtrees along the paths to both endpoints.The collected subtrees are decoded in total time O(m).
7 Compressed Approximate String Matching
The paper solves approximate matching on grammar-compressed strings without decompressing the full text by combining local boundary decompression with an uncompressed matching algorithm. Matches are computed bottom-up and merged across grammar nodes.
- Method: The method combines substring decompression with a black-box uncompressed approximate string matching algorithm.The approach assumes the uncompressed algorithm reports matches in sorted order.
- Matching Algorithm: O(n) local matching computations find approximate occurrences by processing each grammar node bottom-up.At an internal node, the algorithm matches across a boundary substring containing up to m + k characters from each child.
- Matching Algorithm: Only matches crossing a grammar-node boundary require the concatenated suffix and prefix substring of the two children.Any match with at most k errors crossing the boundary is contained in this boundary region.
- Complexity: O(occ) time merges the sorted match lists because matches merged at each node are disjoint in the text.The total output size is occ, the number of occurrences of P in S.
8 Random Access to Compressed Trees
The paper represents ordered trees through SLP-compressed balanced-parentheses strings and reduces tree navigation to compressed binary-string operations. Heavy-path data and excess-search structures provide logarithmic-time navigation without decompressing the tree.
- Tree Representation: O(e) SLP size represents the balanced-parentheses string of a tree compressed as a DAG with e edges.The construction introduces nonterminals for each DAG node and its child positions.
- Binary-String Primitives: Excess on an opening parenthesis equals the represented node’s depth when opening parentheses encode 1 and closing parentheses encode 0.This connects binary-string excess operations to tree navigation.
- Binary-String Primitives: O(log N) time supports rank, select, and excess with O(nα_k) pointer-machine space and preprocessing, or linear space and preprocessing on the RAM.These operations form the binary-string primitives used by the tree representation.
- Excess Search: O(log N) time supports forward and backward excess search plus RMQ and RMQi operations under the same pointer-machine and RAM bounds.The method simulates excess search over a min-max structure built on the parse tree.
- Excess Search: Heavy-path suffixes store sums and excess ranges for light-child subtrees, enabling searches that move between heavy paths.The stored values include suml, sumr, mr, and Mr, with asymmetric variants for the search direction.
- Tree Navigation: O(log N) time supports the listed navigation operations on an SLP-compressed balanced-parentheses tree representation.The representation combines rank, select, excess, search, and range-extremum operations.
9 Conclusions
The paper achieves logarithmic-time access and substring decompression for grammar-compressed strings, while extending efficient operations to grammar-compressed ordered trees. These results avoid dependence on grammar height and enable non-trivial approximate matching without decompression.
- O(log N) random access and O(m + log N) substring decompression are supported for strings generated by grammars of size n.The representations use O(n) space and preprocessing time on the RAM model, with near-linear bounds on the pointer machine.
- O(log N) tree operations are supported on N-node ordered trees represented by grammars generating balanced parenthesis strings.The supported operations cover a wide variety of navigation and other tree queries.
- The presented time complexities are the first for these problems without a linear dependency on grammar height.
- The substring-decompression method yields the first non-trivial approximate string-matching results on grammar-compressed strings, and remains the fastest black-box method to date.
- Existing lower bounds show that random access on some grammar-compressed string families requires near-logarithmic time under polynomial or near-polynomial space constraints.The bounds are Ω((log N)^(1−ϵ)) with n^O(1) space for one family and Ω(log N / log log N) with n(log n)^O(1) space for another.