Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

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

Для того, чтобы понять как работает декодер метода 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). Процесс вполне регулярный, его легко проанализировать и предсказать, что будет заноситься на к-ом шаге в файл и словарь. Результат не стоит затраченных усилий.

Похожие материалы