Efficient online string prediction improves update and prediction speeds

Efficient Lempel-Ziv Prediction with the Run-Length BWT

Data Structures and AlgorithmsMachine Learning

Summary

Predicting the next letter in a sequence can help computers compress or understand text better. Kosoy created a method called LZP that predicts these letters but was slow to update and predict. The authors designed faster ways to implement LZP by using a special data structure called the run-length encoded Burrows-Wheeler transform. They also introduced a new predictor called LZM that predicts much quicker, especially when the alphabet is large or unknown.

What this means in practice

  • For data compression engineers: Implement faster online text compression algorithms that adapt quickly to incoming data without knowing the alphabet upfront.
  • For streaming data system developers: Integrate efficient online predictors that update rapidly and predict next symbols in real-time data streams with large or dynamic alphabets.

Authors

Ohad Avnery

Abstract

Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.