The Sort Transformation

Michael Schindler >data<////compression consulting

The sort transformation is an alternative to the Burrows-Wheeler transformation described in Wheelers article or Mark Nelsons article.

This transformation features a fast and deterministic in time alternate approach that could be implemented in hardware easily. For more information see the original paper presented at the DCC97 or patent application ur US patent 6,199,064. (both links go to external sites - please inform me if broken)

This algorithm is protected by US patent 6,199,064, others pending.

Available at this page is (Explorer users: Your program has problems with double extensions (.tar.gz, .ps.gz), so please look at the extension produced when saving):

  • gzipped extended abstract
  • DCC97 gzipped poster
  • DCC97 proceedings page 469 (c) IEEE, inhouse use only!
  • sample program for order 4 as from 1997
  • source for order 1 and 2 program as from 1997
  • NEW source code for comp/decomp BWT model as in the order 4 package
  • source code of mark nelsons BWT article (you may want this for comparison)

    • The compression program szip uses this sort and allows you to experiment with various orders.

    A remark on the comp/decomp source code: the comments at the beginning are not accurate, it actually uses 2 MTF models before the full model and a cache of size 30. However for historical reasons I made the original source available. If there is interest I can also make the source available with unix linefeeds and as .tar.gz instead of .zip.

    (c) Michael Schindler, April 2000.
    If you locate a spelling error click here

     michael@compressconsult.com