Finger Search, Random Access, and Longest Common Extensions in Grammar-Compressed Strings
Preprint
Abstract
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 new representations of grammars that supports efficient finger search style access, random access, and longest common extensions queries. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present the following. - An $O(n)$ space representation that supports setting a finger at any position $f$ in $O(\log N)$ time, and subsequently supporting access to any position $i$ in time $O(\log |f - i|)$. - An $O(N^\epsilon n^{1-\epsilon})$ space representation that supports random access to any position in constant time. - Two representations that support longest common extensions queries in either $O(N^{\frac{1}{2}+\epsilon} n^{\frac{1}{2}-\epsilon})$ space and $O(1)$ time or $O(n)$ space and $O(\log N + \log^2 \ell)$ time where $\ell$ is the length of the longest common extension. All of the above bounds significantly improve the currently best known results. To achieve the bounds we introduce several new data structural techniques of independent interest, including a new van Emde Boas style decomposition for grammars.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Detecting regularities on grammar-compressed stringsInformation and Computation, 2015
- Optimal finger search trees in the pointer machineJournal of Computer and System Sciences, 2003
- Application of Lempel–Ziv factorization to the approximation of grammar-based compressionTheoretical Computer Science, 2003
- Quorums from difference coversInformation Processing Letters, 2000
- Universal lossless compression via multilevel pattern matchingIEEE Transactions on Information Theory, 2000
- Grammar-based codes: a new class of universal lossless source codesIEEE Transactions on Information Theory, 2000
- Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context modelsIEEE Transactions on Information Theory, 2000
- On-line construction of suffix treesAlgorithmica, 1995
- A constant update time finger search treeInformation Processing Letters, 1994
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976