Современные методы хранения информации в сжатом виде(методы неискажающего сжатия и восстановления информации)

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

Как правило, алгоритмы словарного сжатия и сжатия сортировкой блоков используют для кодирования выхода основного алгоритма сжатия коды Хаффмана.

4.6 Арифметические  коды

Арифметические коды не ставят явного соответствия между символами и  кодовыми словами, они основаны на других принципах.

Качество арифметического кодирования лучше, чем у посимвольного префиксного кодирования, и близко к теоретическому минимуму и при малой мощности алфавита, и при очень неравномерном распределении вероятностей появления символов.

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

Арифметические коды обычно применяются  в сочетании с методами статистического моделирования для кодирования символов в соответствии с предсказанными вероятностями.

 

5 Обзор алгоритмов сжатия без потерь

5.1 RLE

Групповое кодирование – Run Length Encoding (RLE) – один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". Лучший, средний и худший коэффициенты сжатия – 1/32, 1/2, 2/1.

Одна из реализаций алгоритма такова: ищут наименее часто встречающийся  байт, называют его префиксом и  делают замены цепочек одинаковых символов на тройки "префикс, счетчик, значение". Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару "префикс, 1" или "префикс, 2". Остается одна неиспользованная пара "префикс, 0", которую можно использовать как признак конца упакованных данных.

При кодировании *.exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode).

Несмотря на то, что кодер RLE, как  правило, дает очень незначительное сжатие, он может работать очень быстро. А скорость работы декодера RLE вообще близка к скорости простого копирования блока информации. Алгоритм RLE схематично может быть описан следующим образом:

Кодер RLE

ТекущийСимвол := ДайОчереднойСимвол()

ТекущееСостояние := НЕТ_ПОВТОРОВ

ТекущаяДлина := 0

Пока ТекущийСимвол <> EOF

  Буфер := ДайОчереднойСимвол()

  Если Буфер = ТекущийСимвол

    Если ТекущееСостояние = НЕТ_ПОВТОРОВ

      Выдать  ( НЕТ_ПОВТОРОВ )

      Выдать  ( ТекущаяДлина )

      Выдать  ( ТекущаяДлина предыдущих символов сообщения )

      ТекущаяДлина := 2

      ТекущееСостояние := ПОВТОРЫ

    Иначе

      ТекущаяДлина := ТекущаяДлина + 1

    Конец если 

  Иначе

    Если ТекущееСостояние = НЕТ_ПОВТОРОВ

      ТекущаяДлина := ТекущаяДлина + 1 Иначе

      Выдать  ( ПОВТОРЫ )

      Выдать  ( ТекущаяДлина )

      Выдать  ( ТекущийСимвол )

      ТекущаяДлина := 1

      ТекущееСостояние := НЕТ_ПОВТОРОВ

    Конец если 

  Конец если

  ТекущийСимвол := Буфер

Конец пока

Декодер RLE

ТекущийКод := ДайКодФрагмента()

Пока ТекущийКод <> EOF

  ТекущаяДлина := ДайДлинуФрагмента()

  Если ТекущийКод = НЕТ_ПОВТОРОВ

    Выдать ( ТекущаяДлина, следующих символов сообщения )

  Иначе

    Выдать ( ТекущаяДлина, ДайОчереднойСимвол() )

  Конец если

  ТекущийКод := ДайКодФрагмента()

Конец пока

К положительным сторонам алгоритма, можно отнести то, что он не требует  дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется  в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования  в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

5.2 Алгоритмы семейства  LZ

Алгоритм LZ лежит в основе таких  известных программ-архиваторов, как PKZIP, LHA, ARJ, Stacker, Dblspace и многих других. Своим появлением он обязан двум исследователям из Израиля: Якобу Зиву и Абрахаму Лемпелу (Jacob Ziv & Abraham Lempel). В 1977 году они опубликовали работу. Ее появление ознаменовало начало новой эры в сжатии информации. Практически все современные компьютерные программы-архиваторы используют ту или иную модификацию алгоритма LZ. Одной из причин широкого распространения алгоритма LZ стала его исключительная простота.

Основная идея алгоритма

Вспомним первое четверостишье  бессмертного “Евгения Онегина”:

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

Обратите внимание на то, что Пушкин избегает повторного использования  подстроки “Мой дядя”. Сначала вместо нее используется местоимение “он”, затем — “его”. При этом информативность  всего сообщения нисколько не снижается, а его объем уменьшается. Очевидно, что нет смысла полностью  повторять однажды сказанную  в разговоре фразу несколько  раз. То же самое относится и к  компьютерной информации.

Основная идея алгоритма LZ состоит  в том, что второе и последующие  вхождения некоторой строки символов в сообщение заменяются ссылкой  на ее первое появление в сообщении.

