Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

BWT

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

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

Компрессор и версия

Даты

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

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

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

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

eteksehendeynkrtdserttnregenskngsgsedeneyswmessrne xgynystslgyegsgstssrhmsstetehselxtptneessthndesddy htksthwtpfdttegedmmhysyresprssneenselgetdemsetse,t reehsetrtteseeeeeesssdeedmnlendeedgtdgttdsgtteeysy tddentnrxsltshtghnteeernsdpwlttensedehsteeswekheee ...

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

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

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

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

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

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

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

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

Введение

Преобразование Барроуза - Уилера применяется в алгоритмах сжатия качественных данных. Для эффективного использования преобразования необходимо, чтобы характеристики данных соответствовали модели источника с памятью.

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

Вот уже в течение полутора десятков лет представители семейства РРМ остаются наиболее мощными практическими алгоритмами с точки зрения степени сжатия. По-видимому, добиться лучших результатов смогут только более изощренные контекстные (в широком смысле) методы, которые, не­сомненно, будут появляться, так как производятся все более быстрые про­цессоры, а объем оперативной памяти ЭВМ становится все больше.

Наилучшие результаты алгоритмы РРМ показывают на текстах: отлич­ный коэффициент сжатия при высокой скорости, чему наглядным примером являются компрессоры PPMd и PPMonstr. Кроме ...

Алгоритмы словарного сжатия Зива-Лемпела появились во второй поло­вине 70-х гг. Это были так называемые алгоритмы LZ77 и LZ78, разрабо­танные совместно Зивом (Ziv) и Лемпелом (Lempel). В дальнейшем перво­начальные схемы подвергались множественным изменениям, в результате чего мы сегодня имеем десятки достаточно самостоятельных алгоритмов и бессчетное количество модификаций.

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


Статистические

Преобразующие

Поточные

Блочные1''

" Поточные

Блочные

Для "слов", модель "Источник с ...