Key points are not available for this paper at this time.
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that is a variant of Lempel-Ziv parsings with a focus on allowing fast access to arbitrary positions of the text directly via the compressed representation. Any LZHB encoding whose referencing height is bounded by h allows access to an arbitrary position of the underlying text using O (h) predecessor queries. We show that there exists a constant c such that the size z₇₁ (₂ ₍) of the optimal (smallest) LZHB encoding whose height is bounded by c n for any string of length n is O (gₑ₋), where gₑ₋ is the size of the smallest run-length grammar. Furthermore, we show that there exists a family of strings such that z₇₁ (₂ ₍) = o (gₑ₋), thus making z₇₁ (₂ ₍) one of the smallest known repetitiveness measures for which O (polylog n) time access is possible using O (z₇₁ (₂ ₍) ) space. While computing the optimal LZHB representation for any given height seems difficult, we propose linear and near linear time greedy algorithms which we show experimentally can efficiently find small LZHB representations in practice.
Bannai et al. (Tue,) studied this question.