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

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

Ловушка

К несчастью прекрасный, простой  алгоритм распаковки, является все  таким слишком простым. В алгоритме  сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и  уже определенную в таблице, а  просматриваемый входной поток  содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик  получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице  с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит следующим образом:

Входная строка : ...JOEYNJOEYNJOEY...
Вход(символы)	Выход(коды)	Новые коды и соотв. строки
JOEYN	288 = JOEY	300 = JOEYN
A	N	301 = NA
...	...	...
JOEYNJ	300 = JOEYN	400 = JOEYNJ
JOEYNJO	400	401 = JOEYNJO

Когда распаковщик просматривает  входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает  специальные действия для еще  неопределенных кодов. В примере  на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет  значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД

вывести СТАРЫЙ_КОД

СИМВОЛ = СТАРЫЙ_КОД

WHILE входной поток не  пуст DO

  читать НОВЫЙ_КОД

  IF NOT в таблице перевода  НОВЫЙ_КОД THEN

    СТРОКА = перевести  СТАРЫЙ_КОД

    СТРОКА = СТРОКА+СИМВОЛ

  ELSE

    СТРОКА = перевести  НОВЫЙ_КОД

  END of IF

  вывести СТРОКУ

  СИМВОЛ = первый символ  СТРОКИ

  добавить в таблицу  перевода СТАРЫЙ_КОД+СИМВОЛ

  СТАРЫЙ_КОД = НОВЫЙ_КОД

END of WHILE

Результаты

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

Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях "сжатый" файл может превосходить по своим размерам исходный текст.

5.7 Алгоритм LZM

LZM представляет собой комбинацию  алгоритмов LZSS и RLE. Он рассчитан на сжатие блоков информации длиной до 8 Кб. Для работы ему необходим внутренний буфер размером 8 Кб. Основной стратегией разработки алгоритма было обеспечить приемлемое сжатие при максимальном быстродействии и минимальных затратах памяти.

Коды LZM

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

Маркер “00” размером в 1 байт означает, что за ним следуют незакодированные символы входного сообщения. Поле “длина” может содержать значение от 1 до 63, соответствующее количеству незакодированных символов. Если это значение равно 0, то следующие два байта содержат пару <количество_повторов, символ>, заменяющую повторяющий символ сообщения, а незакодирован¬ные символы отсутствуют.

Маркер “01” размером в 2 байта состоит из трех полей. Первое 2-битовое поле содержит количество (от 0 до 3) незакодированных символов, следующих сразу за маркером. Второе 3-битовое поле — длину совпадения (от 3 до 10 символов), а третье 9-битовое поле содержит смещение назад (!) от текущей позиции (от 0 до 511).

Маркер “10” размером в 2 байта состоит из двух полей. Первое 2-битовое поле содержит длину совпадения (от 3 до 6 символов), а второе 12-битовое поле — смещение назад от текущей позиции.

Маркер “11” размером в 3 байта состоит из трех полей. Первое 4-битовое поле содержит количество (от 0 до 15) незакодированных символов, следующих сразу за маркером. Второе и третье поля содержат пару <смещение, длина>, причем смещение может принимать значение от 0 до 8191, а длина — от 0 до 31.

Вместо обычного для LZSS набора <0, незакодированный байт>, <1, 12 битов — смещение, 4 бита — длина совпадения> используется несколько аналогичных, но более сложных кодов. Это позволяет добиться лучших результатов сжатия на коротких сообщениях.

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

В отличие от алгоритма LZ77, в LZM для поиска повторяющихся подстрок сообщения используется хеш-таблица смещений строк относительно начала сжимаемого блока. Размер таблицы — 4096 значений. Индексом при входе в таблицу является 12-битовый хеш-код, получаемый по очередным трем символам сжимаемого сообщения. Для получения хеш-кода используется широко известная функция хеширования символьных строк.

ХЕШ_КОД = О

ХЕШ_КОД = Первый_Символ

ХЕШ_КОД = ХЕШ_КОД “ 2 (* Побитовый  сдвиг *)

ХЕШ_КОД = ХЕШ_КОД хоr ВторойСимвол

ХЕШ_КОД = ХЕШ_КОД “ 2

ХЕШ_КОД = ХЕШ_КОД хоr ТретийСимвол

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

Кодер LZM

Схема работы кодера LZM может быть описана следующим образом.

1. Кодер пытается определить, возможно ли закодировать текущий фрагмент с помощью кодирования повторов (RLE). Если да, то кодер выдает соответствующий маркер (или их комбинацию), сбрасывает счетчик незакодированных символов, обновляет текущее смещение и переходит к пункту 1.
2. Кодер строит значение хеш-функции для текущего смещения от начала сообщения, выбирает из таблицы по хеш-значению смещение подстроки с аналогичным значением хеш-функции от начала сообщения, заменяет этот элемент таблицы на текущее смещение. Затем ко¬дер пытается определить длину совпадения двух подстрок: с текущим смещением и со смещением из таблицы. Если длина совпадения больше 2, то кодер выдает наиболее подходящий маркер (или их комбинацию) и сбрасывает счетчик незакодированных символов. Иначе кодер увеличивает счетчик пропущенных символов. Кодер обновляет текущее смещение и переходит к пункту 1. В силу того, что длина сжимаемого сообщения известна, вопрос об остановке кодера не вызывает сложностей.

