Efficient Lempel-Ziv Prediction with the Run-Length BWT

Lempel-Ziv Plurality (LZP) is an algorithm that uses the Lempel-Ziv decomposition of a string to predict the next symbol, proposed by Kosoy. For a string of length n with z LZ77 phrases, the algorithm makes at most O(z log n) errors. However, Kosoy's implementation has an update time of O(z log^7 n), which can become a bottleneck in practical applications. This article presents an efficient online implementation based on the run-length encoded Burrows-Wheeler Transform (RLBWT) that reduces the update time to O(log z + log log n), achieving an exponential improvement. We also introduce a new variant—the Lempel-Ziv Majority (LZM) predictor—which performs predictions in O(1) time, independent of the alphabet size σ.

Background: LZP and LZ77 Decomposition

The core idea of LZP is to capture repeated patterns in a string through LZ77 decomposition and thereby predict the next symbol. LZ77 decomposition partitions a string into a sequence of phrases, each of which is either a reference to a previously occurring substring. LZP leverages the contexts of these phrases to predict the next symbol, with an error bound of O(z log n), where z is the number of phrases. This predictive capability has potential applications in areas such as data compression and text generation.

However, while Kosoy's original implementation guarantees the error bound, its update time is as high as O(z log^7 n), making it inefficient for long strings or scenarios requiring frequent updates. Therefore, designing a more efficient online implementation becomes a key challenge.

LZ77 decomposition is a fundamental technique for lossless data compression, introduced by Lempel and Ziv in 1977. It parses the input string into a sequence of phrases, each of which is either a single character or a reference to a previously occurring substring (typically represented as a distance-length pair). This decomposition captures repeated patterns in the data and is the core of many compression algorithms (such as DEFLATE and LZ4). In the context of LZP, the number of LZ77 phrases z directly determines the error bound of the predictor: the more repetitive the string, the smaller z, and the fewer prediction errors. Thus, the performance of LZP is closely tied to the LZ77 decomposition of the string.

Efficient Implementation Based on RLBWT

Our first implementation maintains the run-length encoded Burrows-Wheeler Transform (RLBWT) of the reversed history. RLBWT is a compressed data structure that efficiently represents repeated substrings. By operating on this structure, we implement the LZP predictor, which uses O(z log z log^2 n) bits of space, with a worst-case update time of O(log z + log log n) and a prediction time of O(σ (log z + log log n)), where σ is the alphabet size.

Compared to Kosoy's implementation, the update time is reduced from O(z log^7 n) to O(log z + log log n), an exponential improvement. This means that even for large-scale data, the implementation can maintain high responsiveness. Furthermore, the implementation supports online updates, i.e., it can accept new symbols at any time without prior knowledge of the alphabet.

The Burrows-Wheeler Transform (BWT) is a reversible string transform that sorts all cyclic shifts of a string and takes the last column, clustering identical characters and thereby greatly improving compression ratios. BWT is the core of compression tools such as bzip2. Run-Length Encoding (RLE) is a simple compression technique that replaces consecutive repeated characters with the character and its repeat count. RLBWT combines the two: it run-length encodes the result of the BWT, thereby efficiently representing highly repetitive strings. RLBWT supports efficient string matching and update operations and is the foundation of many modern compressed indexes (such as the r-index). In this article, RLBWT is used to maintain the reversed history, enabling the LZP predictor to be updated online and achieving an update time of O(log z + log log n).

New Variant: The Lempel-Ziv Majority Predictor

In addition to LZP, we also propose the Lempel-Ziv Majority (LZM) predictor. LZM has the same error bound and update time as LZP, but its prediction time is only O(1) and independent of the alphabet size σ. This property gives LZM a significant advantage when dealing with large alphabets, as the prediction time does not grow with σ.

Both LZM and LZP support online updates without prior knowledge of the alphabet. For the case where the alphabet is known, we provide another data structure with a per-symbol processing time of O(σ (1 + log z / log log n)), which is constant when σ=O(1) and z=polylog(n). This further extends the applicability of the algorithms.

Performance Analysis and Comparison

In terms of theoretical complexity, our RLBWT implementation reduces the update time of LZP from O(z log^7 n) to O(log z + log log n), and the prediction time from a higher level to O(σ (log z + log log n)). For LZM, the prediction time is further reduced to O(1) and is independent of σ. These improvements make the algorithms more efficient in practical applications.

In terms of space usage, the RLBWT implementation uses O(z log z log^2 n) bits, which is related to the logarithm polynomials of z and n; for highly compressible data, the space efficiency is high. In addition, the algorithms support online updates, making them suitable for streaming data processing scenarios.

It should be noted that these complexity results are theoretical worst-case guarantees, and actual performance may vary depending on data characteristics. However, the exponential improvement means that in most cases, the new implementation will be significantly faster than the original.

Online updates refer to the algorithm incrementally building the data structure as it reads input symbols and being able to immediately use it for prediction or queries without waiting for the entire input to be processed. This is crucial for streaming data (such as real-time logs and sensor data). Alphabet size σ is the number of distinct characters in the string; for example, σ=128 for ASCII text, while σ can be large for Unicode text. The dependence of prediction time on σ directly affects the practicality of the algorithm in large-alphabet scenarios (such as natural language processing or biological sequence analysis). The LZM predictor, with its O(1) prediction time independent of σ, significantly improves efficiency under large alphabets.

Application Prospects and Conclusion

Efficient LZP and LZM predictors have potential applications in data compression, text prediction, bioinformatics, and other fields. For example, in compression algorithms, accurate prediction can improve compression ratios; in text generation, fast prediction can enhance the interactive experience. The online update capability makes them suitable for real-time data streams.

In summary, through the RLBWT data structure, we achieve an exponential speedup of LZP and propose a more efficient LZM variant. These results lay the foundation for the application of prediction algorithms based on LZ decomposition in practical systems. Future work may include further optimizing practical performance, exploring more variants, and applying them to specific domains.