Efficient Grammar Compression via RLZ-based RePair

Area of Science:

• Computer Science
• Data Compression
• Algorithms

Background:

• RePair is a grammar-based compression technique effective for creating compact grammars.
• RePair's main limitation is its high memory usage, scaling poorly with input size.
• Relative Lempel-Ziv (RLZ) parsing is a scalable, lightweight online method but may miss structural patterns.

Purpose of the Study:

• To develop a scalable algorithm that constructs exact RePair grammars.
• To leverage the strengths of both RePair and RLZ parsing for improved data compression.
• To reduce memory usage and the number of bigram replacements in grammar-based compression.

Main Methods:

• Introduced RLZ-RePair, an algorithm generating RePair grammars from RLZ parses.
• Ensured systematic bigram replacements while preserving RLZ phrase integrity.
• Systematically applied RePair iterations on RLZ parsed input.

Main Results:

• RLZ-RePair achieves identical grammars to standard RePair with a well-chosen reference.
• Demonstrated significant memory reduction: RePair used 18%–480% more memory.
• RLZ-RePair requires fewer bigram replacements compared to standard RePair.

Conclusions:

• RLZ-RePair offers a scalable solution for constructing exact RePair grammars.
• This method results in a practical grammar-based compressor for large datasets.
• RLZ-RePair combines the efficiency of RLZ parsing with the theoretical strengths of RePair.