LZBE: An LZ-Style Compressor Supporting $O(\log n)$-Time Random Access

This paper proposes the LZ-Begin-End (LZBE) factorizations, a new class of LZ-like factorizations in which each copy factor refers to a contiguous sequence of preceding factors, i.e., both the begin and end positions of the reference must align with factor boundaries. LZBE lies between grammar-based compression and LZ-Begin/LZ-End in terms of structure and compression performance. Our contributions are summarized as follows:

1. 1.

   We clarify the theoretical relationship between LZBE factorizations and grammar-based compression. First, we show that any context-free grammar can be converted into an LZBE factorization without increasing its size. We then prove that the greedy LZBE factorization can be asymptotically smaller than the smallest grammar, and establish a matching upper bound on the grammar–LZBE size ratio. Together, these results establish the relationship between the two representations with matching upper and lower bounds.

2. 2.

   We propose a linear-space compressed data structure that supports random access in $O(\log n)$ time. This establishes LZBE as one of the smallest known compression schemes that support $O(\log n)$-time random access using space linear in the compressed size.

3. 3.

   We present a linear-time algorithm for computing the greedy LZBE factorization.

To address the limitations of traditional LZ-like factorizations, several restricted variants have been proposed, including LZ-Begin/LZ-End [16] and Height-Bounded LZ (LZHB, also known as BAT-LZ) [4, 18]. These variants aim to support efficient random access while keeping space usage linear in their compressed size. LZ-Begin/LZ-End restricts each copy factor to reference a previous substring that begins/ends at a factor boundary, whereas LZHB constrains the height of the dependency graph formed by copy relationships.

The LZ-End index [15] allows for random access in $O({\log }^{4}n\log \log n)$ time on LZ-End compressed strings. However, that work establishes only the “existence” of such a data structure and does not provide an efficient construction algorithm. The authors note that the construction achieving the worst-case polylogarithmic query time is only known to run in expected polynomial time and no deterministic variant is known. Improving either the construction time or derandomization remains an open problem.

In contrast, LZHB with a maximum height of $O(\mathrm{poly}\log n)$ naturally supports $O(\mathrm{poly}\log n)$-time random access. Nevertheless, the theoretical understanding of LZHB remains limited. Given an arbitrary LZ-like factorization (even when restricted to LZ-Begin/LZ-End), how to “balance” the factorization without increasing its size is still an open problem. Moreover, it is known that finding the smallest parsing under a given height bound is NP- and APX-hard [10]. Therefore, it remains unclear whether LZHB can outperform other LZ-like factorization methods.

We apply the grammar decomposition [22] to $T$, which prunes all subtrees rooted at non-leftmost occurrences of nonterminals in the derivation tree. Each leaf in the pruned tree becomes a factor: terminals form char factors, and pruned nonterminals form copy factors referring to their leftmost occurrence. Since each nonterminal appears at most once as an internal node, the number of factors is bounded by $g$. As each copy factor refers to the concatenation of leaves (i.e., factors) in a subtree, it refers to a consecutive preceding factors. Hence, the resulting factorization is an LZBE factorization. $◀$ This theorem immediately implies that $z_{\mathrm{be}}^{\mathrm{OPT}}\le g^{\mathrm{OPT}}$. Figure 2 shows an example of a grammar and its corresponding LZBE factorization.

The above discussion shows that the LZBE scheme is at least as powerful as grammar compression. A natural question is whether they are asymptotically equivalent or strictly stronger. To address this, we present the following theorem.

To prove this, we consider the off-line range-product problem (ORPP).

The following lower bound is known for this problem:

We construct an input string $T$ for ORPP over the alphabet $\mathrm{\Sigma }=\{x_1,\mathrm{\dots },x_m,{\$}_1,\mathrm{\dots },{\$}_{m+1}\}$ as follows:

We refer to each character ${\$}_i$ as a delimiter character, and let ${\mathrm{\Sigma }}_x=\{x_1,\mathrm{\dots },x_m\}$ be the set of non-delimiter characters. The greedy LZBE factorization of $T$ consists of the first $m$ characters and each delimiter as a char factor, and each substring $x_{l_i}\mathrm{\cdots }{x}_{r_i}$ as a copy factor referring to $[l_i,r_i]$. Thus, $z_{\mathrm{be}}^{\mathrm{g}}\in \mathrm{\Theta }(m)$ holds. We now show the following lemma.

We first convert the input CFG $𝒢$ into an equivalent SLP ${𝒢}^{\prime }$ of size $O(g)$. Since $T$ contains $2m+1$ distinct characters, we have $g\in \mathrm{\Omega }(m)$. For any nonterminal $X$, let $\mathrm{head}(X)$ and $\mathrm{tail}(X)$ denote the longest prefix and suffix of $\exp (X)$ consisting of non-delimiter characters, respectively. For any string $C=x_{t_1}\mathrm{\cdots }{x}_{t_{|C|}}$ over ${\mathrm{\Sigma }}_x$, we define $\mathrm{val}(C)={⨂}_{j=1}^{|C|}{x}_{t_j}$. We compute $\mathrm{val}(\mathrm{head}(X))$ and $\mathrm{val}(\mathrm{tail}(X))$ for each nonterminal $X$ in a bottom-up fashion. For rules $X\to x_i$, the values are trivially $x_i$. For a nonterminal $X$ with a rule $X\to YZ$, the values are computed as follows:

An example of computing $\mathrm{val}(\mathrm{head}(X))$ and $\mathrm{val}(\mathrm{tail}(X))$ using the rules above is shown in Figure 3. Since the total number of nonterminals is $O(g)$, we can compute $\mathrm{val}(\mathrm{head}(X))$ and $\mathrm{val}(\mathrm{tail}(X))$ for all nonterminals using $O(g)$ semigroup operations.

Since $T$ contains delimiters ${\$}_1,\mathrm{\dots },{\$}_{m+1}$ in order, for each $1\le i\le m$, there exists a unique rule $X\to YZ$ such that $Y$ contains ${\$}_i$ and $Z$ contains ${\$}_{i+1}$. For such a rule, the string $Q_i$ corresponding to the $i$-th query range can be represented as $Q_i=\mathrm{tail}(Y)\cdot \mathrm{head}(Z)$. Thus, the value $q_i$ of the $i$-th range-product query can be computed by

After computing $\mathrm{val}(\mathrm{head}(X))$ and $\mathrm{val}(\mathrm{tail}(X))$ for all $X$, we can compute all $q_i$ in $O(m)$ time. Thus, the total number of operations required is $O(g+m)=O(g)$. $◀$ We are now ready to prove Theorem 2.

Let $m$ be an arbitrarily large integer, and consider an ORPP instance requiring $\mathrm{\Omega }(m\alpha (m))$ semigroup operations by Lemma 4. Construct the string $T$ from this instance as described earlier. The greedy LZBE factorization of $T$ has size $z_{\mathrm{be}}^{\mathrm{g}}\in \mathrm{\Theta }(m)$. Assume, for contradiction, that $g^{\mathrm{OPT}}\in o(z_{\mathrm{be}}^{\mathrm{g}}\alpha (z_{\mathrm{be}}^{\mathrm{g}}))$ for such a string $T$. Then, by Lemma 3, the ORPP instance could be solved in $O(g)$ operations, contradicting the lower bound $\mathrm{\Omega }(m\alpha (m))=\mathrm{\Omega }(z_{\mathrm{be}}^{\mathrm{g}}\alpha (z_{\mathrm{be}}^{\mathrm{g}}))$. Therefore, the theorem holds. $◀$

Conversely, we can also prove that the above lower bound is tight even when considering the ratio between the smallest grammar size and the smallest LZBE factorization size. This is shown by a reduction to the same problem together with an existing upper bound of ORPP.

The construction given in the theorem directly yields an SLP of size $O(m\alpha (m))$, because the sequences $(b_1,\mathrm{\dots },b_t)$, $(c_{m+1},\mathrm{\dots },c_t)$, and $(d_{m+1},\mathrm{\dots },d_t)$ can be interpreted as a derivation sequence of nonterminals.

We now show the following theorem which directly implies $g^{\mathrm{OPT}}\in O(z_{\mathrm{be}}^{\mathrm{OPT}}\alpha (z_{\mathrm{be}}^{\mathrm{OPT}}))$.

We begin by constructing an ORPP instance from the given LZBE factorization. The instance consists of a sequence $(a_1,\mathrm{\dots },a_{z_{\mathrm{be}}})$ and $z_{\mathrm{be}}$ queries, each corresponding to an LZBE factor. If the $i$-th factor $F_i$ is a char factor, its query range is simply $(l_i,r_i)=(i,i)$. If $F_i$ is a copy factor referring to $F_j\mathrm{\cdots }{F}_k$, its query range is defined as $(l_i,r_i)=(j,k)$.

Using Corollary 3, we obtain an SLP of size $O(z_{\mathrm{be}}\alpha (z_{\mathrm{be}}))$. We then convert this SLP with terminals ${\mathrm{\Sigma }}_a$ into a CFG with terminals $\mathrm{\Sigma }$ that generates the original string $T$. First, we introduce a new start symbol $S$ and add the rule $S\to a_1\mathrm{\cdots }{a}_{z_{\mathrm{be}}}$. Next, for each terminal $a_i$, we replace all its occurrences in the rules as follows.

