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

5.12 Алгоритм LZMV

Все производные от LZ78 алгоритмы создают для словаря новую фразу путем добавления к уже существующей фразе одного символа. Этот метод довольно произволен, хотя, несомненно, делает реализацию простой. LZMV использует другой подход для формирования записей словаря. Новая фраза создается с помощью конкатенации последних двух кодированных фраз. Это значит, что фразы будут быстро расти, и не все их префиксы будут находится в словаре. Редко используемые фразы, как и в LZT, при ограниченном размере словаря будут удаляться, чтобы обеспечить адаптивный режим работы. Стратегия быстрого конструирования фразы LZMV достигает лучшего сжатия, по сравнению с наращиванием фразы на один символ за раз.

5.13 Алгоритм LZJ

LZJ представляет собой новый  подход к LZ-сжатию, заслоняющий значительную брешь в строю его вариантов. Первоначально предполагаемый словарь LZJ содержит каждую уникальную строку из уже просмотренной части текста, ограниченную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пределах от 0 до H-1 (годится H около 8192). Для гарантированной кодировки каждой строки, в словарь включается множество исходных символов. Когда словарь полон, он сокращается удалением строки, появлявшейся во входе только один раз.

Кодирование и декодирование LZJ выполняется  на основе структуры дерева цифрового  поиска для хранения подстрок из уже  закодированной части текста. Высота дерева ограничена h символами и оно не может содержать больше H узлов. Строка распознается по уникальному номеру, присвоенному соответствующему ей узлу. Процесс декодирования должен поддерживать такое же дерево, методом преобразования номера узла обратно к подстроке, совершая путь вверх по дереву.

5.14 Алгоритм LZFG

LZFG, предложенный Фиалой и Грини – это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и декодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя разными указателями устраняются хранением кодированного текста в виде дерева цифрового поиска и помещением в выходной файл позиции в дереве.

LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобранной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по существу неограниченной длины, показывающую как много символов должно быть скопировано. Закодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов используются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.

5.15 Унарное кодирование

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

Однако, существуют коды, для которых задача определения длины легко решается (так называемые неравномерные коды со свойством однозначного декодирования). Например, унарный код (в двоичной системе), где:

“о”-1

“а”-01

“и”-001

...

“щ”-00....1

т.е. для самой частой буквы длина  кода составляет 1 бит, для самой  редкой - 33 бита (32 нуля и единица). Этот код очень прост, но далеко не эффективен. Однако, он может пригодиться для построения кодов целых переменной длины (Variable Length Integers (VLI) codes). VLI-коды состоят из двух частей: сначала следует унарный код, определяющий группу чисел определенной длины, а затем само число указанной длины. Таким образом, унарный код выполняет роль префикса, указывающего какой длины будет следующее число. Для записи VLI-кодов используют три числа: (start, step, stop), где start определяет начальную длину числа, step – приращение длины для следующей группы, stop – конечную длину.

Например, код (3,2,9) задает четыре группы чисел:0ххх – числа от 0 до 7, группа 0,

10ххххх – числа от 8 до 39, группа 1,

110ххххххх – числа от 40 до 167, группа 2,

111ххххххххх – числа от 168 до 679, группа 3.

Унарный код для n-ой группы – n единиц, затем ноль; для последней группы – только n единиц, так как это  не вносит неопределенности. Размер числа  из n-ой группы равен start+n*step. VLI-коды удобно применять для кодирования монотонных источников, для которых вероятность появления меньших чисел выше, чем больших. При отсутствии кодирования любое число представлялось бы десятью битами.

5.16 Метод Хафмана

5.16.1 Идея метода

Метод сжатия информации на основе двоичных кодирующих деревьев был предложен Д. А. Хаффманом в 1952 году задолго до появления современного цифрового компьютера. Обладая высокой эффективностью, он и его многочисленные адаптивные версии лежат в основе многих методов, используемых в алгоритмах кодирования.

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

5.16.2 Алгоритм

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в ожидаемое сообщение.
2. Выбираются 2 свободных узла дерева с наименьшими весами.
3. Создается родитель с весом равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а двое его потомков удаляются из этого списка.
5. Одной дуге выходящей их родителя ставится в соответствие бит 1, другой – бит 0.
6. 6. Далее пункты повторяются, начиная со второго, до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