Декодер LZM

Алгоритм работы декодера очень  прост.

1. Прочитать один байт. В зависимости от пре¬фикса прочитать весь маркер.
2. Прочитать из маркера количество незакодированных символов, смещение и длину совпадения. Если это маркер “00” и количество незакодированных символов равно 0, то выдать соответствующее количество одинаковых символов в выходной буфер. Иначе:
• скопировать необходимое количество очередных символов в выходной поток (несжатая информация);
• скопировать указанное количество символов выходного потока, находящихся на указанном смещении от текущей позиции, в выходной поток. (Декодирование повторяющейся подстроки сообщения.)

Перейти к пункту 1.

Сравнение с LZSS: плюсы и минусы

Когда речь идет об алгоритмах сжатия информации, то нужно очень хорошо отдавать себе отчет в том, что требования к степени сжатия, быстродействию и объему памяти, необходимой для работы алгоритма, являются практически взаимоисключающими. Любая коммерческая программа сжатия информации является тем или иным компромиссом между этими требованиями. Так, алгоритм LZM, выигрывая у LZSS по быстродействию и памяти, проигрывает в степени сжатия. Где именно это происходит? Все дело в разных моделях данных, используемых алгоритмами. LZM не пытается запоминать упорядоченное дерево под¬строк сообщения, как LZSS, а только таблицу их хеш-кодов. Это и дает LZM существенное преимущество по памяти и скорости. Но, с другой стороны, для модели данных LZM все подстроки с одинаковым значением хеш-функции просто неразличимы, то есть модель сообщения LZM менее точна, чем у LZSS. Как раз это и приводит к уменьшению степени сжатия и к существенному выигрышу в скорости работы.

Заключение

LZM — это компактный и очень  быстрый алгоритм, который дает  хорошее сжатие, и ориентирован на использование в драйверах устройств. По своим суммарным характеристикам он уступает разве что алгоритму LZS фирмы Stac Electronics. Так, например, на файлах различных СУБД и картинках (BMP) сжатие достигает 5:1, текстовых файлах — 2: 1, текстах программ — 3:1, выполняемых файлах — 1,5:1.

5.8 Алгоритм LZB

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

Первой составляющей указателя  есть позиция начала фразы от начала окна. LZB работает относительно этой компоненты. Первоначально, когда символов в  окне 2, размер равен 1 биту, потом, при 4-х  символах в окне, возрастает до 2 битов, и т.д., пока окно не станет содержать N символов. Для кодирования второй составляющей (длины фразы) указателя, LZB применяет схему кодов переменной длины Элиаса. Поскольку этот код может представлять фразу любой длины, то никаких ограничений на нее не накладывается.

5.9 Алгоритм LZH

Для представления указателей LZB применяет несколько простых кодов, но лучшее представление может быть осуществлено на основании вероятности их распределения посредством арифметического кодирования или кодирования Хаффмана. LZH-система подобна LZSS, но применяет для указателей и символов кодирование Хаффмана. Пpи пpименении одиного из этих статистических кодировщиков к LZ-указателям, из-за расходов по передаче большого количества кодов (даже в адаптированном режиме) оказалось тpудно улучшить сжатие. Кроме того, итоговой схеме не хватает быстроты и простоты LZ-метода.

5.10 Алгоритм LZC

LZC - это схема, применяемая программой COMPRESS, используемой в системе  UNIX. Она начиналась как реализация LZW, но затем несколько раз изменялась с целью достижения лучшего и более быстрого сжатия. Результатом явилась схема с высокими характеристиками.

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

5.11 Алгоритм LZT

LZT основан на LZC. Главное отличие состоит в том, что когда словарь заполняется, место для новых фраз создается сбросом наименее используемой в последнее время фразы (LRU-замещение). Это эффективно осуществляется поддержанием саморегулируемого списка фраз, организованного в виде хеш-таблицы. Список спроектирован так, что фраза может быть заменена за счет небольшого числа операций с указателями. Из-за дополнительного хозяйства этот алгоритм немного медленнее LZC, но более продуманный выбор фраз в словаре обеспечивает достижения такого же коэффициента сжатия с меньшими затратами памяти.

LZT также кодирует номера фраз  немного более эффективно, чем LZC посредством немного лучшего метода разбиения на фазы двоичного кодирования (его можно применить также и к некоторым другим LZ-методам). При этом кодировщику и декодировщику требуются небольшие дополнительные затраты, являющиеся незначительными по сравнению с задачей поиска и поддержания LRU-списка.