Работа. Практическая рбота №7 Колков Наквасин 0323. Словарное кодирование. Метод lzw
 Скачать 131.82 Kb.
|
|
МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра информационных систем ОТЧЕТ по практической работе №7 по дисциплине «Теория информации, данные, знания» Тема: Словарное кодирование. Метод LZW. Студент(ка) гр. 0323 Наквасин А.А. Колков К.В. Преподаватель Писарев И. А. Санкт-Петербург 2022 2 Цель работы Письменно ответить на вопросы и решить задачи. Вопросы: 1. В чем состоит особенность методов словарного кодирования. 2. Дайте сравнительную характеристику наиболее известных методов словарного кодирования (LZ77, LZ78, LZW). 3. Опишите метод Лемпеля-Зива-Велча (LZW). Задачи: 1. Закодировать сообщение методом LZW. Опишите выполненные шаги алгоритма кодирования. Какое значение степени сжатия получено ? bbbbbbbbbb Приведите описание последовательности выполненных действий по кодированию с комментариями выполняемых шагов алгоритма. 2. Закодировать сообщение методом LZW. Опишите выполненные шаги алгоритма кодирования. Какое значение степени сжатия получено ? DADAADAAA Приведите описание последовательности выполненных действий. 3 Выполнение работы Вопросы: 1. В чем состоит особенность методов словарного кодирования. Методы, основанные на словарном подходе, не рассматривают статистические модели, они также не используют коды переменной длины. Вместо этого они выбирают некоторые последовательности символов, сохраняют их в словаре, а все последовательности кодируются в виде меток, используя словарь. Словарь может быть статическим или динамическим (адаптивным). Первый является постоянным; иногда в него добавляют новые последовательности, но никогда не удаляют. Динамический словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается и добавление, и удаление данных из словаря по мере чтения входного файла. [1, С.81] 2. Дайте сравнительную характеристику наиболее известных методов словарного кодирования (LZ77, LZ78, LZW). Метод LZ77 Этот алгоритм основывается на предположении, что похожие образцы сжи- маемых данных находятся близко друг от друга. Если содержимое файла не удовлетворяет этому условию, то он будет сжиматься плохо. Простой пример - это текст, в котором слово «economy» встречается часто и равномерно распределено по всему тексту. Может случиться, что когда это слово попадает в упреждающий буфер, его предыдущая копия уже вышла из буфера просмотра. Более лучший алгоритм мог бы сохранять часто встречающиеся слова в словаре, а не сдвигал бы их все время. Другой недостаток метода - это ограниченные размеры упреждающего буфера. Размер совпадающей строки лимитирован числом L — 1, но L приходится держать маленьким, так как процесс сравнения строк основан на сравнении индивидуальных символов. Если удвоить L, то степень сжатия 4 могла бы возрасти, но одновременно с этим произойдет замедление процесса поиска совпадений. Размер S буфера поиска тоже ограничен. Большой буфер поиска мог бы тоже улучшить компрессию, но опять возрастет сложность поиска по дереву, даже двоичному. Увеличение буферов также означает удлинение меток, что сокращает фактор сжатия. Метод LZ78 Метод LZ78 (иногда его называют LZ2, см. [Ziv 78]) не использует буфер поиск, упреждающий буфер и скользящее окно. Вместо этого имеется словарь встретившихся ранее строк. В начале этот словарь пуст (или почти пуст), и размер этого словаря ограничен только объемом доступной памяти. На выход кодера поступает последовательность меток, состоящих из двух полей. Первое поле -это указатель на строку в словаре, а второе - код символа. Метка не содержит длины строки, поскольку строка берется из сло- варя. Каждая метка соответствует последовательности во входном файле, и эта последовательность добавляется в словарь после того, как метка записана в выходной сжатый файл. Ничего из словаря не удаляется, что является одновременно и преимуществом над LZ77 (поскольку будущие строки могут совпадать даже с очень давними последовательностями) и недостатком (так как быстро растет объем словаря). Метод LZW Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Алгоритмы LZ77 и LZ78 уступают алгоритму LZW. В методе LZW первым делом инициализируется словарь всеми символами исходного алфавита. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, и поэтому метка может состоять только из указателя, и не нужно хранить код символа, к в алгоритмах LZ77 и LZ78. 3. Опишите метод Лемпеля-Зива-Велча (LZW). 5 Процесс сжатия выглядит следующим образом. Последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова. Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от «0» до «255»). Если используется 10 - битный код, то под коды для строк остаются значения в диапазоне от 256 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом. Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при дешифровании при получении нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря. [2, С.66] 6 Задачи: 1. Сообщение: bbbbbbbbbb 0:b Текущая строка Текущий символ Следующий символ Вывод Словарь Код Биты bb b b 0 000 1:bb bb b b - - - bbb b b 1 001 2:bbb bb b b - - - bbb b b - - - bbbb b b 2 010 3:bbbb bb b b - - - bbb b b - - - bbbb b b - - - bbbb b - 3 011 - Ответ: 0123, что на 2 бита короче. Коэффициент сжатия: 𝐾 = ! "# ∗ 100 = 40% 2. Сообщение: DADAADAAA 0:A 1:D Текущая строка Текущий символ Следующий символ Вывод Словарь Код Биты DA D A 1 001 2:DA AD A D 0 000 3:AD DA D A - - - DAA A A 2 010 4:DAA AD A D - - - ADA D A 3 011 5:ADA AA A A 0 000 6:AA AA A A - - - AA A - 6 110 - Ответ: 102306, что на 5 бит короче. Коэффициент сжатия: 𝐾 = $ % ∗ 100 = 66% 7 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Д.Сэломон. Сжатие данных, изображений и звука М.: Техносфера, 2004. - 368с. 2. Гошин Е.В. Теория информации и кодирования. Самара: Самарский университет, 2018 — 124 с. |