Burrows-Wheeler transform

The Burrows-Wheeler transform (BWT, also called block-sorting compression), is an algorithm used in data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler.

Note on sorting convention

If you sort with Posix collating, you get the slightly different string

Related Topics:
Posix - Collating

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

instead of

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

ISO 8859 has complex collating rules, but in this case, periods are

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

ignored. Posix collating treats periods as characters.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~