36 Программы сжатия данных: возможности и принципы работы

Архиваторы (программы сжатия данных) - это программы для создания архивов. Как правило, данные предварительно подвергаются процедуре сжатия, или упаковки. Поэтому почти каждый архиватор одновременно является программой для сжатия данных.

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

Методы сжатия архиваторов

1) статистический - если предпоалгает соответствие входного потока определенной модели сигнала и осуществляет сжатие на основе собранной о тексте стат.информации.
2) инкрементальный - осуществляющий сжатие путем кодирвоания отличий в последовательных записях.
3) макро-или текстовой подстановки - выполняющий сжатие путем поиска совпадающих строк и замены их на более короткие коды.

Кодирование длин серий (RLE, Run Length encoding - кодирование длин серий). Очень простой метод. Последовательная серия одинаковых элементов данных заменяется на 2 символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный методы. В качестве самостоятельного метода применяется например в графическом формате BMP.

Словарный метод (LZ, Lempel Ziv - имена авторов). Наиболее распространенный метод. Используется словарь, состоящий из последовательностей данных или слов. При сжатии эти слова заменяются на их коды из словаря. В наиболее распространенном варианте реализации в качестве словаря выступает сам исходный блок данных.

Энтропийный метод (Huffman - кодирование Хаффмена, Арифметическое кодирование). В этом методе элементы данных, которые встречаются чаще, кодируются при сжатии более коротким кодом, а более редкие элементы данных кодируются более длинным кодом. За счет того, что коротких кодов значительно больше общий размер получается меньше исходного. Широко используется в графическом формате JPG.

Метод контекстного моделирования (CM, контекстное моделирование). В этом методе строится модель исходных данных. При сжатии очередного элемента данных эта модель выдает свое предсказание, или вероятность. Согласно этой вероятности элемент данных кодируется энтропийным методом.

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

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

Предварительные преобразования или фильтрация - данные методы служат не для сжатия, а для представления информации в удобном для дальнейшего сжатия виде.

Метод сортировки блока данных (по имени авторов). Это особый вид или группа преобразований в основе которых лежит сортировка. Такому преобразованию можно подвергать почти любые данные. Сортировка производится над блоками, поэтому данные предварительно разбиваются на части.
Этот метод показыват наиболее высокую скорость и степень сжатия для текстовых данных (!)

Сжатие способом кодирования серий

Наиболее известный простой подход и алгоритм сжатия информации обратным путем - это кодирование серий последовательностей (RLE). Метод состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на 1 кодирующий байт и счетчик числа их повторений.


Характеристики алгоритмов сжатия и их применимость

Коэффициент сжатия - основная характеристика алгоритма сжатия. Он определяется как отношение объема исходных несжатых данных к объему сжатых: k = So / Sc , где k - коэффициент сжатия, So - объем исходных данных, Sc - объем сжатых

Чем выше коэффициент сжатия, тем алгоритм эффективнее.

если k = 1 - сжатие не производится
если k < 1 - алгоритм порождает сообщение большего размера, нежели несжатое, - вредная работа