5.16.3 Кодирование  Хаффмана

Допустим у нас есть таблица частот:

15	7	6	6	5
A	B	C	D	E

На первом шаге из листьев дерева выбираются два с наименьшими  весами – D и E. Они присоединяются к  новому узлу-родителю, вес которого устанавливается в 5+6=11. Затем узлы D и E удаляются из списка свободных. Узел D соответствует ветви 0 родителя, узел E – ветви 1. На следующем шаге то же происходит с узлами B и C, так  как теперь эта пара имеет самый  меньший вес в дереве. Создается  новый узел с весом 13, а узлы B и C удаляются из списка свободных. На следующем шаге "наилегчайшей" парой оказываются узлы B/C и D/E. Для  них еще раз создается родитель, теперь уже с весом 24. Узел B/C соответствует  ветви 0 родителя, D/E – ветви 1. На последнем  шаге в списке свободных остается только 2 узла – это A и узел (B/C)/(D/E). В очередной раз создается  родитель с весом 39, и бывшие свободные  узлы присоединяются к разным его  ветвям. Поскольку свободным остается только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Чтобы определить код для каждого  из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при  перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного  символа, записанная в обратном порядке. Для данной таблицы символов коды Хаффмана будут выглядеть следующим  образом:

A	0
B	100
C	101
D	110
E	111

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

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

5.16.4 Адаптивное сжатие Хаффмана

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

ИнициализироватьМодель();

Пока не конец сообщения

  Символ = ВзятьСледующийСимвол();

  Закодировать(Символ);

  ОбновитьМодельСимволом(Символ);

Конец пока;

Декодер в адаптивной схеме работает аналогичным образом:

ИнициализироватьМодель();

Пока не конец сжатой информации

  Символ = РаскодироватьСледующий();

  ВыдатьСимвол(Символ);

  ОбновитьМодельСимволом(Символ);

Конец пока;

Схема адаптивного кодирования/декодирования  работает благодаря тому, что при  кодировании, и при декодировании  используются одни и те же процедуры "ИнициализироватьМодель" и "ОбновитьМодельСимволом" И компрессор, и декомпрессор начинают с "пустой" модели (не содержащей информации о сообщении) и с каждым просмотренным символом обновляют ее одинаковым образом.

5.16.5 Адаптивное кодирование Хаффмана

В создании алгоритма адаптивного  кодирования Хаффмана наибольшие сложности  возникают при разработке процедуры ОбновитьМодельСимволом(); можно было бы просто вставить внутрь этой процедуры полное построение дерева Хаффмана. В результате мы получили бы очень медленный алгоритм сжатия, так как построение дерева – это слишком большая работа и производить ее при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее дерево так, чтобы отобразить обработку нового символа.

Упорядоченное Дерево

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

Примем без доказательства утверждение  о том, что двоичное дерево является деревом кодирования Хаффмана тогда и только тогда, когда оно удовлетворяет свойству упорядоченности. Сохранение свойства упорядоченности в процессе обновления дерева позволяет нам быть уверенным в том, что двоичное дерево, с которым мы работаем, – это дерево кодирования Хаффмана и до, и после обновления веса у листьев дерева. Обновление дерева при считывании очередного символа сообщения состоит из двух операций. Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса у потомков. Этот процесс продолжается до тех пор, пока мы не доберемся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ.

Вторая операция – перестановка узлов дерева – требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный  вес узла стал больше, чем вес  следующего по порядку узла. Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то наше дерево перестанет быть деревом Хаффмана. Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве. При этом родители каждого из узлов тоже изменяются. На этом операция перестановки заканчивается. После перестановки операция увеличения веса узлов продолжается дальше.

Следующий узел, вес которого будет  увеличен алгоритмом, – это новый  родитель узла, увеличение веса которого вызвало перестановку. Предположим, что символ A встретился в сообщении  еще два раза подряд. Обратите внимание, как обновление дерева кодирования  отражается на длине кодов Хаффмана для входящих в данное сообщение символов. В целом алгоритм обновления дерева может быть записан следующим образом: