2015-09-07
752
Словарные методы основаны на применении динамических словарей. Эти методы базируются на алгоритмах LZ77 и LZ78, предложенных Лемпелем Зивом. В основе словарных методов лежат следующие идеи:
1. каждая очередная закодированная последовательность символов добавляется к ранее закодированным символам таким образом, что вместе с ними она образует разложение всей переданной и принятой информации на несовпадающие между собой слова;
2. слова хранятся в памяти и используются в дальнейшем в качестве словаря;
3. кодирование осуществляется при помощи указателей на слова из сформированного словаря;
4. кодирование является динамической процедурой, ориентированной на блоки символов.
При реализации методов Лемпеля-Зива как правило используется скользящее окно, состоящее из словаря и упреждающего буфера.
В результате сжатия файла с помощью метода LZ77 формируется последовательность вида
á A, L, S ñ,
где A – относительный адрес в словаре, L – количество совпадающих символов, S – символ из буфера, который отличается от продолжения слова в словаре. При этом код á–1, 0, S ñ (или á0, 0, S ñ) означает, что в словаре ничего не найдено.
|
|
|
Алгоритм LZ77 работает следующим образом. Сначала упреждающий буфер заполняется символами из начала сжимаемого файла. Затем осуществляется поиск в словаре слова, максимально совпадающего со словом в начале упреждающего буфера. После этого формируется и выдается код. После выдачи кода L + 1 символов из начала упреждающего буфера переписываются в словарь, оставшиеся символы смещаются в начало, а на их место записываются символы из файла. Так как размер словаря ограничен, то из его начала часть символов может удаляться со смещением остальных на соответствующее число позиций.
Пусть, например, необходимо закодировать последовательность символов
aaaabaabbb EOF
методом LZ77 с использованием словаря и упреждающего буфера, рассчитанных на 8 и 4 символов соответственно. Процесс кодирования показан в таблице 6.5.
Таблица 6.5
Пример кодирования по методу LZ77
| № | Словарь | Упреждающий буфер | Код | ||||||||||
| á–1, 0, a ñ | |||||||||||||
| - | - | - | - | - | - | - | - | a | a | a | a | ||
| á0, 1, a ñ | |||||||||||||
| a | - | - | - | - | - | - | - | a | a | a | b | ||
| á0, 1, b ñ | |||||||||||||
| a | a | a | - | - | - | - | - | a | b | a | a | ||
| á0, 2, b ñ | |||||||||||||
| a | a | a | a | b | - | - | - | a | a | b | b | ||
| á4, 1, b ñ | |||||||||||||
| a | a | a | a | b | a | a | b | b | b | EOF | - | ||
| á–1, 0, EOFñ | |||||||||||||
| a | a | b | a | a | b | b | b | EOF | - | - | - | ||
| - | |||||||||||||
| a | b | a | a | b | b | b | EOF | - | - | - | - |
Метод LZ78 отличается от LZ77 тем, что в каждой позиции словаря хранятся слова. Поэтому в выходном коде количество совпадающих символов L отсутствует, т.е. код имеет вид
|
|
|
á A, S ñ,
где A – адрес слова в словаре, совпадающего со словом в начале упреждающего буфера, S – символ из буфера, который отличается от продолжения слова в словаре. При этом код á–1, S ñ означает, что в словаре ничего не найдено. После выдачи кода в словарь добавляется слово, начало которого представляет собой слово из словаря по адресу A (A ≠ –1), а окончание – символ S.
Процесс кодирования по методу LZ78 последовательности символов, рассмотренной в примере применения метода LZ77, показан в таблице 6.6.
Таблица 6.6
Пример кодирования по методу LZ78
| № | Словарь (позиция: слово) | Упреждающий буфер | Код |
| - | aaaa | á–1, a ñ | |
| 0: a | aaab | á0, a ñ | |
| 0: a 1: aa | abaa | á0, b ñ | |
| 0: a 1: aa 2: ab | aabb | á1, b ñ | |
| 0: a 1: aa 2: ab 3: aab | bb EOF | á–1, b ñ | |
| 0: a 1: aa 2: ab 3: aab 4: b | b EOF | á4, EOFñ | |
| 0: a 1: aa 2: ab 3: aab 4: b 5: b EOF | - | - |
Одной из практических модификаций LZ77 является алгоритм LZSS, который отличается от LZ77 тем, как поддерживается скользящее окно и какие коды выдает кодер. LZSS, помимо собственно окна с содержимым сообщения, поддерживает двоичное дерево для ускорения поиска совпадения. Каждая подстрока, покидающая буфер, добавляется в дерево поиска, а подстрока, покидающая словарь, удаляется из дерева. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от LZ77, становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. На выходе кодера формируются либо пары á A, L ñ, либо незакодированные символы. Для их различения кодер LZSS использует однобитовый префикс.
Как и в LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. Доступ к нему организован как к кольцевому буферу, а размер кратен степени 2. Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух детей: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.
Для того чтобы кодер LZSS мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера. После этого алгоритм последовательно выполняет следующие действия:
1) кодирует содержимое буфера;
2) считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря;
3) вставляет в дерево новые строки, соответствующие считанным символам.
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ конца файла после того, как он обработал все символы сообщения.
Вся работа по поиску расположения и установлению длины максимального совпадения содержимого словаря с буфером происходит в процессе добавления в дерево новой строки. При добавлении строки в дерево алгоритм последовательно перемещается от корня дерева к его листу, каждый раз осуществляя лексикографическое сравнение новой строки и узла дерева. В зависимости от результата сравнения выбирается больший или меньший ребёнок этого узла и запоминается длина совпадения строк и положение текущего узла. Если в результате сравнения оказывается, что содержимое буфера и строка, на которую ссылается текущий узел, в точности совпадают, то ссылки в текущем узле обновляются так, чтобы они указывали на буфер, и процедура добавления строки в дерево завершается. Если ребенок текущего узла, выбранный для очередного шага, отмечен как несуществующий, остается заполнить его соответствующей ссылкой и завершить работу.
|
|
|
При удалении узла из дерева возможны два варианта. Если узел имеет не более одного ребенка, то удаление узла осуществляется простым исправлением ссылок «родитель – ребенок». Если узел имеет двоих детей, то необходимы другие действия. Для этого найдем следующий меньший узел в дереве, удалим его из дерева и заменим им текущий удаляемый узел. Следующий меньший узел находится выбором меньшего ребенка и последующим перемещением от него по дереву до листа по большим ветвям.
При восстановлении данных, декодер читает один бит сжатой информации и определяет, что следует далее. Если далее следует символ, то следующие 8 битов выдаются как раскодированный символ и помещаются в скользящее окно. Если же далее следует пара á A, L ñ, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Декодирование заканчивается при обнаружении символа конца файла.
Примером практической модификации алгоритма LZ78 является алгоритм LZW. Кодер LZW никогда не выдает сами символы сжимаемого сообщения, только коды фраз. Он построен вокруг таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины вида á A ñ. Таблица обладает так называемым свойством предшествования, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа S, фраза w тоже содержится в словаре.
Очевидно, что декодер LZW использует тот же словарь, что и кодер, строя его по аналогичным правилам при восстановлении сжитого сообщения. Каждый считываемый код разбивается с помощью словаря на предшествующую фразу w и символ S. Затем рекурсия продолжается для предшествующей фразы w до тех пор, пока она не окажется кодом одного символа, что и завершает декомпрессию этого кода. Обновление словаря происходит для каждого декодируемого кода, кроме первого. После завершения декодирования кода его последний символ, соединенный с предыдущей фразой, добавляется в словарь. Новая фраза получает то же значение кода (позицию в словаре), что присвоил ей кодер. Так шаг за шагом декодер восстанавливает тот словарь, который построил кодер.
|
|
|
Отметим, что словарные методы являются асимметричными методами, поскольку при восстановлении данных не нужно выполнять поиск: ссылка на словарь содержится непосредственно в коде. Например, для LZ77 декодер по адресу A и количеству совпадающих символов L находит слово в словаре, добавляет к нему символ S и выдает на выход.
