  We introduce height-bounded LZ encodings (LZHB), a new family of compressed
representations that are variants of Lempel-Ziv parsings with a focus on
bounding the worst-case access time to arbitrary positions in the text directly
via the compressed representation. An LZ-like encoding is a partitioning of the
string into phrases of length $1$ which can be encoded literally, or phrases of
length at least $2$ which have a previous occurrence in the string and can be
encoded by its position and length. An LZ-like encoding induces an implicit
referencing forest on the set of positions of the string. An LZHB encoding is
an LZ-like encoding where the height of the implicit referencing forest is
bounded. An LZHB encoding with height constraint $h$ allows access to an
arbitrary position of the underlying text using $O(h)$ predecessor queries.
While computing the smallest LZHB encoding efficiently seems to be difficult
[Cicalese \& Ugazio 2024, arxiv], we give the first linear time algorithm for
strings over a constant size alphabet that computes the greedy LZHB encoding,
i.e., the string is processed from beginning to end, and the longest prefix of
the remaining string that can satisfy the height constraint is taken as the
next phrase. Our algorithms significantly improve both theoretically and
practically, the very recently and independently proposed algorithms by
Lipt\'ak et al. (arxiv, to appear at CPM 2024). We also analyze the size of
height bounded LZ encodings in the context of repetitiveness measures, and show
for some constant $c$, the size $z_{HB}$ of the optimal LZHB encoding with
height bound $c\log n$ is $O(g_{rl})$, where $g_{rl}$ is the size of the
smallest run-length grammar. We also show $z_{HB} = o(g_{rl})$ for some family
of strings, making $z_{HB}$ one of the smallest known repetitiveness measures
for which $O({\sf polylog} n)$ time access is possible using linear space.
