Довольно быстро после опубликования статьи Бао появляться первые компрессоры. Это объясняется, вопервых метод оказался хорошим компромиссом между быс использующими словарное сжатие, и медленными писсимистическими компрессорами. Во-вторых, авторы соглашаются на некоммерческое использование.

С тех пор количество программ, использующих уза - Уилера, непрерывно растет.

Сортировка - это очень важный компонент архиватора, реализующего сжатие на основе преобразования Барроуза - Уилера. Именно от нее зависит скорость сжатия. До недавнего времени именно сортировка была узким ме­стом. В настоящее время моделирование стало достаточно сложным, чтобы конкурировать по времени работы с процедурой сортировки, реализации которой, напротив, совершенствуются в сторону ускорения. Но и теперь возможна ситуация, когда характеристики сжимаемых данных таковы, что могут существенно замедлить сортировку.

Основные требования к сортировке заключаются в том, что она ...

Перейдем к рассмотрению способов сжатия данных, полученных в ре­зультате описанных выше преобразований. Для начала надо разобраться с данными, которые нам необходимо сжать.

Рассмотрим фрагмент данных, типичный для текста, преобразованного посредством BWT. Для примера взят файл bookl из набора "Calgary Corpus" (рис. 5.19).

eteksehendeynkrtdserttnregenskngsgsedeneyswmessrne xgynystslgyegsgstssrhmsstetehselxtptneessthndesddy htksthwtpfdttegedmmhysyresprssneenselgetdemsetse,t reehsetrtteseeeeeesssdeedmnlendeedgtdgttdsgtteeysy tddentnrxsltshtghnteeernsdpwlttensedehsteeswekheee ...

Как уже было сказано, само по себе преобразование Барроуза - Уилера не сжимает. Эту работу проделывают другие методы, призванные толково распо­рядиться теми свойствами, которыми обладают преобразованные данные.

Среди таких методов можно отметить следующие:

■ кодирование длин повторов (RLE);

■ метод перемещения стопки книг [35] (MTF);

■ кодирование расстояний (DC);

■ метод Хаффмана;

■ арифметическое кодирование.

Последовательность применения методов, используемых совместно с BWT: