Random Access to Grammar Compressed Strings

Details Random Access to Grammar Compressed Strings Random Access to Grammar Compressed Strings

2010-01-11

arxiv.org/abs/1001.1565v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 of the popular compression schemes, including the Lempel-Ziv family, Run-Length Encoding, Byte-Pair Encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring of $S$ without decompressing $S$. 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 either O(n) construction time and space and $O(\log N \log \log N)$ random access time, or $O(n\cdot \alpha_k(n))$ construction time and space and $O(\log N)$ random access time. Here, $\alpha_k(n)$ is the inverse of the $k^{th}$ row of Ackermann's function. Our representations extend to efficiently support decompression of any substring in $S$. Namely, we can decompress any substring of length $m$ in the same complexity as a random access query and additional $O(m)$ time. Combining this with fast algorithms for standard uncompressed approximate string matching leads to several efficient algorithms for approximate string matching within 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$.

Affiliated with

Also associated with

No associations

Rating

Random Access to Grammar Compressed Strings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random Access to Grammar Compressed Strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Access to Grammar Compressed Strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-458337