A Metric for Compression with the Burrows-Wheeler and Move-to-Front Transforms

Compression of symbolic information constructed according to a grammar, such as textual strings, has long been a topic of interest in computer science. The Burrows Wheeler Transform (BWT), combined with some form of the Move-To-Front Transform (MTFT), have received significant attention in recent year. Much of the BWT/MTFT literature has debated the suitability of one algorithm flavor over another, justifying these results against standardized test suites. However, there has been little activity in evaluating the input string for suitability with respect to a particular algorithm flavor, without significantly degrading the computational performance of the compression system.

We introduce a metric used to evaluate input strings for BWT/MTFT-type compression algorithm suitability. The metric may be used with input strings of arbitrary length, and may be used with arbitrary input language. The convergence of the metric is discussed, showing that the metric may be approximated accurately with relatively low computational complexity, allowing input to be evaluated with lower complexity than that required for computing the output of the compression algorithm. Furthermore, much of the computation required for the highly parallelizable metric also serves to compute the BWT. As a result, the metric may be employed impractical computational systems.