2.4.2. Структура словаря LZW

До этого момента считалось, что словарем LZW служит массив из строк переменной длины. Чтобы понять, почему специальное дерево будет являться лучшей структурой для словаря, следует напомнить работу кодера. Он считывает символы и добавляет их в строку I до тех пор, пока I находится в словаре. В некоторый момент строка Iх в словаре не обнаруживается, и тогда строка Iх помещается в словарь. Значит, при добавлении новых строк в словарь поступает всего один новый символ х. Это предложение можно перефразировать еще так: для каждой словарной строки в словаре найдется «родительская» строка, которая короче ровно на один символ.

Поэтому для наших целей хорошим выбором будет структура дерева, которая уже использовалось в LZ78, при построении которого добавление новых строк Iх делается добавлением всего одного нового символа х. Основная проблема состоит в том, что каждый узел дерева LZW может иметь много потомков (дерево не двоичное, а -ичное, где  - это объем алфавита). Представим себе узел буквы а с номером 97. В начале у него нет потомков, но если к дереву добавится строка ab, то у а появится один потомок. Если позже добавится новая строка, скажем, ае, то потомков станет два, и так далее. Значит, дерево следует сконструировать так, чтобы каждый узел в нем мог бы иметь любое число потомков, причем без резервирования дополнительной памяти для них заранее.

Один путь конструирования такой структуры данных это построение дерева в виде массива узлов, в котором каждый узел является структурой из двух полей: символа и указателя на узел родителя. В самом узле нет указателей на его потомков. Перемещение вниз по дереву от родителя к потомку делается с помощью процесса хеширования (перемешивания или рандомизации), в котором указатели на узлы и символы потомков перемешиваются некоторой функцией для создания новых указателей.

Предположим, что строка abc уже была на входе, символ за символом, и ее сохранили в трех узлах с адресами 97, 266, 284. Пусть далее за ними следует символ d. Теперь кодер ищет строку abed, а точнее, узел, содержащий символ d, чей родитель находится по адресу 284. Кодер хеширует адреса 284 (указатель на строку abc) и 100 (ASCII код d) и создает указатель на некоторый узел, скажем, 299. Потом кодер проверяет узел 299. Возможны три случая:

1. Этот узел не используется. Это означает строки abed еще нет в словаре и его следует туда добавить. Кодер делает это путем сохранения родительского указателя и ASCII кода 100 в этом узле.

Получаем следующий результат:

Узел
Адрес	97	266	284	299
Содержимое	(-: «а»)	(97: «b»)	(266: «с»)	(284: «d»)
Строки	«а»	«аb»	«аbс»	«abcd»

2. Узел содержит родительский указатель 284 и ASCII код символа d. Это означает, что строка abcd уже есть на дереве. Тогда кодер вводит следующий символ, скажем, е и ищет на дереве строку abcde.

3. В узле хранится что-то другое. Это означает, что хеширование другой пары указателя и кода ASCII дало адрес 299, и узел 299 уже содержит в себе информацию про другие строки. Такая ситуация называется коллизией, и ее можно разрешить несколькими путями. Простейший путь разрешения коллизии это увеличивать адрес до 300, 301,... до тех пор, пока не будет найден пустой узел или узел с содержимым (284: «d»).

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

parent

index

symbol

Пример: Проиллюстрируем эту структуру данных с помощью строки «ababab…» из примера на стр. 103). Словарем будет служить массив diсt, элементами которого являются структуры с тремя полями parent, index, symbol. Мы будем обращаться к этим полям с помощью выражения вида dict[pointer].parent, где pointer - индекс в массиве. Словарь инициализируется двумя символами а и b. (Для простоты мы не будем использовать коды ASCII, но будем считать, что а и b имеют коды 1 и 2.) Первые несколько шагов кодера будут следующими:

Шаг 0: Отметить все позиции, начиная с третьей, как неиспользуемые.

Шаг 1: Первый входной символ а помещается в переменную I. Точнее, переменной I присваивается значение кода l. Поскольку это первый символ входного файла, кодер его не ищет в словаре.

Шаг 2: Второй символ b помещается в переменную J, то есть, J=2. Кодер должен искать в словаре строку ab. Он выполняет операцию pointer:=hash(I,J). Здесь hash(x,у) обозначает некоторую функцию двух аргументов х и у. Предположим, что результатом этой операции будет 5. Поле dict[pointer].index содержит «пусто», так как строки аb нет в словаре. Она туда заносится с помощью следующих действий

dict[pointer].parent:=I;

dict[pointer].index:=pointer;

dict[pointer].symbol:=J;

причем pointer=5. После чего J помещается в I, то есть I=2.

Шаг 3: Третий символ а поступает в J, то есть, J=1. Кодер должен искать в словаре строку bа. Выполняется pointer:=hash(I,J). Пусть результат равен 8. Поле dict[pointer].index содержит «пусто», то есть, строки bа нет в словаре. Добавляем ее в словарь с помощью операций

dict[pointer].parent:=I;

dict[pointer].index:=pointer;

dict[pointer].symbol:=J;

причем pointer=8. После чего J помещается в I, то есть I=1.

Шаг 4: Четвертый символ b переносится в J, теперь J=2. Кодер должен искать в словаре строку ab. Выполняется pointer:=hash(I,J). Мы знаем из шага 2, что результат - 5. Поле dict[pointer].index содержит 5, то есть строка ab имеется в словаре. Значение переменной pointer заносится в I, I=5.

Шаг 5: Пятый символ а попадает в J, теперь J=l. Кодер должен искать в словаре строку aba. Как обычно, выполняется оператор pointer:=hash(I,J). Предположим, что результатом будет 8 (коллизия). Поле dict[pointer].index содержит 8, что хорошо, но поле dict[pointer].parent содержит 2 вместо ожидавшего указателя 5. Произошла коллизия, это означает, что строки aba нет в словаре по адресу 8. Тогда pointer последовательно увеличивается на 1 до тех пор, пока не найдет узел, для которого index=8 и parent=5 или, который пуст. В первом случае aba имеется в словаре, и pointer записывается в I. Во втором случае aba нет в словаре, кодер сохраняет его в узле pointer и записывает в I содержимое J.

Пример: Сделаем процедуру хеширование для кодирования строки символов «alf_eats_alfalfa». Сам процесс кодирования детально разобран в предыдущем примере. Результаты хеширования выбраны произвольно. Они не порождены какой-либо реальной функцией хеширования. Все 12 построенных узлов этого дерева показаны на рис. 2.10.

1. Hash(1,97)=278. По адресу 278 заносится (97,278,1).

2. Hash(f,.108)=266. По адресу 266 заносится (108,266,f).

3. Hash(_,102)=269. По адресу 269 заносится (102,269,_).

4. Hash(e,32)=267. По адресу 267 заносится (32,267,е).

5. Hash(a,101)=265. По адресу 265 заносится (101,265,а).

6. Hash(t,97)=272. По адресу 272 заносится (97,272,t).

7. Hash(s,116)=265. Коллизия! Спускаемся в следующую свободную позицию 268 и заносим (116,265,s).

8. Hash(_,115)=270. По адресу 270 заносится (115,270,_).

9. Hash(a,32)=268. Коллизия! Спускаемся в следующую свободную позицию 271 и заносим (32,268,а).

10. Hash(l,97)=278. По адресу 278 в поле index записано 278, а поле symbol содержит 1. Значит, ничего не надо записывать или сохранять на дереве.

11. Hash(f ,278)=276. По адресу 276 заносится (278,276,f).

12. Hash(a,102)=274. По адресу 274 заносится (102,274,а).

13. Hash(l,97)=278. По адресу 278 в поле index записано 278, а поле symbol содержит 1. Значит, ничего не надо делать.

14. Hash(f,278)=276. По адресу 276 в поле index записано 276, а поле symbol содержит f. Значит, ничего не надо делать.

15. Hash(a,276)=274. Коллизия! Спускаемся в следующую свободную позицию 275, и заносим (276,274,а).

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

Рис. 2.10. Рост дерева LZW для «alf_eats_alfalfa».

Сначала декодер, как и кодер заполняет первые 256 позиций словаря кодами ASCII. Затем он читает указатели из входного файла и использует их для нахождения символов в словаре.

На первом шаге декодирования, декодер вводит первый указатель и использует его для обнаружения в словаре первой строки I. Этот символ записывается в выходной (разжатый) файл. Теперь необходимо записать в словарь строку Iх, но символ х еще не известен; им будет первый символ следующей строки извлекаемой из словаря.

На каждом шаге декодирования после первого декодер читает следующий указатель из файла, использует его для извлечения следующей строки J из словаря и записывает эту строку в выходной файл. Если указатель был равен, скажем, 8, то декодер изучает поле dict[8].index. Если это поле равно 8, то это правильный узел. В противном случае декодер изучает последующие элементы массива до тех пор, пока не найдет правильный узел.

После того, как правильный узел найден, его поле parent используется при проходе назад по дереву для извлечения всех символов строки в обратном порядке. Затем символы помещаются в J в правильном порядке (см. пункт 2 после следующего примера), декодер извлекает последний символ х из J и записывает в словарь строку Iх в следующую свободную позицию. (Строка I была найдена на предыдущем шаге, поэтому на дерево необходимо добавить только один узел с символом х.) После чего декодер перемещает J в I. Теперь он готов для следующего шага.

Для извлечения полной строки из дерева LZW декодер следует по указателям полей parent. Это эквивалентно продвижению вверх по дереву. Вот почему хеширование здесь не нужно.

Пример: В предыдущем примере описана процедура хеширования строки «alf_eats_alfalfa». На последнем шаге в позицию 275 массива был записан узел (276,274,а), а в выходной сжатый файл был записан указатель 275. Когда этот файл читается декодером, указатель 275 является последним обработанным им элементом входного файла. Декодер находит символ а в поле symbol узла с адресом 275, а в поле pernt читает указатель 276. Тогда декодер проверяет адрес 276 и находит в нем символ f и указатель на родительский узел 278. В позиции 278 находится символ 1 и указатель 97. Наконец, в позиции 97 декодер находит символ а и нулевой указатель. Значит, восстановленной строкой будет alfa. У декодера не возникает необходимости делать хеширование и применять поле index.

Нам осталось обсудить обращение строки. Возможны два варианта решения.

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

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

 

2.4.3. LZW в практических приложениях

Опубликование в 1984 году алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода. Наиболее важные из них приведены в [Salomon 2000].