ПР8_Отчёт_ЗаболотниковМЕ_9373
.docx
МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра информационных систем
отчет
по практической работе №8
по дисциплине «Теория информации, данные, знания»
Тема: Декодирование LZW
Студент(ка) гр. 9373 |
|
Заболотников М.Е. |
Преподаватель |
|
Писарев И. А. |
Санкт-Петербург
2020
Цель работы
Сформулировать ответы на вопросы с указанием источников информации.
Вопросы по теме 8:
В каких популярных программах реализован метод LZW.
Гарантирует ли метод LZW отсутствие потерь или искажений данных?
Опишите метод декодирования Лемпеля-Зива-Велча (LZW).
Декодируйте сообщение методом LZW: 99, 256, 257, 258.
Приведите описание последовательности выполненных действий декодирования с комментариями выполняемых шагов алгоритма.
Декодировать сообщение методом LZW: 65, 68, 256, 257, 68, 260.
Приведите описание последовательности выполненных действий.
Выполнение работы
Алгоритм LZW используется для сжатия информации в файлах формата TIFF, PDF, GIF и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).
Потерь или искажений данных при применении алгоритма LZW не происходит, алгоритм это гарантирует.
Особенность LZW заключается в том, что для декодирования нам нет необходимости сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы можем восстановить таблицу строк, пользуясь только потоком кодов.
У нас имеется код сообщения: 99, 256, 257, 258. Считываем первый элемент кода, он равен 99. Так как исходный словарь – словарь ASCII-символов, то однозначно декодируем данный символ как «с». Таким образом, на данный момент мы имеем строки «с» и «с…», где «…» -- неизвестный символ. Считываем дальше, получаем код 256. Такого кода нет в словаре, следовательно, мы его уже занесли в словарь при кодировании. А это значит, что неизвестный символ – «с» и мы получили строку «сс». Также в словаре нет кода 257, поэтому очередной символ – «с» и строка «ссс». Ну из кода 258 получаем строку «сссс». Таким образом, получаем исходное сообщение: «сссссссссс».
Ответ: сссссссссс.
Пусть у нас имеется код сообщения: 65, 68, 256, 257, 68, 260. Читаем код 65, 68. Из словаря получаем и выводим 65 = «A». Заносим в словарь «AD» = 256. Далее читаем код 68, 256. Из словаря получаем и выводим 68 = «D». Заносим в словарь «DAD» = 257. Потом: код 256, 257. Из словаря получаем и выводим 256 = «AD». Заносим в словарь «ADDAD» = 258. Затем читаем код 257, 68. Из словаря получаем и выводим 257 = «DAD». Заносим в словарь «DADD» = 259. Читаем код 68, 260. Кода 260 нет в словаре, значит это возможно, только если в считываемой последовательности последний символ был такой же, как и первый (68 = «D»), то есть получаем и выводим это сообщение два раза – «DD». Получаем, что на первом шаге декодировали «A», на втором «D», на третьем «AD», на четвёртом «DAD», на пятом «DD». Итоговое сообщение: «ADADDADDD».
Ответ: ADADDADDD.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
https://yadi.sk/i/wthU8ISpHESyQQ
https://yadi.sk/i/djuccSCVCeQpxQ