Архиваторы, использующие BWT и ST

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

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

220

Раздел 1. Методы сжатия без потерь

Семейство программ BRed, BRed и BRed3 написано одним из родона­чальников BWT - Дэвидом Уилером. Многие идеи, использованные в этих компрессорах, описаны в работах Петера Фенвика [18] и нашли свое приме­нение в ряде других программ, например в XI.

Bzip использует адаптированную к BWT сортировку Бентли - Седжвика, во многом позаимствованную из вышеупомянутого семейства. После BWT выполняется преобразование методом стопки книг, выходные данные кото­рого сжимаются при помощи интервального кодирования (аналог арифме­тического сжатия) с использованием 1-2-кодирования и структурной моде­ли Петера Фенвика.

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

В BWC используются такие же методы, что и bzip и bzip2. А именно оп­тимизированная сортировка, MTF, 1-2-кодирование и интервальное коди­рование.

IMP использует собственную сортировку, очень быструю на обычных текстах, но буквально "зависающую" на данных, в которых встречаются длинные одинаковые последовательности символов. Сжатие полностью по­заимствовано из bzip2.

Алгоритм сжатия, используемый в bzip2, также включен и в архива­тор 7-Zip.

В szip, помимо упоминавшегося частичного сортирующего преобразова­ния, реализована и возможность использования BWT. Реализована, прямо скажем, только для примера, без затей. А вот для сжатия используются очень интересные решения, представляющие собой некий гибрид MTF-преобразования и адаптивного кодера, берущий статистику из короткого окна преобразованных с помощью BWT данных. С участием автора szip и с использованием описанных решений был также создан архиватор ICT UC.

В Zzip применяются все те же испытанные временем структурная мо­дель, сортировка Бентли - Седжвика и кодирование диапазонов.

ВА использует аналогичную сортировку. Но повышение устойчивости реализовано в ВА другим способом. Деление строк по ключу прекращается в том случае, когда оказывается, что этим строкам предшествуют одинако­вые символы. Еще одно новшество, реализованное в ВА, - это выбор струк­турной модели MTF в отдельном проходе. Также за счет динамического оп­ределения размера блока улучшено сжатие неоднородных файлов. Для уси­ления сжатия английских текстов используется переупорядочение алфавита.

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

Отличительная особенность SBC - наличие мощной криптосистемы. Ни в одном из архиваторов, пожалуй, не реализовано столько алгоритмов шиф­рования, как в SBC. В SBC используется алгоритм BWT, ориентированный на большие блоки избыточных данных и позволяющий очень быстро сорти­ровать данные с большим количеством длинных похожих строк. Вместо MTF в архиваторе используется кодирование расстояний, хотя пока не так эффективно, как в YBS и DC, но это компенсируется большим количеством фильтров (методов препроцессинга), настроенных на определенные типы данных.

ARC (автор - Ian Sutton, которому также принадлежит РРМ-архиватор BOA). Как и многие другие, использует BWT на основе сортировки Бент-ли - Седжвика и MTF. Как и в SBC, дополнительно отслеживаются очень длинные повторы данных.

Первые версии YBS также использовали перемещение стопки книг, ко­торое затем было заменено на кодирование расстояний. Что дало заметный выигрыш в степени сжатия.

Среди не распространяемых свободно компрессоров, описание которых опубликовано в научных трудах, можно отметить BKS98 и BKS99, которые принадлежат сразу трем авторам [10]. Эти компрессоры используют суф-фиксную сортировку и многоконтекстовую модель MTF по трем последним кодам.

Сравнение BWT-архиваторов

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

Тестирование производилось на компьютере со следующей конфигура­цией:

Процессор Частота шины Оперативная память Жесткий диск Операционная система

Начнем со сжатия русских текстов, потому что BWT-архиваторы осо­бенно эффективны именно для сжатия текстов. А русские тексты выбраны для того, чтобы показать эффективность сжатия в чистом виде, без исполь­зования текстовых фильтров, которые для русских текстов еще не созданы авторами описываемых программ. Файл имеет длину 1,639,139 байт.

Как можно заметить, первенство удерживают компрессоры, использую­щие кодирование расстояний.

На английском тексте (2 042 760 байт) некоторые архиваторы использу­ют фильтры, тем самым заметно улучшая сжатие. Ниже приведены резуль­таты, принадлежащие тем программам, которые показали наилучшие ре­зультаты в первом тесте.

При сжатии данных, представляющих собой исходные тексты программ, распределение среди лидеров тестов практически не меняется.

Для иллюстрации поведения BWT-архиваторов на неоднородных дан­ных применен исполнимый модуль из дистрибутива компилятора Watcom 10.0 wcc386.exe (536,624 байта). Для того чтобы можно было судить об эф­фективности различных методов и режимов, некоторые строки помечены специальными знаками:

В качестве файла, содержащего смесь текстовых и бинарных данных, использовался Fileware.doc размером 427,520 байт из поставки русского MS Office'95. Данный пример показывает, что иногда модель, использующая MTF, оказывается достаточно эффективной.

Заключение

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

Можно отметить характерные особенности архиваторов, использующих описанное преобразование, по сравнению с другими.

Скорость сжатия - на уровне архиваторов, применяющих словарные ме­тоды, например LZ77. Разжатие, как правило, в 3-4 раза быстрее сжатия. Степень сжатия сильно зависит от типа данных.

Наиболее эффективно применение BWT-архиваторов для текстов и лю­бых данных со стабильными контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к программам, использую­щим РРМ. На неоднородных данных существующие архиваторы на основе BWT немного уступают лучшим современным компрессорам, использующим словарные методы или РРМ. Впрочем, существуют способы компен­сировать этот недостаток.

Расходы памяти в режиме максимального сжатия довольно близки у всех современных архиваторов. Наибольшее отличие наблюдается при декоди­ровании. Наиболее скромными в этом отношении являются архиваторы, ис­пользующие алгоритмы семейства LZ77, а наиболее расточительными -РРМ-компрессоры, требующие столько же ресурсов, сколько им нужно при сжатии. Архиваторы на основе BWT занимают промежуточное положение.