Введение в цифровую графику
Алгоритм LZW
Алгоритм, названный
в честь своих создателей Лемпеля, Зива и Велча (Lempel, Ziv и Welch), не требует
вычисления вероятностей встречаемости символов или кодов. Основная идея состоит
в замене совокупности байтов в исходном файле ссылкой на предыдущее появление
той же совокупности.
Процесс сжатия
выглядит следующим образом. Последовательно считываются символы входного потока
и происходит проверка, существует ли в созданной таблице строк такая строка.
Если такая строка существует, считывается следующий символ, а если строка не
существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.
Например, если
сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0"
до "255"). Для кода очистки и кода конца информации используются коды
256 и 257. Если используется 10-битный код, то под коды для строк остаются значения
в диапазоне от 258 до 1023. Новые строки формируют таблицу последовательно,
т. е. можно считать индекс строки ее кодом.
Пример
Пусть сжимается последовательность символов АВВСВВВ. Сначала в сжатый документ сохраняется код удаления [256], затем считывается символ "А" и проверяется, существует ли в таблице строка "А". Поскольку при инициализации в таблицу сохраняются все строки длиной в один символ, то строка "А", конечно, существует в таблице.
Далее считывается
следующий символ "В" и проверяется, существует ли в таблице строка
"АВ". Такая строка в таблице пока отсутствует, поэтому с первым свободным
кодом [258] в таблицу вносится строка "АВ", а в документе сохраняется
код [А]. Последовательность "АВ" в таблице отсутствует, поэтому в
таблицу добавляется код [258] для сочетания "АВ", а в документе сохраняется
код [А].
Далее рассматривается
последовательность "ВВ", которая отсутствует в таблице, в таблицу
заносится код [259] для символов "ВВ", а в документе сохраняется код
[В].
Считывается символ
"С" и проверяется наличие символов "ВС" в таблице, поскольку
такая последовательность отсутствует, то в таблицу заносится кед [260] для последовательности
"ВС", а в документ — код [В].
Снова добавляется
из исходного файла символ "В" и теперь уже проверяется сочетание "СВ",
которое тоже отсутствует. В таблицу записывается код [261] для "СВ",
а в документ — код [С].
Затем считывается
символ "В" и строка "ВВ", наконец, имеется в таблице, поэтому
считывается следующий символ и рассматривается последовательность "ВВВ",
которая, конечно, в таблице отсутствует. В таблицу заносится код [262] для "ВВВ",
а в документ (внимание!) — код [259].
В результате в
документе окажется следующая последовательность кодов [256][А][В][В][С][259],
что короче исходной последовательности. К сожалению, последовательность слишком
короткая, а алгоритм достатчно сложен, чтобы выгода оказалась реальной. При
значительном объеме коэффициент сжатия может достигать несколько сот единиц.
Особенностью рассматриваемого алгоритма LZW является то, что для выполнения обратного процесса ("распаковки") нет необходимости сохранять таблицу в документе (алгоритм позволяет восстановить таблицу строк только из сохраненных в документе кодов).
