Преобразование Барроуза Уилера

Преобразование Барроуза Уилера (Burrows-Wheeler transform, BWT)-это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. BWT используется в архиваторе bzip2.
Краткое описание и решаемые задачи
Меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов. Таким образом BWT выполняет задачу сжатия исключением повторяющихся подстрок.

Когда символьная строка трансформируется при помощи BWT, ни один из её символов не изменяется. Оно просто меняет порядок символов. Если в исходной строке есть подстроки, которые встречаются часто, тогда трансформированная строка будет иметь некоторые места, где одиночный символ повторяется несколько раз подряд. Это полезно для компрессии, так как ведёт к облегчению сжатия строки, которая состоит из повторяющихся символов, при помощи таких техник, как кодирование длин серий.
Например, строка:
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
трансформируется в эту* строку, которая легче сжимается, потому что содержит много повторяющихся символов:
TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT
Описание алгоритма