Для того, чтобы понять как работает декодер метода LZW, прежде всего еще раз напомним основные три шага, которые выполняет кодер каждый раз, делая очередную запись в выходной файл: (1) он заносит туда словарный указатель на строку I, (2) сохраняет строку 1х в следующей свободной позиции словаря и (3) инициализирует строку I символом х.
Декодер начинает с заполнения словаря первыми символами алфавита (их, обычно, 256). Затем он читает входной файл, который состоит из указателей в словаре, использует каждый указатель для того, чтобы восстановить несжатые символы из словаря и записать их в выходной файл. Кроме того, он строит словарь тем же методом, что и кодер (этот факт, обычно, отражается фразой: кодер и декодер работают синхронно или шаг в шаг).
На первом шаге декодирования, декодер вводит первый указатель и использует его для восстановления словарного элемента I. Это строка символов, и она записывается декодером в выходной файл. Далее следует записать в словарь строку 1х, однако символ х еще неизвестен; это будет первый символ следующей строки, извлеченной из словаря.
На каждом шаге декодирования после первого декодер вводит следующий указатель, извлекает следующую строку J из словаря, записывает ее в выходной файл, извлекает ее первый символ х и заносит строку 1х в словарь на свободную позицию (предварительно проверив, что строки 1х нет в словаре). Затем декодер перемещает J в I. Теперь он готов к следующему шагу декодирования.
В нашем примере «sir.sid. . .» первым символом входного файла декодера является указатель 115. Он соответствует строке s, которая извлекается из словаря, сохраняется в I и становится первой строкой, записанной в выходной (разжатый) файл. Следующий указатель - 105, поэтому в J заносится строка i, а содержимое J записывается в выходной файл. Первый символ строки J добавляется к переменной I, образуя строку si, которой нет в словаре, поэтому она добавляется в словарь на позиции 256. Содержимое переменной J переносится в переменную I; теперь I равно i. Следующий указатель - 114, поэтому, из словаря извлекается строка г, заносится в J и пишется в выходной файл. Переменная I дополняется до значения ir; такой строки нет в словаре, поэтому она туда заносится под номером 257. Переменная J переписывается в I, теперь I равно г. На следующем шаге декодер читает указатель 32, записывает «_» в файл и сохраняет в словаре строку г_.
Пример: Строка «alf_eats_alfalfa» будет декодироваться с помощью сжатого файла из примера на стр. 100 следующим образом: 1. Читаем указатель 97. Из словаря заносим 1=«а» и выводим в файл «а». Строку Ix надо записать в словарь, но х неизвестно.
2. Читаем указатель 108. Из словаря заносим J=«l» и выводим в файл «1». Сохраняем «al» в словаре под номером 256. Заносим 1=«1».
3. Читаем указатель 102. Из словаря заносим J=«f» и выводим в файл «f». Сохраняем «If» в словаре под номером 257. Заносим I=«f».
4. Читаем указатель 32. Из словаря заносим J=«_» и выводим в файл «_». Сохраняем «f _» в словаре под номером 258. Заносим 1=«_».
5. Читаем указатель 101. Из словаря заносим J=«e» и выводим в файл «е». Сохраняем «_е» в словаре под номером 259. Заносим 1=«е».
6. Читаем указатель 97. Из словаря заносим J=«a» и выводим в файл «а». Сохраняем «еа» в словаре под номером 260. Заносим 1=«а».
7. Читаем указатель 116. Из словаря заносим J=«t» и выводим в файл «t». Сохраняем «at» в словаре под номером 261. Заносим I=«t».
8. Читаем указатель 115. Из словаря заносим J=«s» и выводим в файл «s». Сохраняем «ts» в словаре под номером 262. Заносим I=«s».
9. Читаем указатель 32. Из словаря заносим J=«_» и выводим в файл «_». Сохраняем «s_» в словаре под номером 263. Заносим 1=«_».
10. Читаем указатель 256. Из словаря заносим J=«al» и выводим в файл «al». Сохраняем «_а» в словаре под номером 264. Заносим 1=«а1».
11. Читаем указатель 102. Из словаря заносим J=«f» и выводим в файл «f». Сохраняем «alf» в словаре под номером 265. Заносим I=«f».
12. Читаем указатель 265. Из словаря заносим J=«alf» и выводим в файл «alf». Сохраняем «fa» в словаре под номером 266. Заносим I=«alf».
13. Читаем указатель 97. Из словаря заносим J=«a» и выводим в файл «а». Сохраняем «alfа» в словаре под номером 267 (хотя она никогда не будет использована). Заносим 1=«а».
14. Читаем eof. Конец.
Пример: Для алфавита из двух символов а и Ъ покажем первые несколько шагов кодирования и декодирования последовательности «ababab. . .». Предполагается, что словарь инициализируется всего двумя строками (1: а) и (2: Ъ). Кодер выдает на выход последовательность
1 (а), 2 (Ъ), 3 (аЪ), 5 (aba), 4 (Ъа), 7 (ЪаЪ), б (abab), 9 (ababa), 8 (ЪаЪа),. . .
и добавляет в словарь новые строки: (3: аЪ), (4: Ъа), (5: aba), (6: abab), (7: bab), (8: baba), (9: ababa), (10: ababab), (11: babab). Процесс вполне регулярный, его легко проанализировать и предсказать, что будет заноситься на к-ом шаге в файл и словарь. Результат не стоит затраченных усилий.
