Читайте также:
|
В настоящее время алгоритм LZW используется в большом количестве программ-архиваторов. Главная особенность алгоритма состоит в том, что метка включает в себя только указатель на место в словаре. Работа алгоритма начинается с инициализации словаря всеми символами исходного алфавита. Если имеется текстовый файл в формате ASCII, то первые 256 записей (отдельные символы с ASCII-кодами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять только из указателя, и нет надобности дополнительно хранить код символа, как в алгоритме LZ77.
Метод LZW накапливает поступающие на вход символы в строке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, то процесс удлинения I продолжается. В некоторый момент добавление некоторого символа x приводит к тому, что строка Ix не обнаруживается в словаре. Тогда кодер записывает в выходной файл указатель на строку I и сохраняет строку Ix в словаре на следующей допустимой позиции и инициализирует строку I значением x. Для примера снова рассмотрим сжатие строки sir_sid_eastman_easily_teases_sea_sick_seals. Получим следующие шаги.
1. Инициализируем словарь записями с номерами 0..255, содержащими все 8-битовее символы.
2. Первый входной символ s обнаруживается в словаре под номером 115 (это его ASCII-код). Следующий входной символ – i, но строки si нет в словаре. Кодер выдаёт на выход ссылку 115, сохраняет si в следующей доступной позиции словаря (позиция номер 256) и инициализирует I строкой i.
3. На вход поступает символ r, но строки ir нет в словаре. Кодер записывает на выход 105 (код символа i), сохраняет в словаре ir (запись 257) и инициализирует I строкой r.
Аналогичные шаги повторяются до тех пор, пока не закончится входной файл.
Декодер LZW также начинает свою работу с заполнения словаря первыми символами алфавита. Затем он читает входной файл, который состоит из указателей на записи в словаре, использует каждый указатель для того, чтобы восстановить несжатые символы из словаря и записать их в выходной файл. Кроме того, он строит словарь тем же способом, что и кодер.
На первом шаге декодирования декодер вводит первый указатель и использует его для восстановления словарного элемента I. Эта строка символов записывается декодером в выходной файл. Далее следует записать в словарь строку Ix, однако символ x ещё неизвестен; это будет первый символ следующей строки, извлечённой из словаря.
На каждом шаге декодирования после первого декодер вводит следующий указатель, извлекает следующую строку J из словаря, записывает её в выходной файл, извлекает её первый символ x и заносит строку Ix в словарь на свободную позицию (предварительно проверив, что строки Ix нет в словаре). Затем декодер записывает значение J в I. Теперь он готов к следующему шагу декодирования.
Дата добавления: 2015-01-05; просмотров: 46 | Поможем написать вашу работу | Нарушение авторских прав |