Сжатие данных по алгоритму словаря

Алгоритм словаря построен вокруг так называемой таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины, равные 12 бит. Таблица обладает свойством предшествования.

В настоящее время методы сжатия данных, включенные в протоколы MNP5 и MNP7, целенаправленно заменяются на метод, основанный на алгоритме словарного типа Лемпеля–Зива–Вэлча (LZW-алгоритме), который имеет два главных преимущества:

– обеспечивает достижение коэффициента сжатия 4:1 файлов с оптимальной структурой;

– LZW-метод утвержден ITU-T как составная часть стандарта V.42bis.

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

Согласно кодировке, приведённой в табл. 8.4, в двоичном коде с помощью 8 бит можно закодировать 256 символов.

Таблица 8.4.

Кодирование буквенно-цифровых знаков

Эти символы (вернее, их коды изначально заносятся в словарь программы, реализующей LZW). Во время работы программа посимвольно перебирает строку, подлежащую сжатию и передаче. При этом выполняется такая последовательность действий.

– Считываемый символ добавляется в формирующую строку. Если полученная строка уже присутствует в словаре, проверяется следующий символ.

– если полученной строки в словаре нет, передается предыдущая сформированная строка, а новая заносится в словарь.

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

префикс + суффикс = новая строка

После формирования новой строки суффикс становится префиксом:

префикс = суффикс

В качестве примера рассмотрим, как с помощью алгоритма LZW выполняется сжатие строки ababc, которая была передана модему терминалом. Вначале каждому символу словаря назначается числовое кодовое значение, соответствующее десятеричному представлению этого символа в кодировке ASCII. To есть кодовое значение символа а равно 97, кодовое значение символа b – 98 и т. д.

В соответствии с алгоритмом LZW, при первой выполняемой операции (первом цикле) принимается, что префиксом является пустая строка, которую мы обозначим символом f. Поэтому при выполнении первой операции первый считываемый символ а добавляется к пустой строке, в результате чего формируется новая строка а. Поскольку а присутствует в словаре, на выход ничего не передается. Далее, согласно алгоритму, суффикс становится префиксом – а становится префиксом при формировании новой строки (этот этап сжатия строки ababc отображен в первой строке табл. 8.5).

Таблица 8.5.

Сжатие строки ababc в соответствии с алгоритмом LZW

Следующим шагом выполнения алгоритма LZW является считывание из строки ввода второго символа – b, который становится суффиксом. В ходе его обработки он добавляется к префиксу а,и в результате образуется новая строка ab. Этой строки нет в словаре программы, поэтому вступает в силу второе правило, согласно которому на выход передается последняя сформированная строка а,кодовое значение которой равно 97, а новая строка аb добавляется в словарь. Ранее уже говорилось, что для представления символов в кодировке ASCII используется 8 бит, что позволяет работать с 255 символами. Из этого следует, что новым строкам можно присвоить кодовые значения, которые будут больше 255 (256 и т. д.) и которые в двоичном представлении требуют большего количества битов. Первоначальный размер лексемы, используемый для представления новых строк, согласовывается модемами во время процесса согласования, выполняемого в соответствии со стандартом V.42bis.

Однако вернемся к рассмотрению процесса сжатия. Символ b, который был суффиксом при формировании строки ab,стал префиксом для следующей операции (это отображено в третьей строке табл. 8.5).

Далее считывается следующий символ – а, который тут же используется как суффикс при создании новой строки bа. Поскольку этой строки нет в словаре, на выход передается предыдущая строка из числа еще не переданных, b,кодовое значение которой равно 98 (в соответствии с кодировкой ASCII). Заметьте, что сформированная перед этим строка аb была добавлена в словарь, а не отправлена на выход. При добавлении в словарь строки bа ей присваивается следующий код – 257, а символ а, который был суффиксом при формировании этой строки, при выполнении следующей операции становится префиксом, что отражено в четвертой строке табл. 6.4. Затем считывается очередной (четвертый) символ строки ввода – b,при добавлении которого в качестве суффикса к предыдущей строке (а)образуется новая строка аb.Однако поскольку она уже была добавлена в таблицу строк (словарь), на выход ничего не передается, а сама строка становится префиксом при создании следующей строки.

Данный этап процесса сжатия отражен в пятой строке табл. 8.5сформированная на предыдущем этапе строка ab,которая ранее была занесена в таблицу строк, стала префиксом при создании следующей строки, а последний символ с стал суффиксом. Полученная новая строка abc отсутствует в словаре, поэтому на выход передается последняя сформированная и не переданная строка – ab,точнее, передается присвоенное ей кодовое значение – 256. Символ с становится префиксом для создаваемой очередной строки, но так как он является последним символом строки ввода, его кодовое значение (99) передается на выход.

Декодер LZW должен использовать тот же словарь, что и кодер, строя его по аналогичным правилам при восстановлении сжатых данных. Каждый считываемый код разбирается с помощью словаря на предшествующую фразу w и символ К. Затем рекурсия продолжается для предшествующей фразы w до тех пор пока она не окажется кодом одного символа. При этом завершается декомпрессия этого кода. Обновление словаря происходит для каждого декодируемого кода, кроме первого. После завершения декодирования кода его последний символ, соединенный с предыдущей фразой, добавляется в словарь. Новая фраза получает то же значение кода (позицию в словаре), которое присвоил ей кодер. В результате такого процесса декодер шагза шагом восстанавливает тот словарь, который построил кодер.

Важное значение имеют алгоритмы сжатия LZ и LZW при архивации данных. Популярные архиваторы ARJ, РАК, LHARC PKZ1P работают на основе этих алгоритмов.