5.3 Алгоритм LZ77

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

В качестве модели данных LZ77 использует “скользящее” по сообщению окно, разделенное  на две неравные части. Первая, большая  по размеру, включает уже просмотренную  часть сообщения. Вторая, намного  меньшая, является буфером, содержащим еще не закодированные символы входного потока. Обычно размер окна составляет несколько килобайтов. Буфер намного  меньше, обычно не более ста байтов. Алгоритм пытается найти в словаре  фрагмент, совпадающий с содержимым буфера.

Рассмотрим работу LZ77 на примере  сообщения, приведенного в таблице:

Скользящее окно в алгоритме LZ77
for (i=0; i<MAX-1; i++)\r for (j=i+l; j	<MAX; j++)\    r
Обработанная часть сообщения (словарь)	Буфер

Алгоритм LZ77 выдает коды, состоящие  из трех элементов:

• смещение в словаре относительно его начала подстроки, совпадающей с содержимым буфера;
• длина подстроки;
• первый символ в буфере, следующий за подстрокой.

В нашем примере, просматривая словарь, алгоритм обнаружит, что совпадающей  подстрокой будет “<МАХ”, в словаре она расположена по смещению 14, имеет длину 4 символа, а следующим символом в буфере является ';'. Таким образом, выходной код будет представлять собой тройку <14, 4, ';'>.

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

Если совпадение не обнаружено, то алгоритм выдает код <0, 0, первый символ в буфере> и продолжает свою работу. Хотя такое решение неэффективно, оно гарантирует, что алгоритм сможет закодировать любое сообщение.

УПРОЩЕННЫЙ АЛГОРИТМ LZ77

пока (буфер не пуст)

  найти наиболее длинное  соответствие (позиция_начала, длина)

  в обработанной_части_сообщения и в буфере;

  если (длина > минимальной_длины ), то

    вывести в кодированные  данные пару (позиция _начала, длина);

  иначе

    вывести в кодированные  данные первый символ буфера;

  изменить указатель  на начало буфера и продолжить.

Декодирование в LZ77 еще проще, так  как не нужно осуществлять поиск в словаре.

Проблемы LZ77

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

Быстродействие и кодера, и декодера зависит от того, как реализовано  “скольжение” окна по содержимому  сообщения. Рационально было бы для  работы с окном пользоваться кольцевым  буфером, организованным на физически  сплошном участке памяти, а не реальным сдвигом содержимого окна. Хотя для  поддержания кольцевого буфера необходимы дополнительные затраты на сохранение целостности индексов в нем, в  целом это дает очень существенный выигрыш потому, что отсутствует  постоянное сдвигание большого блока  памяти. Если размер кольцевого буфера равен степени двойки, то стандартная  для кольцевого буфера операция “смещение  по модулю размер”, может быть заменена побитовой логической операцией, что  еще больше повышает эффективность.

Помимо проблем с быстродействием, у алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4Кб, а буфер — 16 байтов, то код <0, 0, символ> будет занимать 3 байта. Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма.

5.4 Алгоритм LZSS

Алгоритм LZSS получил свое название по именам своих разработчиков: Lempel, Ziv, Storer, Szimansky. Существенный вклад в развитие алгоритма внес Т. С. Bell. LZSS является развитием LZ77 и стремится избавиться от недостатков своего предшественника. LZSS отличается от LZ77 тем, как поддерживается скользящее окно и какие коды выдает компрессор.

LZSS, помимо собственно окна с  содержимым сообщения, поддерживает  двоичное дерево для ускорения  поиска совпадения. Каждая подстрока,  покидающая буфер, добавляется  в дерево поиска, а подстрока,  покидающая словарь, удаляется  из дерева. Такая организация  модели данных позволяет добиться  существенного увеличения скорости  поиска совпадения, которая, в  отличие от LZ77, становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя в скорости сжатия.

Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина>. Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения

Модель данных

Как и в LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности “скольжения” окна по содержимому сообщения доступ к нему организован как к кольцевому, и размер окна кратен степени 2.

Дерево поиска представляет собой  двоичное лексикографически упорядоченное  дерево. Каждый узел в дереве соответствует  одной подстроке словаря и  содержит ссылки на родителя и двух потомков: “большего” и “меньшего” в смысле лексикографического сравнения  символьных строк.

Кодер LZSS

Инициализация 
Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.

Основной цикл работы

Алгоритм последовательно выполняет  следующие действия:

1. кодирует содержимое буфера;
2. считывает очередные символы в буфер, удаляя при необходимости наиболее “старые” строки из словаря;
3. вставляет в дерево новые строки, соответствующие считанным символам.

Завершение работы 
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ “КОНЕЦ ФАЙЛА” после того, как он обработал все символы сообщения.