Improving Run Length Encoding by Preprocessing
Sven Fiergolla, Petra Wolf · 2021
The binary representation of an arbitrary string does not contain long runs of repeating bits, but, first, reading all most significant bits of all bytes, then all second most significant bits and so on, results in much longer average runs. We use this observation in combination with several preprocessing steps to obtain a lossless RLE based compression algorithm comparable to ZIP: First, the uncompressed byte array is analyzed and for each byte its number of occurrences is counted. In parallel, a bijective Burrows-Wheeler-Scott Transform is applied, which produces a reversible permutation of the input byte array with long repetitions of similar symbols. Afterwards, each byte is remapped, where the most frequent byte values are mapped to the lowest binary values. The resulting byte array is interpreted in a specific way, known as Bit-Layers text representation, where all bits of same significance are read consecutively, starting with the most significant bits, resulting in long average runs of identical bits. On this representation, a run length encoding (RLE) is applied and the runs are counted to generate a Huffman tree. Then, the runs are output with a variable length code, together with the mapping needed to decompress the file.