Основные алгоритмы сжатия без потерь информации

Сжатие осуществляется либо на прикладном уровне с помощью программы сжатия, либо с помощью устройств защиты от ошибок непосредственно в составе модемов.

Основными методами сжатия являются: вероятностные, статические, арифметические, словарей и кодирование повторов.

К методам сжатия также относятся методы разностного кодирования, поскольку разности амплитуд представляется меньшим числом разрядов. Разностное кодирование реализовано в методах дельта-модуляции и её разновидностях.

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

Вероятностные методы сжатияиспользуют кодовые слова переменной длинны. В основе вероятностных методов сжатия (алгоритмов Шеннона-Фано и Хаффмена) лежит идея построения «дерева», на «ветвях» которого положение символа определяется частостью его появления. Каждому символу присваивается код, длина которого обратно пропорциональна частости появления этого символа. Существуют две разновидности вероятностных методов, различающихся способом определения вероятности появления каждого символа:

– статические методы, использующие фиксированную таблицу частости появления символов, рассчитываемую перед началом процесса сжатия,

– динамические или адаптивные методы, в которых частость появления символов все время меняется и по мере считывания нового блока данных происходит перерасчет начальных значений частостей.

Статические методыимеют значительное быстродействие и не требуют большой оперативной памяти. Они нашли широкое применение в многочисленных программах–архиваторах, например ARC, PKZIP и др., но для сжатия передаваемых модемами данных используются редко – предпочтение отдается арифметическому кодированию и методу словарей, обеспечивающим большую степень сжатия.

Арифметические методы. При арифметическом кодировании строка символов заменяется действительным числом больше нуля и меньше единицы Арифметическое кодирование позволяет обеспечить высокую степень сжатия, особенно в случаях, когда сжимаются данные, где частость появления различных символов сильно варьируется. Однако сама процедура арифметического кодирования требует мощных вычислительных ресурсов, так как активно использует нецелочисленную арифметику, и до недавнего времени этот метод мало применялся при сжатии передаваемых данных. Лишь появление мощных процессоров, особенно с RISC–архитектурой, позволило создать эффективные устройства арифметического сжатия данных.

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