Кодирование методом LZW — это кодирование при помощи универсального алгоритма сжатия данных без потерь.
Общие сведения о кодировании методом LZW
С течением времени уровень мощности и производительности вычислительной техники непрерывно возрастет, а проблемы сжатия и кодирования информации не теряют своей актуальности для разработчиков программного обеспечения. Эффективным и распространенным решением данной проблемы может считаться использование метода кодирования (сжатия) информации LZW.
Основой данного алгоритма кодирования является предположение о том, что информация, которая поступает на вход кодирующего устройства, является заведомо избыточной, а содержание в ней полезных данных не равняется нулю. В данной ситуации получить идеальное сжатие можно только в случае, когда заранее известны энтропия, то есть, мера содержания информации, выраженная в битах, множество символов входного алфавита и степень вероятности появления каждого из символов во входном потоке. Одним из решений этой задачи считается метод LZW, который способен по мере получения информации в динамическом режиме вычислять целочисленные признаки частоты появления входных символов. Такими признаками могут считаться:
- Местоположение повторяющейся последовательности символов в промежуточной таблице соответствия среди исходного фиксированного алфавита и кодирующих последовательностей.
- Размер сжатого кода, который соответствует совокупности символов во входном потоке.
- Битовый диапазон длины кодов, значения которого находятся в границах от девяти до шестнадцати бит.
- Размеры хэш-таблицы, а также разбиение ячеек данной таблицы на четко зафиксированные и обладающие переменными значениями.
Основными достоинствам метода кодирования LZW являются следующие моменты:
- Применение операций целочисленной арифметики.
- Наличие возможности автоматической адаптации к качественному составу входного информационного потока.
- Наличие возможности разделять и инициализировать последовательности, имеющие заранее известную структуру.
- Применение плавающей длины байта, а именно, от девяти до N битов.
- Возможность экономного использования динамической памяти.
- Наличие файловой независимости от таблицы соответствия между кодами и символами алфавита.
Это все предоставляет возможность использования алгоритма LZW в различных приложениях не только обособленно как архиватор данных, но и в составе более сложных методик, таких как, к примеру, методы шифрования или любые другие методики побайтовой информационной обработки.
История и особенности метода LZW
Метод сжатия LZW (Lempel-Ziv-Welch) был предложен в 1978-ом году израильскими специалистами Лемпелом и Зивом и позже дорабатывался в Соединенных Штатах. Название алгоритму было присвоено по первым буквам фамилий его разработчиков, а именно, Lempel, Ziv и Welch. Сжатие в нем, в отличие от алгоритма RLE, выполняется уже за счет одинаковых цепочек байтов. LZW является методом сжатия данных, который способен извлекать преимущества при наличии повторяющихся цепочек данных.
Известность алгоритма LZW в существенной мере сопряжена с успехом программы compress. Исходный код последней версии этой программы, которая способна осуществлять как сжатие, так и декомпрессию, имеет размер всего в 1200 строк. Ядро кода сжатия имеет не больше ста строк, а код декомпрессии имеет немного больший размер. Программисты полагают, что это может облегчить чтение и понимание алгоритма, а также предоставляет возможность его адаптации для различных целей.
Усовершенствованная версия алгоритма (Terry Welch) была представлена в 1984-ом году. Алгоритм является, по сути, необычайно простым. LZW-сжатие выполняет замену строки символов определенными кодами. Это осуществляется без какого-нибудь предварительного анализа входной информации. Вместо этого при прибавлении любой новой строки символов реализуется просмотр таблицы строк. Сжатие выполняется, когда код подменяет символьную строку. Коды, которые генерирует алгоритм LZW, могут иметь любую длину, но они обязаны иметь больше битов, чем единичный символ.
Первые 256 кодов, если применяются восьмибитовые символы, по умолчанию должны соответствовать стандартной совокупности символов. Остальные коды должны соответствовать обрабатываемым алгоритмом строкам. Ядром алгоритма LZW считается словарь, который содержит весь набор символов входного алфавита и отдельные строки, состоящие из этих символов. До начала работы алгоритма в словарь должны входить компоненты, которые в качестве строк содержат каждый из символов входного алфавита. По мере выполнения алгоритма, попадающиеся во входном потоке цепочки символов должны заноситься в словарь. Причем в выходной поток должен заноситься номер компонента словаря, который содержит строку наибольшего размера, совпадающую со строкой входного потока.
Организация словаря выполнена в виде совокупности двоичных деревьев и должна содержать по одному двоичному дереву на любой символ входного алфавита. Каждый компонент словаря выступает при этом в качестве вершины одного из двоичных деревьев. Вершины деревьев считаются компонентами словаря, которые соответствуют символам входного алфавита. Каждая вершина должна соответствовать определенной строке, обладает одной входящей дугой и до двух выходящих дуг. Первая из них должна указывать на вершину, соответствующую строке, такой же как данная, но на один символ длиннее (связь $\lt$равно>), а вторая должна указывать на вершину, которая соответствует строке, обладающей таким же размером, как данная, но отличающуюся последним символом (связь $\lt$не равно>). Во всех вершинах графа должен содержаться также один символ. Параллельно выборке символов из входного потока выполняется обход одного из деревьев.
Арифметическое сжатие подразумевает знание вероятностей появления во входном потоке символов входного алфавита.
