A copy of this work was available on the public web and has been preserved in the Wayback Machine. The capture dates from 2011; you can also visit the original URL.
The file type is `application/pdf`

.

##
###
Random Access to Grammar-Compressed Strings
[chapter]

2011
*
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
*

Let S be a string of length N compressed into a contextfree grammar S of size n. We present two representations of S achieving O(log N ) random access time, and either O(n · α 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

doi:10.1137/1.9781611973082.30
dblp:conf/soda/BilleLRSSW11
fatcat:docm3pba2zepxfohirlpmzzteu