Классификация методов сжатия
Современные методы сжатия
Без преувеличения можно сказать, что известны тысячи различных методов сжатия данных, однако многие из них заметно уступают другим по всем параметрам и поэтому не представляют интереса. Оставшиеся методы можно разбить на три больших класса.
Алгоритмы статистического моделирования
Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.
Эти алгоритмы обладают очень низкой скоростью сжатия и требуют большого объема оперативной памяти, скорость декодирования практически не отличается от скорости кодирования.
Несмотря на очень хорошие характеристики в смысле качества сжатия, использовать алгоритмы статистического моделирования на практике часто затруднительно или невозможно ввиду невысокой скорости сжатия.
Кроме того, многие предложенные способы реализации методов сжатия статистическим моделированием для получения оценок вероятностей появления символов используют команды умножения и/или деления, а иногда и вычисления с плавающей точкой. Так как такие реализации предъявляют жесткие требования к аппаратному обеспечению, область их применения ограничена.
Алгоритмы словарного сжатия
Алгоритмы словарного сжатия заменяют подстроки кодируемой последовательности символов ссылками в словарь на идентичные подстроки. С практической точки зрения наилучшими представляются алгоритмы семейства LZ (впервые предложенные Лемпелом и Зивом в 1977г.), которые заменяют начало не просмотренной части кодируемого сообщения ссылкой на самое длинное вхождение идентичной подстроки в уже закодированной части.
Обычно для ускорения поиска совпадающих подстрок и ограничения объема требуемой памяти область поиска ограничивается определенным количеством последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).
Алгоритмы семейства LZ в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.
Огромное преимущество алгоритмов семейства LZ – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).
Большая часть современных промышленных систем сжатия данных построено на основе различных вариантов алгоритма LZ77, в течение многих лет заслуженно считавшихся наилучшими по соотношению скорости и качества сжатия.
Алгоритмы сжатия сортировкой блоков
Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.
По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.
Методы энтропийного кодирования
Как правило, вышеперечисленные методы сжатия применяются не самостоятельно, а в сочетании с каким-либо методом энтропийного кодирования, заменяющего символы их кодовыми словами – строками нулей и единиц – так, что более часто встречающимся символам соответствуют более короткие слова.
Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.
Префиксные коды
Префиксные коды называются так потому, что ни одно кодовое слово не является полным началом (т. е. префиксом) никакого другого слова, что гарантирует однозначность декодирования.
Известно много способов построения префиксных кодов: коды Шеннона и Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.
Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах малой мощности (2-8 символов) или при наличии символов с очень большой (более 30-50%) вероятностью появления и по качеству сжатия могут уступать арифметическим.
Применение блочных кодов, кодирующих не отдельные символы, а блоки из k символов, позволяет построение кодов, сколь угодно близких по качеству кодирования к арифметическим, однако из-за полиномиальной сложности блочного кодирования по размеру блока и ряда других причин блочное кодирование почти не применяется на практике.
Как правило, алгоритмы словарного сжатия и сжатия сортировкой блоков используют для кодирования выхода основного алгоритма сжатия коды Хаффмана.
Арифметические коды
Арифметические коды не ставят явного соответствия между символами и кодовыми словами, они основаны на других принципах.
Качество арифметического кодирования лучше, чем у посимвольного префиксного кодирования, и близко к теоретическому минимуму и при малой мощности алфавита, и при очень неравномерном распределении вероятностей появления символов.
С другой стороны, кодирование и декодирование арифметических кодов при достаточно большой мощности кодируемого алфавита заметно медленнее кодирования и декодирования префиксных кодов, а разница в качестве сжатия обычно незначительна; по этим и ряду других причин в большинстве случаев префиксное кодирование более предпочтительно для практического использования.
Арифметические коды обычно применяются в сочетании с методами статистического моделирования для кодирования символов в соответствии с предсказанными вероятностями.