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

Добавление новой строки в дерево

Вся работа по поиску расположения и  установлению длины максимального  совпадения содержимого словаря  с буфером происходит в процессе добавления в дерево новой строки.

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

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

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

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

Удаление строки из дерева

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

Декодер LZSS

Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.

Декодер читает один бит сжатой информации и решает - это символ или пара <смещение, длина>. Если это символ, то следующие 8 битов выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.

5.5 Алгоритм LZ78

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

Например, строка "aaabbabaabaaabab" делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс текущий символ. Например, последние три символа кодируются как фраза номер 4 ("ba"), за которой следует символ "b". Фраза номер 0 - пустая строка.

LZ78-кодирование  строки 'aaabbabaabaaabab'; запись (i,a) обозначает копирование цепочки i перед символом a.
Вход:	a	aa	b	ba	baa	baaa	bab
№ цепочки:	1	2	3	4	5	6	7
Выход:	(0,a)	(1,a)	(0,b)	(3,a)	(4,a)	(5,a)	(4,b)

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

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

Важным теоретическим свойством LZ78 является то, что пpи пpозводстве исходного текста стационарным эргодическим источником, сжатие является приблизительно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией источника. Источник является эргодическим, если любая производимая им последовательность все точнее характеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текстов. Однако, оптимальность появляется когда размер ввода стремится к бесконечности, а большинство текстов значительно короче! Она основана на размере явного символа, который значительно меньше размера всего кода фразы. Т.к. его длина 8 битов, он будет занимать всего 20% вывода при создании 2⁴⁰ фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.

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

Обычно, при инициализации словарь  заполняется исходными (элементарными) фрагментами – всеми возможными значениями байта от 0 до 255. Это гарантирует, что при поступлении на вход очередной  порции данных будет найден в словаре  хотя бы однобайтовый фрагмент.

Алгоритм LZ78 резервирует специальный  код, назовем его «Reset», который вставляется в упакованные данные, отмечая момент сброса словаря. Значение кода Reset примем равным 256.

Таким образом, при начале кодирования  минимальная длина кода составляет 9 бит. Максимальная длина кода зависит  от объема словаря – количества различных фрагментов, которые туда можно поместить. Если объем словаря  измерять в байтах (символах), то очевидно, что максимальное количество фрагментов равно числу символов, а, следовательно, максимальная длина кода равна log2 (объем  словаря в байтах).

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

Таким образом, алгоритм упаковки и  распаковки методом LZ78 весьма прост. Основную проблему при реализации этого метода представляет устройство словаря.

Очевидно, что чем больше словарь, тем (при прочих равных условиях) большую  степень сжатия можно достичь. С  другой стороны, важным практическим моментом является скорость упаковки, этот параметр тоже зависит от устройства словаря. Основные операции при упаковке: 1) поиск в словаре фрагмента; 2) вставка в словарь новых фрагментов. Необходимо, чтобы эти две операции были максимально быстрыми.

5.6 Алгоритм LZW

Как и LZ77, алгоритм LZ78 был опубликован в сугубо научном журнале и сначала воспринимался читателями скорее как абстракция, нежели то, что можно положить в основу программного продукта. Так было до 1984 года, когда Терри Уэлч (Terry Welch) опубликовал свою работу. Модификация алгоритма LZ78, предложенная Уэлчем, получила название LZW (Lempel-Ziv-Welch).

Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это  делается без какого-либо анализа  входного текста. Вместо этого при  добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они  должны содержать больше бит, чем  единичный символ. Первые 256 кодов (когда  используются 8-битные символы) по умолчанию  соответствуют стандартному набору символов. Остальные коды соответствуют  обрабатываемым алгоритмом строкам.

Сжатие

Алгоритм LZW-сжатия в простейшей форме  приведен ниже. Каждый раз, когда генерируется новый код, новая строка добавляется  в таблицу строк. LZW постоянно  проверяет, является ли строка уже известной, и, если так, выводит существующий код  без генерации нового.

Процедура LZW-сжатия

СТРОКА = очередной символ из входного потока

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

  СИМВОЛ = очередной символ  из входного потока

  IF СТРОКА+СИМВОЛ в  таблице строк THEN

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

  ELSE

    вывести в выходной  поток код для СТРОКА

    добавить в  таблицу строк СТРОКА+СИМВОЛ

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

  END of IF

END of WHILE

вывести в выходной поток  код для СТРОКА

Рассмотрим пример для демонстрации алгоритма. Входная строка:

/WED/WE/WEE/WEB/WET

Входная строка является кратким списком  английских слов, разделенных символом "/". Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки "/W" в таблице. Когда он не находит эту строку, то генерирует код для "/" и добавляет в таблицу строку "/W". Т.к. 256 символов уже определены для кодов 0 - 255, то первой определенной строке может быть поставлен в соответствие код 256. После этого система читает следующую букву ("E"), добавляет вторую подстроку ("WE") в таблицу и выводит код для буквы "W".

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая  из прочитанных символов "/" и "W", не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка: /WED/WE/WEE/WEB/WET
Вход (символы)	Выход (коды)	Новые коды и соответствующие  строки
/W	/	256 = /W
E	W	257 = WE
D	E	258 = ED
/	D	259 = D/
WE	256	260 = /WE
/	E	261 = E/
WEE	260	262 = /WEE
/W	261	263 = E/W
EB	257	264 = WEB
/	B	265 = B/
WET	260	266 = /WET
<EOF>	T	—

Как вы можете заметить, эта таблица  быстро заполняется, т.к. новая строка добавляется в таблицу каждый раз, когда генерируется код. В этом явно вырожденном примере было выведено пять закодированных подстрок и семь символов. Если использовать 9-битные коды для вывода, то 19-символьная входная  строка будет преобразована в 13.5-символьная выходную строку. Конечно, этот пример был выбран только для демонстрации. В действительности сжатие обычно не начинается до тех пор, пока не будет  построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт.

Распаковка

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного  восстановления входного потока. Одной  из причин эффективности LZW-алгоритма  является то, что он не нуждается  в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма  сжатия. Это возможно потому, что  алгоритм сжатия выводит СТРОКОВУЮ  и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

Алгоритм распаковки представлен  ниже. В соответствии с алгоритмом сжатия, он добавляет новую строку в таблицу строк каждый раз, когда  читает из входного потока новый код. Все, что ему необходимо сделать  в добавок - это перевести каждый входной код в строку и переслать ее в выходной поток.

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

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

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

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

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

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

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

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

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

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

END of WHILE

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

Входные коды: / W E D 256 E 260 261 257 B 260 T
Вход	СТАРЫЙ КОД	СТРОКА	СИМВОЛ	Новый вход таблицы
НОВЫЙ КОД	—	Выход	—	—
/	/	/	—	—
W	/	W	W	256 = /W
E	W	E	E	257 = WE
D	E	D	D	258 = ED
256	D	/W	/	259 = D/
E	256	E	E	260 = /WE
260	E	/WE	/	261 = E/
261	260	E/	E	262 = /WEE
257	261	WE	W	263 = E/W
B	257	B	B	264 = WEB
260	B	/WE	/	265 = B/
T	260	T	T	266 = /WET