1. 1.

   If $F_i$ is a char factor representing a character $c$, then replace $a_i$ with a new nonterminal $X_i$ such that $\exp (X_i)=c$.

2. 2.

   If $F_i$ is a copy factor, then replace $a_i$ with the existing nonterminal $X_i$ such that $\exp (X_i)=a_{l_i}\mathrm{\cdots }{a}_{r_i}$.

The existence of such a nonterminal in the second case is guaranteed by Corollary 3. We can easily see that the size of the new grammar is $O(z_{\mathrm{be}}\alpha (z_{\mathrm{be}}))$.

Since the start symbol $S$ is expanded as $S\to a_1\mathrm{\cdots }{a}_{z_{\mathrm{be}}}$, it suffices to verify that each nonterminal $X_i$ replacing $a_i$ satisfies $\exp (X_i)=F_i$. We prove this by induction on $i$. If $F_i$ is a char factor representing $c$, then by the definition of $X_i$, the nonterminal $X_i$ generates $c$, and hence $\exp (X_i)=F_i$. Now suppose that $F_i$ is a copy factor, and assume as the induction hypothesis that $\exp (X_{i^{\prime }})=F_{i^{\prime }}$ for all . The new nonterminal $X_i$ corresponding to $F_i$ is defined by the rule $X_i\to X_{l_i}\mathrm{\cdots }{X}_{r_i}$. By the induction hypothesis and the fact that , each $X_{i^{\prime }}$ with $l_i\le i^{\prime }\le r_i$ expands to $F_{i^{\prime }}$. Therefore, $\exp (X_i)=\exp (X_{l_i})\mathrm{\cdots }\exp (X_{r_i})=F_{l_i}\mathrm{\cdots }{F}_{r_i}=F_i$. By induction, we have $\exp (X_i)=F_i$ for all $1\le i\le z_{\mathrm{be}}$, and consequently $\exp (S)=F_1\mathrm{\cdots }{F}_{z_{\mathrm{be}}}=T$. Since the size of the constructed grammar is $O(z_{\mathrm{be}}\alpha (z_{\mathrm{be}}))$, the theorem follows. $◀$

We note that the lower bound also applies to run-length grammars [21], which are an extension of CFGs allowing for run-length rules of the form $X\to Y^k$. We denote the size of the smallest run-length grammar generating $T$ by $g_{\mathrm{rl}}^{\mathrm{OPT}}$. Since the string $T$ constructed from the ORPP input is square-free, $g_{\mathrm{rl}}^{\mathrm{OPT}}=g^{\mathrm{OPT}}$ holds. Thus, for such $T$, we have $g_{\mathrm{rl}}^{\mathrm{OPT}}\in \mathrm{\Omega }(z_{\mathrm{be}}^{\mathrm{g}}\alpha (z_{\mathrm{be}}^{\mathrm{g}}))$. This bound is tight even for optimal LZBE factorization; $g_{\mathrm{rl}}^{\mathrm{OPT}}\in O(z_{\mathrm{be}}^{\mathrm{OPT}}\alpha (z_{\mathrm{be}}^{\mathrm{OPT}}))$ also holds for any $T$ since $g_{\mathrm{rl}}^{\mathrm{OPT}}\le g^{\mathrm{OPT}}$ and $g^{\mathrm{OPT}}\in O(z_{\mathrm{be}}^{\mathrm{OPT}}\alpha (z_{\mathrm{be}}^{\mathrm{OPT}}))$.

Conversely, there exists a string for which $g_{\mathrm{rl}}^{\mathrm{OPT}}$ is asymptotically smaller than $z_{\mathrm{be}}^{\mathrm{OPT}}$. For example, the string $T={𝚊}^n$ satisfies $g_{\mathrm{rl}}^{\mathrm{OPT}}=O(1)$ and $z_{\mathrm{be}}^{\mathrm{OPT}}=O(\log n)$, which implies that $z_{\mathrm{be}}^{\mathrm{OPT}}\in \mathrm{\Omega }(g_{\mathrm{rl}}^{\mathrm{OPT}}\log n)$ in this case. This bound is tight, since $g^{\mathrm{OPT}}\in O(g_{\mathrm{rl}}^{\mathrm{OPT}}\log n)$ and $z_{\mathrm{be}}^{\mathrm{OPT}}\le g^{\mathrm{OPT}}$ together yield $z_{\mathrm{be}}^{\mathrm{OPT}}\in O(g_{\mathrm{rl}}^{\mathrm{OPT}}\log n)$ for any $T$.

We prove this lemma by showing that any two non-consecutive extended factors (i.e., those with $|i-j|\ge 2$) must be distinct. Assume for contradiction that $E_i=E_j$ for some . If $E_j=F_j$, then $E_i=E_j$ implies that $E_j$ appears in $\{E_1,\mathrm{\dots },E_{j-1}\}$, contradicting the definition of extended factors. Therefore, it must be that $E_j=F_j{F}_{j+1}$. In that case, since $E_i=E_j=F_j{F}_{j+1}$ appears earlier than ${\mathrm{pos}}_{\mathrm{L}}(F_j)$ as a consecutive sequence of factors, choosing $F_j$ as the next factor violates the longest-greedy condition, as $E_i$ would have been the longer valid choice. Thus, non-consecutive extended factors must be distinct. $◀$

If , then $F_{k+1}$ begins with $F_i{F}_{i+1}=E_i$, so the claim holds. If $E_i=F_i$, the claim also clearly holds. It remains to consider the case where $E_i=F_i{F}_{i+1}$ and $F_{k+1}=F_i$. In this case, $F_i$ already appears as an earlier extended factor. Thus, $F_i$ would not be chosen as the start of a new factor since the algorithm selects the leftmost valid occurrence. Therefore, this case does not occur, and the claim holds. $◀$

We begin by describing a simple algorithm that does not provide strong theoretical guarantees. This algorithm maintains a trie representing all extended factors computed so far. Suppose we have already computed the factorization $F_1\mathrm{\cdots }{F}_k$ for the prefix $T[1,p]$. To determine the next factor starting at position $p+1$, we follow the path in the trie along the suffix $T[p+1,n]$. For each extended factor $E_i$ on this path, we attempt to extend $E_i$ to the longest prefix of $T[p+1,n]$ that can be expressed as a concatenation $F_i\mathrm{\cdots }{F}_j$ for some $i\le j$. This is done by computing the longest common prefix (LCP) length $d$ between $T[p+1,n]$ and $T[{\mathrm{pos}}_{\mathrm{L}}(F_i),n]$, and locating the factor containing the position ${\mathrm{pos}}_{\mathrm{L}}(F_i)+d$. Each such computation yields a candidate factor $F_i\mathrm{\cdots }{F}_j$, and we select the longest among them as $F_{k+1}$. We can answer LCP queries in constant time by using an LCP array [19] together with a range minimum data structure [6], both of which can be constructed in $O(n)$ time and space.

Although conceptually simple, this approach offers no strong time bound. In the worst case, the path traversal for computing $F_{k+1}$ may traverse far beyond the length of the factor eventually selected. A straightforward analysis shows that the running time becomes $O(n^2)$, and it is unclear whether a faster guarantee can be obtained for this method. We therefore turn to a refined approach that achieves an $O(n)$ running time.

To obtain a linear time algorithm, we replace the extended factor trie with the suffix tree ST [25] of $T$ and augment it with additional structures. We construct a Weighted Level Ancestor (WLA) structure [5] and an incremental Nearest Marked Ancestor (NMA) structure [3] on the ST. Together, these allow us to locate the locus of any substring and to maintain marks on the loci with amortized constant time updates and queries. All components can be constructed in $O(n)$ time and stored in $O(n)$ space. In the algorithm, each extended factor $E_i$ is represented by a mark at the corresponding locus. With this refinement, enumerating candidate extended factors is replaced by walking up from the leaf representing the suffix $T[p+1,n]$ and repeatedly computing NMAs. For each retrieved mark corresponding to an extended factor, we compute the LCP value between the suffix and extendend factor, and obtain a candidate of the next factor. After selecting $F_{k+1}$, we insert marks for the newly created extended factors, and the NMA structure maintains them.

We now analyze the running time of this algorithm. Consider computing $F_{k+1}$ starting from the position $p+1$, and let $d$ be the maximum depth of any marked locus on the path representing $T[p+1,n]$. Since each locus can carry at most two marks by Lemma 5, the path contains at most $2d$ marks in total. The deepest mark on the path corresponds to an extended factor that matches a prefix of $T[p+1,n]$ of length $d$, which implies that the length of the next factor $F_{k+1}$ is at least $d$. Consequently, the number of candidate extended factors that must be examined is $O(|F_{k+1}|)$. Because each LCP, WLA, NMA, and marking operation runs in amortized constant time, computing $F_{k+1}$ and updating the data structures takes amortized $O(|F_{k+1}|)$ time. Since the total length of all factors is $n$, summing over all iterations shows that the greedy LZBE factorization can be computed in overall $O(n)$ time.