Re-Pair
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Re-Pair (short for recursive pairing) is a grammar-based compression algorithm that, given an input text, builds a straight-line program, i.e. a context-free grammar generating a single string: the input text. In order to perform the compression in linear time, it consumes the amount of memory that is approximately five times the size of its input. The grammar is built by recursively replacing the most frequent pair of characters occurring in the text. Once there is no pair of characters occurring twice, the resulting string is used as the axiom of the grammar. Therefore, the output grammar is such that all rules but the axiom have two symbols on the right-hand side. Re-Pair was first introduced by N. J. Larsson and A. Moffat in 1999.
Re-Pair (short for recursive pairing) is a grammar-based compression algorithm that, given an input text, builds a straight-line program, i.e. a context-free grammar generating a single string: the input text. In order to perform the compression in linear time, it consumes the amount of memory that is approximately five times the size of its input. The grammar is built by recursively replacing the most frequent pair of characters occurring in the text. Once there is no pair of characters occurring twice, the resulting string is used as the axiom of the grammar. Therefore, the output grammar is such that all rules but the axiom have two symbols on the right-hand side. Re-Pair was first introduced by N. J. Larsson and A. Moffat in 1999. The image on the right shows how the algorithm compresses the string w=xabcabcy123123zabc . During the first iteration, the pair ab , which occurs three times in w , is replaced by a new symbol R_1 . On the second iteration, the most frequent pair in the string w=xR_1cR_1cy123123zR_1c , which is R_1c , is replaced by a new symbol R_2 . Thus, at the end of the second iteration, the remaining string is w=xR_2R_2y123123zR_2 . In the next two iterations, the pairs 12 and R_{3}3 are replaced by symbols R_3 and R_4 respectively. Finally, the string w=xR_2R_2yR_4R_4zR_2 contains no repeated pair and therefore it is used as the axiom of the output grammar. num_rules_encoded = 256 // By default, the extended ASCII charset are the terminals of the grammar. writeSymbol(symbol s) { bitslen = log(num_rules_encoded); // Initially 8, to describe any extended ASCII character write s in binary using bitslen bits } void encodeCFG_rec(symbol s) { if (s is non-terminal and this is the first time symbol s appears) { take rule s → X Y; write bit 1; encodeCFG_rec(X); encodeCFG_rec(Y); assign to symbol s value ++num_rules_encoded; } else { write bit 0; writeSymbol(terminal/value assigned) } } void encodeCFG(symbol s) { encodeCFG_rec(s); write bit 1; } Another possibility is to separate the rules of the grammar into generations such that a rule X \to YZ belongs to generation i iff at least one of Y or Z belongs to generation i-1 and the other belongs to generation j with j \leq i-1 . Then these generations are encoded subsequently starting from generation 0 . This was the method proposed originally when Re-Pair was first introduced. However, most implementations of Re-Pair use the implicit encoding method due to its simplicity and good performance. Furthermore, it allows on-the-fly decompression.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1321817209 under CC BY-SA 4.0; modifications have been made.