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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.2.4.1 Кодирование последовательностей повторяющихся символов, метод RLE предусматривает замену последовательности повторяющихся символов на строку, содержащую этот символ, и число, соответствующее количеству его повторений. В качестве примера рассмотрим сжатие последовательности символов ACCOUNTbbbbbbbMOUNT, в которой b означает символ пробела. Если для обозначения выполненного сжатия символов пробела модем использует специальный символ Sс, то между модемами будет передана последовательность символов ACCONTSc7MOUNT. Символ Sс в этой последовательности означает, что было произведено сжатие символов пробела, а число 7 указывает, сколько именно символов пробела заменено символом Sс. С помощью этой информации принимающий модем может восстановить данные.

Однако в последовательности передаваемых символов может встретиться пара символов S и с, которые являются частью данных, а не специальным символом Sс, обозначающим сжатие. Чтобы принимающий модем воспринимал эти символы как данные, передающий модем при обнаружении пары символов Sс добавляет в передаваемую последовательность еще одну такую пару. Таким образом, если модем принял от терминала поток данных XYZScABC, то по телефонному каналу он передаст следующую последовательность символов: XYZScScABC. На принимающем модеме при обнаружении первого специального символа Sc проверяется следующий символ. Если им окажется не число, а еще один такой символ, модем отбросит второй символ и восстановит первоначальный поток данных.

Сжатие позволяет увеличить пропускную способность систем передачи данных, но если один или более символов будут переданы с ошибкой, это может привести к очень печальным последствиям при восстановлении потока данных. В качестве примера покажем, к чему может привести ошибка при передаче последовательности символов AAAAAAAA. Предположим, что используется алгоритм сжатия RLE, в котором символ, означающий сжатие, представлен последовательностью битов 11111111, а символ A – последовательностью 01000001 (табл. 8.6.).

На рис. 8.6 демонстрируется, к чему может привести ошибка всего лишь в одном символе переданной последовательности битов.

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

– Последовательность одинаковых символов: АААААААА

– Последовательность символов после сжатия: S c 8 A

– Двоичное представление передаваемых данных: 11111111 00001000 01000001

– Принятая последовательность символов: S c 8 C

– Распакованная последовательность символов: СССССССС

Рис. 8.6. Последствие ошибки в одном бите переданной сжатой строки

8.2.4.2. Кодирование длин повторений, может быть достаточно эффективным при сжатии двоичных данных, например, черно-белых факсимильных изображений, черно-белых изображений, содержащих множество прямых линий и однородных участков, схем и т.п. Кодирование длин повторений является одним из элементов известного алгоритма сжатия изображений JPEG.

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

Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8 х 8 элементов, приведенное на рис. 8.2.

Рис.8.2. Двухцветное изображение 8 х 8 элементов

Просканируем это изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1), в результате получим двоичный вектор данных

длиной 64 бита (скорость исходного кода составляет 1 бит на элемент изображения).

Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков - положительных целых чисел, соответствующих исходному вектору данных X, - будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4). Теперь эту последовательность, в которой заметна определенная повторяемость (единиц и четверок гораздо больше, чем других символов), можно закодировать каким-либо статистическим кодом, например, кодом Хаффмена без памяти, имеющим таблицу кодированием (табл. 8.6.)

Для того, чтобы указать, что кодируемая последовательность начинается с нуля, добавим в начале кодового слова префиксный символ 0. В результате получим кодовое слово B (r)= (01 00011010110101101011001110100100) длиной в 34 бита, то есть результирующая скорость кода R составит 34/64, или немногим более 0,5 бита на элемент изображения. При сжатии изображений большего размера и содержащих множество повторяющихся элементов эффективность сжатия может оказаться существенно более высокой.

Ниже приведен другой пример использования кодирования длин повторений, когда в цифровых данных встречаются участки с большим количеством нулевых значений. Всякий раз, когда в потоке данных встречается “ ноль ”, он кодируется двумя числами. Первое - 0, являющееся флагом начала кодирования длины потока нулей, и второе – количество нулей в очередной группе. Если среднее число нулей в группе больше двух, будет иметь место сжатие. С другой стороны, большое число отдельных нулей может привести даже к увеличению размера кодируемого файла:

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

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: