Improvements to the Block Sorting Text Compression Algorithm

Abstract

This report presents some further work on the recently described “Block Sorting” lossless or text compression algorithm. It is already known that it is a context-based compressor of unbounded order, but those contexts are completely restructured by the sort phase of the compression. The report examines the effects of those context changes. It is shown that the requirements on the final compression stage are quite different from those in compressors of more conventional design. The report then presents several different approaches to improving the compression performance, eventually yielding a compressor which is among the best so far presented and is actually based on fundamental work by Shannon in 1950. It is shown that the block-sorting technique compares well with other compressors in terms of compression factor, compression speed and working memory.