= Burrows-Wheeler transform
{c}
{title2=$\operatorname{BWT}(S)$}
The <Burrows-Wheeler transform> appends a unique smallest terminator to a <string>, sorts its <cyclic rotations> in <lexicographic order>, and records the last column. It is reversible because the first and last columns contain the same characters and the <last-to-first mapping> preserves the occurrence order of each character. The resulting letter arrangement supports both compression and <backward search>.<Opportunistic Data Structures with Applications by Paolo Ferragina and others>[§2, Background: sorted cyclic shifts and inversion]{ref}
Back to article page
