LZ-ABT: A Practical Algorithm for α-Balanced Grammar Compression

摘要

We propose a new LZ78-style grammar compression algorithm, named LZ-ABT, which is a simple online algorithm to create, given a string of length N over an alphabet of size σ, an α-balanced grammar in O(N log N log σ) time and O(n) space in addition to the input string, where n is the grammar size to output. LZ-ABT can avoid the lower-bound of Ω(N~(5/4)) time of the naive algorithms for LZMW and LZD, other LZ78-style compression algorithms, which was observed in [Badkobeh et al. SPIRE 2017, pp. 51-67]. We also show that the algorithm can be executed in compressed space, i.e., without storing the whole input string explicitly in memory: in O(N log2 N log σ) time and O（n) space, or O(N log N log σ) time and O(nlog* N) space. We implement LZ-ABT running in O(N log N log σ) time and O(N) space and empirically show that its performance is competitive to LZD. This is the first practical implementation of a-balanced grammar compression to the best of our knowledge.