Алгоритм LZW

Алгоритм, названный в честь своих создателей Лемпеля, Зива и Велча (Lempel, Ziv и Welch), не требует вычисления вероятностей встречаемости символов или кодов. Основная идея состоит в замене совокупности байтов в исходном файле ссылкой на предыдущее появление той же совокупности.

Процесс сжатия выглядит следующим образом. Последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.

Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Для кода очистки и кода конца информации используются коды 256 и 257. Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 258 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.

Пример

Пусть сжимается последовательность символов АВВСВВВ. Сначала в сжатый документ сохраняется код удаления [256], затем считывается символ "А" и проверяется, существует ли в таблице строка "А". Поскольку при инициализации в таблицу сохраняются все строки длиной в один символ, то строка "А", конечно, существует в таблице.

Далее считывается следующий символ "В" и проверяется, существует ли в таблице строка "АВ". Такая строка в таблице пока отсутствует, поэтому с первым свободным кодом [258] в таблицу вносится строка "АВ", а в документе сохраняется код [А]. Последовательность "АВ" в таблице отсутствует, поэтому в таблицу добавляется код [258] для сочетания "АВ", а в документе сохраняется код [А].

Далее рассматривается последовательность "ВВ", которая отсутствует в таблице, в таблицу заносится код [259] для символов "ВВ", а в документе сохраняется код [В].

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий