2.4.1. Декодирование LZW

Для того, чтобы понять как работает декодер метода LZW, прежде всего еще раз напомним основные три шага, которые выполняет кодер каждый раз, делая очередную запись в выходной файл: (1) он заносит туда словарный указатель на строку I, (2) сохраняет строку Iх в следующей свободной позиции словаря и (3) инициализирует строку I символом x.

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

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

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

В нашем примере «sir_sid…» первым символом входного файла декодера является указатель 115. Он соответствует строке s, которая извлекается из словаря, сохраняется в I и становится первой строкой, записанной в выходной (разжатый) файл. Следующий указатель 105, поэтому в J заносится строка i, а содержимое J записывается в выходной файл. Первый символ строки J добавляется к переменной I, образуя строку si, которой нет в словаре, поэтому она добавляется в словарь на позиции 256. Содержимое переменной J переносится в переменную I; теперь I равно i. Следующий указатель - 114, поэтому, из словаря извлекается строка r, заносится в J и пишется в выходной файл. Переменная I дополняется до значения ir; такой строки нет в словаре, поэтому она туда заносится под номером 257. Переменная J переписывается в I, теперь I равно r. На следующем шаге декодер читает указатель 32, записывает «_» в файл и сохраняет в словаре строку r_.

Пример: Строка «alf_eats_alfalfa» будет декодироваться с помощью сжатого файла из примера на стр. 100 следующим образом:

1. Читаем указатель 97. Из словаря заносим I=«а» и выводим в файл «а». Строку Ix надо записать в словарь, но х неизвестно.

2. Читаем указатель 108. Из словаря заносим J=«l» и выводим в файл «1». Сохраняем «а1» в словаре под номером 256. Заносим I=«1».

3. Читаем указатель 102. Из словаря заносим J=«f» и выводим в файл «f». Сохраняем «lf» в словаре под номером 257. Заносим I=«f».

4. Читаем указатель 32. Из словаря заносим J=«_» и выводим в файл «_». Сохраняем «f _» в словаре под номером 258. Заносим I=«_».

5. Читаем указатель 101. Из словаря заносим J=«e» и выводим в файл «е». Сохраняем «_е» в словаре под номером 259. Заносим I=«е».

6. Читаем указатель 97. Из словаря заносим J=«a» и выводим в файл «а». Сохраняем «еа» в словаре под номером 260. Заносим I=«а».

7. Читаем указатель 116. Из словаря заносим J=«t» и выводим в файл «t». Сохраняем «at» в словаре под номером 261. Заносим I=«t».

8. Читаем указатель 115. Из словаря заносим J=«s» и выводим в файл «s». Сохраняем «ts» в словаре под номером 262. Заносим I=«s».

9. Читаем указатель 32. Из словаря заносим J=«_» и выводим в файл «_». Сохраняем «s_» в словаре под номером 263. Заносим I=«_».

10. Читаем указатель 256. Из словаря заносим J=«al» и выводим в файл «аl». Сохраняем «_а» в словаре под номером 264. Заносим I=«а1».

11. Читаем указатель 102. Из словаря заносим J=«f» и выводим в файл «f». Сохраняем «alf» в словаре под номером 265. Заносим I=«f».

12. Читаем указатель 265. Из словаря заносим J=«alf» и выводим в файл «alf». Сохраняем «fa» в словаре под номером 266. Заносим I=«alf».

13. Читаем указатель 97. Из словаря заносим J=«a» и выводим в файл «а». Сохраняем «alfa» в словаре под номером 267 (хотя она никогда не будет использована). Заносим I=«а».

14. Читаем eof. Конец.

Пример: Для алфавита из двух символов а и b покажем первые несколько шагов кодирования и декодирования последовательности «ababab...». Предполагается, что словарь инициализируется всего двумя строками (1: а) и (2: Ь). Кодер выдает на выход последовательность

1 (а), 2 (b), 3 (ab), 5 (aba), 4 (ba), 7 (bab), 6 (abab), 9 (ababa), 8 (baba), …

и добавляет в словарь новые строки: (3: ab), (4: bа), (5: aba), (6: abab), (7: bab), (8: baba), (9: ababa), (10: ababab), (11: babab). Процесс вполне регулярный, его легко проанализировать и предсказать, что будет заноситься на -ом шаге в файл и словарь. Результат не стоит затраченных усилий.