Height-bounded Lempel-Ziv encodings

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 ẑHB(clog n) of the optimal (smallest) LZHB encoding whose height is bounded by clog n for any string of length n is O(ĝᵣₗ), where ĝᵣₗ is the size of the smallest run-length grammar. Furthermore, we show that there exists a family of strings such that ẑHB(clog n) = o(ĝᵣₗ), thus making ẑHB(clog n) one of the smallest known repetitiveness measures for which O(polylog n) time access is possible using O(ẑHB(clog n)) 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.