Методическое пособие Теория информации-2
.pdfучитывается тот факт, что одни значения смещений во время кодирования используются чаще, чем другие, а некоторые из них вообще не используются.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.1 |
|
|
|
|
|
|
|
|
|
Иллюстрация работы LZ77 алгоритма |
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Скользящее окно |
|
|
|
|
|
|
|
|
|
|
|
Код |
||||||||
|
|
|
|
|
Буфер поиска |
|
|
|
|
|
|
|
Буфер просмотра |
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
1 |
6 |
9 |
1 |
6 |
|
6 |
1 |
|
6 |
8 |
|
1 |
|
7 |
1 |
1 |
6 |
9 |
|
1 |
6 |
8 |
1 |
7 |
5 |
|
1 |
7 |
0 |
|
9,5,«5» |
1 |
6 |
8 |
1 |
7 |
|
1 |
1 |
|
6 |
9 |
|
1 |
|
6 |
8 |
1 |
7 |
5 |
|
1 |
7 |
0 |
1 |
6 |
7 |
|
1 |
6 |
6 |
|
3,2, «0» |
1 |
7 |
1 |
1 |
6 |
|
9 |
1 |
|
6 |
8 |
|
1 |
|
7 |
5 |
1 |
7 |
0 |
|
1 |
6 |
7 |
1 |
6 |
6 |
|
1 |
6 |
5 |
|
9,2, «7» |
1 |
6 |
9 |
1 |
6 |
|
8 |
1 |
|
7 |
5 |
|
1 |
|
7 |
0 |
1 |
6 |
7 |
|
1 |
6 |
6 |
1 |
6 |
5 |
|
1 |
7 |
0 |
|
3,2, «6» |
1 |
6 |
8 |
1 |
7 |
|
5 |
1 |
|
7 |
0 |
|
1 |
|
6 |
7 |
1 |
6 |
6 |
|
1 |
6 |
5 |
1 |
7 |
0 |
|
1 |
7 |
0 |
|
3,2, «6» |
1 |
7 |
5 |
1 |
7 |
|
0 |
1 |
|
6 |
7 |
|
1 |
|
6 |
6 |
1 |
6 |
5 |
|
1 |
7 |
0 |
1 |
7 |
0 |
|
1 |
7 |
0 |
|
12,4, «7» |
0 |
1 |
6 |
7 |
1 |
|
6 |
6 |
|
1 |
6 |
|
5 |
|
1 |
7 |
0 |
1 |
7 |
|
0 |
1 |
7 |
0 |
1 |
7 |
|
0 |
1 |
7 |
|
3,3, «0» |
1 |
6 |
6 |
1 |
6 |
|
5 |
1 |
|
7 |
0 |
|
1 |
|
7 |
0 |
1 |
7 |
0 |
|
1 |
7 |
0 |
1 |
7 |
0 |
|
1 |
6 |
7 |
|
9,7, «6» |
0 |
1 |
7 |
0 |
1 |
|
7 |
0 |
|
1 |
7 |
|
0 |
|
1 |
7 |
0 |
1 |
6 |
|
7 |
1 |
6 |
8 |
1 |
7 |
|
1 |
1 |
6 |
|
4,1, «1» |
7 |
0 |
1 |
7 |
0 |
|
1 |
7 |
|
0 |
1 |
|
7 |
|
0 |
1 |
6 |
7 |
1 |
|
6 |
8 |
1 |
7 |
1 |
1 |
|
6 |
8 |
1 |
|
3,1, «8» |
1 |
7 |
0 |
1 |
7 |
|
0 |
1 |
|
7 |
0 |
|
1 |
|
6 |
7 |
1 |
6 |
8 |
|
1 |
7 |
1 |
1 |
6 |
8 |
|
1 |
6 |
8 |
|
9,2, «1» |
1 |
7 |
0 |
1 |
7 |
|
0 |
1 |
|
6 |
7 |
|
1 |
|
6 |
8 |
1 |
7 |
1 |
|
1 |
6 |
8 |
1 |
6 |
8 |
|
1 |
7 |
0 |
|
6,4, «6» |
0 |
1 |
6 |
7 |
1 |
|
6 |
8 |
|
1 |
7 |
|
1 |
|
1 |
6 |
8 |
1 |
6 |
|
8 |
1 |
7 |
0 |
1 |
7 |
|
1 |
1 |
7 |
|
9,3, «0» |
1 |
6 |
8 |
1 |
7 |
|
1 |
1 |
|
6 |
8 |
|
1 |
|
6 |
8 |
1 |
7 |
0 |
|
1 |
7 |
1 |
1 |
7 |
0 |
|
1 |
6 |
7 |
|
12,4, «7» |
1 |
1 |
6 |
8 |
1 |
|
6 |
8 |
|
1 |
7 |
|
0 |
|
1 |
7 |
1 |
1 |
7 |
|
0 |
1 |
6 |
7 |
1 |
6 |
|
8 |
1 |
6 |
|
6,1, «1» |
6 |
8 |
1 |
6 |
8 |
|
1 |
7 |
|
0 |
1 |
|
7 |
|
1 |
1 |
7 |
0 |
1 |
|
6 |
7 |
1 |
6 |
8 |
1 |
|
6 |
9 |
1 |
|
12,1, «7» |
1 |
6 |
8 |
1 |
7 |
|
0 |
1 |
|
7 |
1 |
|
1 |
|
7 |
0 |
1 |
6 |
7 |
|
1 |
6 |
8 |
1 |
6 |
9 |
|
1 |
6 |
6 |
|
15,4, «6» |
Выбор параметров скользящего окна самым непосредственным образом влияет на эффективность кодирования. С одной стороны, увеличение размера буфера поиска означает расширение словаря и ведет к повышению вероятности нахождения идентичных строк, а увеличение размера буфера просмотра позволяет учитывать при кодировании более длинные совпадения. С другой стороны, размер кодового пространства, необходимого для хранения смещений строк и длин совпадений, возрастает с увеличением соответствующих составляющих скользящего окна по логарифмическому закону.
Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. К
231
достоинствам LZ77 можно отнести чрезвычайную простоту алгоритма
декомпрессии.
Алгоритм LZSS (Lempel-Ziv-Storer- Szimanski)
Необходимость включения в каждый код в качестве третьего компонента,
как это делается в алгоритме LZ77, дополнительного символа является спорной. Данные недостатки были частично устранены в алгоритме LZSS.
Алгоритм LZSS был предложен Д. Сторером и Т. Сжиманским, а затем усовершенствован Т. Беллом. Отличие данного алгоритма от алгоритма LZ77
заключается в отказе от последнего компонента кодовой триады. Для описания совпадений в данном случае используются кодовые пары типа <смещение совпадения, длина совпадения>. Проблема отсутствия совпадений в словаре решается путем введения дополнительного служебного бита, значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой,
или она представляет собой незакодированный символ в его исходном представлении. Отметим, что кодовые пары используются только в том случае,
когда длина кодовой комбинации с учетом служебного бита не превышает длины найденного совпадения в словаре. Результат работы алгоритма,
разобранный на предыдущем примере, представлен в таблице 7.2.
Жирным начертанием в таблице 7.2 выделены коды для случаев, когда длина кодовой комбинации с учетом служебного бита превысила длину найденного совпадения в словаре и кодовая пара не использовалась. Таким образом, часть строки, в которую вошло 63 символа по 3 бита каждый,
закодируется последовательностью, содержащей 10 элементов по 4 бит (1 бит на служебный символ и 3 бита на незакодированный символ) и 18 элементов по
7 бит (1 бит на служебный символ и 6 бит на кодовую пару).
Помимо оригинальной системы кодирования в алгоритме LZSS
используется особый способ поиска совпадений в словаре. При кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в
котором каждому узлу (как внутреннему, так и листовому) соответствует
232
определенная строка словаря длины l (максимальная длина совпадения).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.2 |
|
|
|
|
|
|
|
|
Иллюстрация работы алгоритма LZSS |
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Скользящее окно |
|
|
|
|
|
|
|
|
|
|
|
Код |
|||||
|
|
|
|
|
Буфер поиска |
|
|
|
|
|
|
Буфер просмотра |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
1 |
6 |
9 |
1 |
6 |
6 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
|
7 |
0 |
|
1<9,5> |
6 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
|
1 |
6 |
|
0<5> |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
|
6 |
6 |
|
1<3,2> |
8 |
1 |
7 |
1 |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
|
1 |
6 |
|
0<0> |
1 |
7 |
1 |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
|
6 |
5 |
|
1<9,2> |
1 |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
|
1 |
7 |
|
0<1> |
1 |
6 |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
1 |
|
7 |
0 |
|
1<3,2> |
9 |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
1 |
7 |
0 |
|
1 |
7 |
|
0<1> |
1 |
6 |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
1 |
7 |
0 |
1 |
|
7 |
0 |
|
1<3,2> |
8 |
1 |
7 |
5 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
1 |
7 |
0 |
1 |
7 |
0 |
|
1 |
7 |
|
1<12,5> |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
|
0 |
1 |
|
1<3,3> |
6 |
7 |
1 |
6 |
6 |
1 |
6 |
5 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
|
0 |
1 |
|
1<6,6> |
6 |
5 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
|
8 |
1 |
|
1<3,3> |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
|
1 |
1 |
|
0<6> |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
|
1 |
6 |
|
0<7> |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
|
6 |
8 |
|
1<3,2> |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
|
8 |
1 |
|
1<3,6> |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
|
1 |
6 |
|
0<8> |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
1 |
|
6 |
8 |
|
1<9,2> |
0 |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
1 |
6 |
8 |
|
1 |
7 |
|
0<1> |
1 |
7 |
0 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
1 |
6 |
8 |
1 |
|
7 |
0 |
|
1<6,4> |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
1 |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
|
1 |
1 |
|
1<9,4> |
7 |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
1 |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
1 |
1 |
7 |
0 |
|
1 |
6 |
|
0<0> |
1 |
6 |
8 |
1 |
7 |
1 |
1 |
6 |
8 |
1 |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
1 |
1 |
7 |
0 |
1 |
|
6 |
7 |
|
1<12,4> |
7 |
1 |
1 |
6 |
8 |
1 |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
1 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
|
8 |
1 |
|
1<6,3> |
6 |
8 |
1 |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
1 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
6 |
|
9 |
1 |
|
0<6> |
8 |
1 |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
1 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
6 |
9 |
|
1 |
6 |
|
1<7,2> |
6 |
8 |
1 |
7 |
0 |
1 |
7 |
1 |
1 |
7 |
0 |
1 |
6 |
7 |
1 |
6 |
8 |
1 |
6 |
9 |
1 |
6 |
|
6 |
|
|
1<15,3> |
Поиск осуществляется путем последовательного сравнения кодируемой строки со строками, соответствующими узлам дерева, проходимым при движении по дереву от корневого узла до некоторого листового узла.
233
Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска трансформируется. Трансформация производится посредством удаления и добавления строк. Если удаление строки требует некоторых дополнительных усилий, то операция добавления предельно проста и осуществляется прямо в процессе поиска совпадений.
Очевидный недостаток данного алгоритма то, что при кодировании не учитываются существующие статистические закономерности в появлении значений служебных битов.
Алгоритм LZ78
Алгоритм представляет собой модификацию LZ77 алгоритма,
предложенного теми же авторами. В данном алгоритме словарь представляет собой множество пронумерованных строк различной длины. Так же, как и в алгоритмах семейства LZ77, на каждом шаге работы алгоритма LZ78 в словаре осуществляется поиск наиболее длинной строки, идентичной части кодируемой символьной последовательности. Кодовая комбинация состоит из двух частей.
Первая является индексом найденной в словаре строки. В качестве второй части выступает символ, следующий за кодируемой строкой. Главное отличие алгоритма LZ78 от алгоритмов семейства LZ77 состоит в том, что длина совпадения здесь в явном виде не фигурирует как компонент кода. Это становится возможным благодаря тому, что в алгоритме LZ78, а также в других алгоритмах семейства, каждому индексу в словаре соответствует строка вполне определенной длины.
Нумерация строк в словаре начинается с первого индекса. Нулевой индекс соответствует пустой строке и зарезервирован для случая отсутствия совпадений. В процессе работы после генерации очередной порции кода только что обработанная последовательность символов добавляется в словарь с присвоением ей первого в порядке возрастания неиспользуемого индекса.
Таким образом, словарь каждый раз пополняется строкой, отличающейся от
234
некоторой уже имеющейся в словаре строки одним дополнительным символом.
Данная особенность позволяет экономно представлять словарь в виде дерева,
каждому узлу которого соответствует ровно один символ. Добавление строк в словарь сводится к добавлению дочернего узла к узлу, соответствующему строке, имеющей на данный момент наибольшее совпадение с кодируемой символьной последовательностью.
На практике, словарь не может продолжать расти бесконечно. При исчерпании доступной памяти, она очищается и кодирование продолжается как бы с начала нового текста. Алгоритм LZ78 резервирует специальный код,
который вставляется в упакованные данные, отмечая момент сброса словаря.
Кодовое пространство, отводимое в алгоритме LZ78 под хранение индекса, находится в логарифмической зависимости от количества используемых индексов. Размер второго компонента кодовой комбинации,
кодирующего отдельный символ, постоянен и зависит от размера информационного алфавита.
Пример. Пусть на кодер поступает последовательность символов
1661651701701701701701671681711681681701711701671681691661691661.
Пусть длина словаря ограничена 15 строками. В таблице 7.3 приведен результат работы алгоритма. Кодируемая последовательность обеспечила двукратное наполнение словаря.
Исходная длина последовательности составила 75 символов по 3 бита;
закодированная последовательность – 4 + 3 × 15 × 2 + N, т.е. 4 бита отводится на индексацию, по 3 бита на второй элемент кода и дополнительные
N бит на код очистки словаря.
Так как код в алгоритме LZ78 включает в себя индексы словаря, то словарь необходимо поддерживать не только на этапе кодирования, но и на этапе декодирования. Как и в любом адаптивном алгоритме, в алгоритме LZ78
изменения в словаре производятся синхронно на обоих этапах. При декодировании после интерпретации очередной кодовой комбинации в словарь
235
добавляется декодированная последовательность символов, состоящая из
строки, уже имеющейся в словаре, и дополнительного символа.
Таблица 7.3
Иллюстрация работы алгоритма LZ78
|
Кодирование первой части последовательности (30 символов) |
|
||||||||||
|
Код |
0, |
0, |
2, |
2, |
|
1, |
0, |
5, |
|
7, «1» |
|
|
|
«1» |
«6» |
«1» |
«5» |
|
«7» |
«0» |
«0» |
|
|
|
|
|
|
|
|
|
|||||||
|
Строка |
1 |
6 |
61 |
65 |
|
17 |
0 |
170 |
|
1701 |
|
|
Индекс |
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
|
8 |
|
|
Код |
0, |
6, |
9, |
1, |
|
9, |
2, |
5, |
|
|
|
|
|
«7» |
«1» |
«0» |
«6» |
|
«1» |
«8» |
«1» |
|
Код |
|
|
Строка |
7 |
01 |
70 |
16 |
|
71 |
68 |
171 |
|
очистки |
|
|
Индекс |
9 |
10 |
11 |
12 |
|
13 |
14 |
15 |
|
|
|
|
Очистка словаря. Кодирование второй части последовательности |
|
||||||||||
|
|
|
|
(35 символов) |
|
|
|
|
|
|||
|
Код |
0, |
1, |
0, |
2, |
|
1, |
0, |
5, |
|
5, «0» |
|
|
|
«1» |
«6» |
«8» |
«8» |
|
«7» |
«0» |
«1» |
|
|
|
|
|
|
|
|
|
|||||||
|
Строка |
1 |
16 |
8 |
168 |
|
17 |
0 |
171 |
|
170 |
|
|
Индекс |
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
|
8 |
|
|
Код |
2, |
4, |
0, |
0, |
|
2, |
2, |
13, |
|
|
|
|
|
«7» |
«1» |
«6» |
«9» |
|
«6» |
«9» |
«1» |
|
Код |
|
|
Строка |
167 |
1681 |
6 |
9 |
|
166 |
169 |
1661 |
|
очистки |
|
|
Индекс |
9 |
10 |
11 |
12 |
|
13 |
14 |
15 |
|
|
|
|
Неоспоримым достоинством алгоритмов семейства LZ78 является очень |
|||||||||||
высокая скорость |
кодирования. |
Быстрый |
поиск совпадений |
становится |
||||||||
возможным благодаря ограниченности словаря (словарь содержит далеко не все
обработанные строки) и использованию для его хранения древовидной
структуры.
Что касается декодирования, то, хотя оно и является более быстрой
операцией, чем операция кодирования, разница оказывается не такой значительной, как в случае с алгоритмами семейства LZ771. Поэтому
алгоритмы семейства LZ78 более выгодны с точки зрения скорости получения
информационного представления и менее выгодны с точки зрения скорости его
интерпретации.
236
Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch -LZW)
Данный алгоритм отличают высокая скорость работы как при упаковке,
так и при распаковке, достаточно небольшие требования к памяти и простая аппаратная реализация. Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. Существует довольно большое семейство LZW - подобных алгоритмов, различающихся, например,
методом поиска повторяющихся цепочек.
Основной алгоритм может быть пошагово описан следующим образом.
Перед началом сжатия в словарь заносятся все возможные символы и им присваиваются соответствующие номера строк в таблице словаря в качестве кода. Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от 0 до 255). Если используется 10-битный код, то под коды для новых комбинаций символов (далее «слов») остаются значения в диапазоне от
256 до 1023. Новые слова будут формировать таблицу словаря последовательно, т. е. можно считать индекс строки ее кодом.
Далее во входную фразу X заносится первый символ сообщения и считывается из сообщения следующий символ Y. Проводят проверку: если Y
является символом конца сообщения, то в выходную последовательность выдается код для сообщения X (номер строки в словаре), в противном случае проводят проверку полученной фразы XY. Если XY уже содержится в словаре,
то выполняют переприсваивание, при этом входной фразой становится X=XY,
и считывают новый символ из сообщения Y. В противном случае в выходную последовательность выдается код для сообщения X, последовательность XY
заносится в словарь, а в качестве входной фразы записывают X=Y, после чего считывают новый символ из сообщения и повторяют весь цикл проверок.
Для декодирования на вход подается только закодированный текст,
поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. Алгоритм
237
генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW
постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер.
Следовательно, при дешифровании при получении нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря.
Пример. Пусть исходный алфавит содержит пять символов: А, Б, В, Г, Д.
Требуется с помощью алгоритма Лемпеля-Зива-Велча закодировать следующее сообщение: АБГДВАБАБГДВАБГ.
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.4 |
|
|
Пример кодирования сообщения «АБГДВАБАБГДВАБГ» |
||||||||||||
|
|
|
|
LZW алгоритмом |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Входная |
|
Входя- |
Проверя- |
|
Словарь |
|
|
Вывод |
|
|
|||
|
щий |
емая |
|
|
|
|
|
|
|
|
Примечание |
|
|
фраза |
|
Фраза |
|
Код |
|
Биты |
|
Код |
Биты |
|
|||
|
символ |
фраза |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
|
2 |
3 |
4 |
|
5 |
|
6 |
|
7 |
8 |
9 |
|
|
|
|
|
А |
|
0 |
|
000 |
|
|
|
|
|
|
|
|
|
Б |
|
1 |
|
001 |
|
|
|
Заполнение |
|
- |
|
- |
- |
В |
|
2 |
|
010 |
|
- |
- |
исходного |
|
|
|
|
|
Г |
|
3 |
|
011 |
|
|
|
словаря |
|
|
|
|
|
Д |
|
4 |
|
100 |
|
|
|
|
|
- |
|
А |
А |
- |
|
- |
|
- |
|
- |
- |
Есть в словаре |
|
А |
|
Б |
АБ |
АБ |
|
5 |
|
101 |
|
0 |
000 |
Код для фразы А |
|
Б |
|
Г |
БГ |
БГ |
|
6 |
|
110 |
|
1 |
001 |
Код для фразы Б |
|
Г |
|
Д |
ГД |
ГД |
|
7 |
|
111 |
|
3 |
011 |
Код для фразы Г |
|
Д |
|
В |
ДВ |
ДВ |
|
8 |
|
1000 |
|
4 |
100 |
Код для фразы Д |
|
В |
|
А |
ВА |
ВА |
|
9 |
|
1001 |
|
2 |
010 |
Код для фразы В |
|
А |
|
Б |
АБ |
- |
|
- |
|
- |
|
- |
- |
АБ есть в словаре |
|
АБ |
|
А |
АБА |
АБА |
|
10 |
|
1010 |
|
5 |
101 |
Код для фразы |
|
|
|
|
|
АБ |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А |
|
Б |
АБ |
- |
|
- |
|
- |
|
- |
- |
АБ есть в словаре |
|
АБ |
|
Г |
АБГ |
АБГ |
|
11 |
|
1011 |
|
5 |
101 |
Код для фразы |
|
|
|
|
|
АБ |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Г |
|
Д |
ГД |
- |
|
- |
|
- |
|
- |
- |
ГД есть в словаре |
|
ГД |
|
В |
ГДВ |
ГДВ |
|
12 |
|
1100 |
|
7 |
111 |
Код для фразы |
|
|
|
|
|
ГД |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
|
А |
ВА |
- |
|
- |
|
- |
|
- |
- |
ВА есть в словаре |
|
238
Продолжение таблицы 7.4
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|
|
|
|
Код для фразы |
|
|
|
|
|
|
|
|
|
ВА; |
|
ВА |
Б |
ВАБ |
ВАБ |
13 |
1101 |
9 |
1001 |
далее используем |
|
|
|
|
|
|
|
|
|
четырехбитный |
|
|
|
|
|
|
|
|
|
код |
|
Б |
Г |
БГ |
- |
- |
- |
- |
- |
БГ есть в словаре |
|
|
Символ |
|
|
|
|
|
|
|
|
БГ |
конца |
БГ |
- |
- |
- |
6 |
0110 |
Код для фразы БГ |
|
сообще- |
|||||||||
|
|
|
|
|
|
|
|
||
|
ния |
|
|
|
|
|
|
|
Закодированное сообщение будет иметь вид: «0 1 3 4 2 5 5 7 9 6» или в двоичной форме «000 001 011 100 010 101 101 111 1001 0110». Каждый символ исходного сообщения кодировался группой из трех бит, следовательно, длина сообщения составляла 15 3 = 45 бит. Закодированное сообщение также вначале кодировалось трехбитными группами, при появлении в словаре восьмой фразы – четырехбитными. Длина закодированного сообщения составила 8 3 + 2 3 = 30 бит, что на 15 бит короче исходного.
Для декодирования на вход подается только закодированный текст,
поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW
постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер.
Следовательно, при дешифровании при получении нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря.
Пример. Провести декодирование последовательности «0 1 3 4 2 5 5 7 9 6», полученной в результате кодирования с использованием LZW алгоритма при условии, что исходный алфавит содержит пять символов: А, Б, В, Г, Д.
Особенность LZW заключается в том, что для декомпрессии не требуется
239
сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что восстановить таблицу строк возможно, пользуясь только потоком кодов при известном начальном словаре (см. табл. 7.5).
Таблица 7.5
Пример восстановления словаря при декодировании последовательности
|
|
|
«0 1 3 4 2 5 5 7 9 6» |
|
|
||
|
|
|
|
|
|
|
|
|
|
Соответству- |
|
|
Словарь |
|
|
|
|
ющая |
|
|
|
||
Входная |
Новый |
|
Проверяемая |
|
|
|
|
символу |
|
|
|
Примечание |
|||
фраза |
символ |
|
фраза |
|
|
||
фраза из |
|
Код |
Фраза |
|
|||
|
|
|
|
|
|||
|
|
словаря |
|
|
|
|
|
1 |
2 |
3 |
|
4 |
5 |
6 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
А |
|
|
|
|
|
|
1 |
Б |
|
- |
- |
- |
|
- |
2 |
В |
Исходный словарь |
|
|
|
|
|
3 |
Г |
|
|
|
|
|
|
4 |
Д |
|
- |
0 |
А |
|
А |
- |
- |
А есть в словаре |
|
|
|
|
|
|
|
АБ в словаре |
А |
1 |
Б |
|
АБ |
5 |
АБ |
отсутствует, |
|
помещаем фразу в |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
словарь |
|
|
|
|
|
|
|
Б есть в словаре, БГ в |
Б |
3 |
Г |
|
БГ |
6 |
БГ |
словаре отсутствует, |
|
помещаем фразу в |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
словарь |
|
|
|
|
|
|
|
Г есть в словаре, ГД в |
Г |
4 |
Д |
|
ГД |
7 |
ГД |
словаре отсутствует, |
|
помещаем фразу в |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
словарь |
|
|
|
|
|
|
|
Д есть в словаре, ДВ в |
Д |
2 |
В |
|
ДВ |
8 |
ДВ |
словаре отсутствует, |
|
помещаем фразу в |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
словарь |
|
|
|
|
|
|
|
В есть в словаре, ВА |
|
|
|
|
|
|
|
в словаре |
В |
5 |
АБ |
|
ВАБ |
9 |
ВА |
отсутствует, |
|
|
|
|
|
|
|
помещаем фразу в |
|
|
|
|
|
|
|
словарь |
|
|
|
|
|
|
|
А и АБ есть в |
|
|
|
|
|
|
|
словаре, АБА в |
АБ |
5 |
АБ |
|
АБАБ |
10 |
АБА |
словаре отсутствует, |
|
|
|
|
|
|
|
помещаем фразу в |
|
|
|
|
|
|
|
словарь |
240