Bzip2 Algorithm

Bzip2 is a lossless data compression algorithm and file format that compresses a single file at a time using a multi-stage pipeline built around the Burrows-Wheeler transform. It first rearranges the input data into runs of similar bytes using that block-sorting transform, applies a move-to-front transformation and run length encoding to exploit the resulting patterns, and finishes by Huffman coding the result. Julian Seward wrote bzip2, first releasing it as bzip in July 1996; a follow-up version, 0.1, replaced an earlier arithmetic coding stage with Huffman coding in August 1997 because of software patent concerns around arithmetic coding, and the tool reached version 1.0 in late 2000. Bzip2 generally compresses text more tightly than the older DEFLATE-based formats, though usually more slowly, which has kept it in use for archiving where a smaller file matters more than compression speed.