Switching between two on-line list update algorithms for higher compression of Burrows-Wheeler transformed data

摘要

Encoding data by switching between two universal data compression algorithms achieves higher rates of compression than either algorithm alone. Applied with two list updating algorithms, the technique yields higher compression of piecewise independent identically distributed (PIID) data, such as the output of the Burrows-Wheeler transform. Introduced within a new class of such algorithms, the Best x of 2x-1. When paired with variants of the move-to-front algorithm in a switching scheme, the Best x of 2x-1 algorithms achieve higher compression of PIID data.