Опрос

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

Новички

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

Алгоритм

В последние несколько лет приобрели популярность и были существен­но развиты методы предварительной обработки текстовой информации. В настоящее время специализированный препроцессинг текстов, позво­ляющий заметно улучшить сжатие, используется в таких архиваторах, как ARHANGEL, JAR, RK, SBC, UHARC, в компрессорах DC, PPMN.

Использование словарей

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

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

Основная идея состоит в том, чтобы для каждой ...

В табл. 4.9 представлены сведения о степени сжатия файлов набора CalgCC компрессорами, реализующими соответствующие алгоритмы кон­текстного моделирования. В первой строке указано название алгоритма, во второй, по необходимости, порядок использованной модели - строка "o-N" указывает, что использовалась модель порядка N. В строке "Итого" указана средняя не взвешенная по размеру файлов степень сжатия всего CalgCC.

Алгоритм сРРМИ реализует механизм наследования информации и ис­пользует SEE-d2. Описание прочих алгоритмов было дано выше.

Таблица ...

LOEMA

Судя по всему, впервые алгоритм контекстного моделирования был реа­лизован в 1982 г. Робертсом (Roberts) [2]. Автор назвал свой алгоритм Local Order Estimation Markov Analysis (марковский анализ посредством оценива­ния локального порядка). В LOEMA используется полное смешивание оце­нок КМ различного порядка, при этом веса представляют собой значения уровня доверия к оценке в том смысле, как это понимается в математиче­ской статистике. Сравнение степени сжатия LOEMA с другими алгоритма­ми затруднено, так как, с одной стороны, программа, реализующая алго­ритм, не стала ...

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

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

При фиксировании максимального порядка контекстов в районе 5-6 РРМ даже без наследования информации дает отличные результаты на текстах, но не очень хорошо работает на высокоизбыточных данных с большим количеством длинных повторяющихся строк. В середине 90-х гт. был предложен метод борьбы с этим недостатком [6]. Предложенный алго­ритм, РРМ* (произносится как "пи-пи-эм ста"), был основан на использова­нии контекстов неограниченной длины. Авторы алгоритма предложили следующую стратегию выбора максимального порядка на каждом шаге: максимальный порядок соответствует порядку самого короткого ...

Модификация счетчиков после обработки очередного символа может быть реализована по-разному. После кодирования каждого символа естест­венно изменять соответствующие счетчики во всех КМ порядков 0,l,...,N, что и предлагается, в частности, делать в алгоритмах РРМА и РРМВ. Такой подход называется полным обновлением (full updates). Но в случае класси­ческого, не использующего наследование информации РРМ лучшие резуль­таты достигаются, когда счетчики оцененного символа увеличиваются только в КМ порядков о, о+1, ..., N, где о - порядок КМ, в которой символ был ...

Опубликование в 1984 году алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода. Наиболее важные из них приведены в [Salomon 2000].

Техника контекстного моделирования Prediction by Partial Matching (предсказание по частичному совпадению), предложенная в 1984 г. Клири (Geary) и Уиттеном (Witten) [5], является одним из самых известных под­ходов к сжатию качественных данных и уж точно самым популярным среди контекстных методов. Значимость подхода обусловлена и тем фактом, что алгоритмы, причисляемые к РРМ, неизменно обеспечивают в среднем наи­лучшее сжатие при кодировании данных различных типов и служат стан­дартом, "точкой отсчета" при сравнении универсальных алгоритмов сжатия.

Перед собственно рассмотрением ...