MR-RePair: Grammar Compression Based on Maximal Repeats

We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePair replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats. Then, we design...

Full description

Saved in:
Bibliographic Details
Main Authors: Furuya, Isamu, Takagi, Takuya, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Kida, Takuya
Format: Conference Proceeding
Language:English
Subjects:
Compression algorithms
Data compression
Grammar
grammar compression
Informatics
Maintenance engineering
maximal repeat
Production
RePair
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePair replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats. Then, we design a novel variant of RePair, called MR-RePair, which substitutes the most frequent maximal repeats at once instead of substituting the most frequent pairs consecutively. We implemented MR-RePair and compared the size of the grammar generated by MR-RePair to that by RePair on several text corpora. Our experiments show that MR-RePair generates more compact grammars than RePair does, especially for highly repetitive texts.
ISSN:2375-0359
DOI:10.1109/DCC.2019.00059