Saturday, 25 July 2009

Optimizing the Burrows-Wheeler Transform

The OCaml Journal just published an article about parallelized data compression:

"The Burrows-Wheeler Transform (BWT) is one of the few preconditioners used in data compression and, in particular, is the core of the popular bzip2 compression utility. This article describes a simple 19-line implementation of the BWT in OCaml and progressively optimizes the implementation to use a customized quicksort then distributed fork-based parallelism and finally shared-memory parallelism. On 8 cores, the final optimized implementation is over 65× faster than the original..."

To read this article and more, subscribe to The OCaml Journal today!

No comments: