Offline dictionary-based compression

Abstract

A compression scheme referred to as RE-PAIR is developed by combining a novel phrase derivation method and a compact dictionary encoding. The scheme is offline only while inferring the dictionary, and during decompression bits are read and phrases written in a fully interleaved manner. Further, during decoding only a compact representation of the dictionary must be stored. Overall, during decompression, the scheme has a space advantage over both incremental dictionary-based schemes and over context-based source models.