Практическая работа 8

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра информационных систем

отчет

по практической работе №8

по дисциплине «Теория информации, данные, знания»

Тема: Декодирование LZW

Студент гр. 9371
Преподаватель

Санкт-Петербург

2020

Цель работы

Письменно ответить на вопросы.

1. В каких популярных программах реализован метод LZW.

2. Гарантирует ли метод LZW отсутствие потерь или искажений данных.

3. Опишите метод декодирования Лемпеля-Зива-Велча (LZW).

Решить задачи:

2.2.1. Декодируйте сообщение методом LZW.

99, 256, 257, 258

Приведите описание последовательности выполненных действий декодирования с комментариями выполняемых шагов алгоритма

2. 2.2. Декодировать сообщение методом LZW

65, 68, 256, 257, 68, 260

Приведите описание последовательности выполненных действий.

Выполнение работы

Вопросы:

№ 1

Метод LZW отчасти используется в программах сжатия: ZIP, ARJ, LHA, а также в файлах формата TIFF, PDF, GIF, PostScript.

№ 2

Да.

№ 3

Для того, чтобы понять как работает декодер метода LZW, прежде всего еще раз напомним основные три шага, которые выполняет кодер каждый раз, делая очередную запись в выходной файл: (1) он заносит туда словарный указатель на строку I, (2) сохраняет строку 1х в следующей свободной позиции словаря и (3) инициализирует строку I символом X. Декодер начинает с заполнения словаря первыми символами ал­фавита (их, обычно, 256). Затем он читает входной файл, который состоит из указателей в словаре, использует каждый указатель для того, чтобы восстановить несжатые символы из словаря и записать их в выходной файл. Кроме того, он строит словарь тем же мето­дом, что и кодер (этот факт, обычно, отражается фразой: кодер и декодер работают синхронно или шаг в шаг). На первом шаге декодирования, декодер вводит первый указа­тель и использует его для восстановления словарного элемента I. Это строка символов, и она записывается декодером в выходной файл. Далее следует записать в словарь строку 1х, однако символ х еще неизвестен; это будет первый символ следующей строки, извле­ченной из словаря. На каждом шаге декодирования после первого декодер вводит следующий указатель, извлекает следующую строку J из словаря, записывает ее в выходной файл, извлекает ее первый символ х и заносит строку 1х в словарь на свободную позицию (предварительно проверив, что строки 1х нет в словаре). Затем декодер перемещает J в I. Теперь он готов к следующему шагу декодирования.

Задачи:

№1

Сообщение: 99, 256, 257, 258

Таблица ASCII – 256 символов

Данные		На выходе	Новая запись
Биты	Код		Полная	Частичная
110 0011	99	c	-	256: c?
1 0000 0000	256	cc	256: cc	257: cc?
1 0000 0001	257	ccc	257: ccc	258: ccc?
1 0000 0010	258	cccc	258: cccc	-

Исходное сообщение – «сссссссссс»

№2

Сообщение: 65, 68, 256, 257, 68, 260

Таблица ASCII – 256 символов

Данные		На выходе	Новая запись
Биты	Код		Полная	Частичная
100 0001	65	A	-	256: A?
100 0100	68	D	256: AD	257: D?
1 0000 0000	256	AD	257: DA	258: AD?
1 0000 0001	257	DA	258: ADD	259: DA?
100 0100	68	D	259: DAD	260: D?
1 0000 0100	260	DD	260: DD	-

Исходное сообщение – «ADADDADDD»

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Гошин Е.В. Теория информации и кодирования. Самара: Самарский университет, 2018 – 124 с.

2. Д.Сэломон. Сжатие данных, изображений и звука М.: Техносфера, 2004. - 368с.