Протоколы сжатия данных

Основные методы сжатия делятся на 2 типа:

· без потерь;

· с потерями (к ним относится, например, метод MPEG, позволяющий сжимать изображения 20:1).

Среди алгоритмов сжатия без потерь выделяют следующие методы:

Кодирование повторов RLE (Run-Length Encoding). Производится замена последовательности повторяющихся символов на строку, содержащую этот символ и число, соответствующее количеству его повторов. Применяется в основном для графических файлов (пример: PCX).

Вероятностные методы сжатия. Основаны на алгоритмах Шеннона-Фано и Хаффмена. Идея — построение дерева, положение символа на ветвях которого определяется частотой его появления. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления символа.
Различают статические и динамические методы. В статических методах используется фиксированная таблица частот появления символов, рассчитанная перед началом сжатия. При использовании динамических (или адаптивных) методов по мере появления нового блока данных происходит перерасчет начальных значений частот.
Статические методы используются в архиваторах, таких как ARC, PKZIP. В системах передачи данных эти методы применяются редко.

В модемах применяется в основном метод словарей.
Этот метод впервые описан в 1977 году в работах израильских исследователей Якова Зива и Абрахама Лемпеля. Алгоритм получил название LZ. В основе метода лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в передаваемом потоке на «образцы», хранящиеся в специально создаваемой таблице (словаре). Алгоритм основывается на том, что по потоку данных движется скользящее «окно», состоящее из двух частей. В большей по объему части содержится уже обработанная информация, а в меньшей помещается информация, прочитанная по мере просмотра. Во время считывания новой порции информации производится проверка, и если оказывается, что такая строка уже помещена в словарь ранее, то она заменяется ссылкой на нее.

Развитие этого алгоритма было предложено в 1984 году Терри Уэлчем и получило название LZW. Здесь таблица отображает строки символов в коды длиной 12 бит. Метод LZW применяется в протоколе V.42 bis, а алгоритм LZ77 – в утилите Double Space. Метод словарей LZW в протоколе V.42 bis позволяет достичь коэффициента сжатия 4:1.

В протоколах группы MNP применяются другие алгоритмы. Например, протокол MNP5 реализует комбинацию адаптивного кодирования с применением кода Хаффмена и группового кодирования. При этом достигается коэффициент сжатия примерно 2:1. В протоколе MNP7 используется метод Хаффмена в сочетании с марковским алгоритмом прогнозирования. Коэффициент сжатия — 3:1.