2017/04/27 by Philip Bille, Bille, Philip, Inge Li Gørtz +3
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.1704.08558
openalex publication_date 2017/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Re-Pair is an efficient grammar compressor that operates by recursively replacing high-frequency character pairs with new grammar symbols. The most space-efficient linear-time algorithm computing Re-Pair uses (1+ε)n+√ n words on top of the re-writable text (of length n and stored in n words), for any constant ε>0; in practice however, this solution uses complex sub-procedures preventing it from being practical. In this paper, we present an implementation of the above-mentioned result making use of more practical solutions; our tool further improves the working space to (1.5+ε)n words (text included), for some small constant ε. As a second contribution, we focus on compact representations of the output grammar. The lower bound for storing a grammar with d rules is log(d!)+2d≈ dlog d+0.557 d bits, and the most efficient encoding algorithm in the literature uses at most dlog d + 2d bits and runs in \mathcal O(d1.5) time. We describe a linear-time heuristic maximizing the compressibility of the output Re-Pair grammar. On real datasets, our grammar encoding uses---on average---only 2.8% more bits than the information-theoretic minimum. In half of the tested cases, our compressor improves the output size of 7-Zip with maximum compression rate turned on.