Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)

LZW - История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом (J.Ziv) и А. Лемпелем (A.Lempel) статьи в журнале "Информационные теории" под названием "IEEE Trans". Впоследствии этот алгоритм был доработан Терри А. Велчем (Terry A.Welch) и в окончательном варианте отражен в статье "IEEE Compute" в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы, с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch ) .

Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку "Объект TSortedCollection порожден от TCollection.". Анализируя эту строку, мы можем видеть, что слово "Collection" повторяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничиться длиной кодируемой строки в 256 символов, то, учитывая байт "флаг", получим, что строка из 80 бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как бы "обучается" в процессе сжатия файла. Если существуют повторяющиеся строки в файле, то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана (Huffman), которому требуется два прохода.

Данный алгоритм отличают высокая скорость работы как при упаковке, так и при распаковке, достаточно скромные требования к памяти и простая аппаратная реализация.

Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования.

Предположим, что у нас имеется словарь, хранящий строки текста и содержащий порядка от 2 до 8 тысяч пронумерованных гнезд. Запишем в первые 256 гнезд строки, состоящие из одного символа, номер которого равен номеру гнезда.

Алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые гнезда в конец словаря. Считаем несколько символов в строку s и найдем в словаре строку t - самый длинный префикс s.

Пусть он найден в гнезде с номером n. Выведем число n в выходной поток, переместим указатель входного потока на length(t) символов вперед и добавим в словарь новое гнездо, содержащее строку t+c, где с - очередной символ на входе (сразу после t). Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе.

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

Пример:

Архивируемая последовательность – ABCABCABCABCABCABC.

Архив - 1 2 3 4 6 5 7 7 7.

Словарь представлен в табл. 9.1.

Таблица 9.1

Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

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

Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву и обычно называется LZ-compression.

Суть его состоит в следующем: упаковщик постоянно хранит некоторое количество последних обработанных символов в буфере. По мере обработки входного потока вновь поступившие символы попадают в конец буфера, сдвигая предшествующие символы и вытесняя самые старые.

Размеры этого буфера, называемого также скользящим словарем (sliding dictionary), варьируются в разных реализациях кодирующих систем.

Экспериментальным путем установлено, что программа LHarc использует 4-килобайтный буфер, LHA и PKZIP - 8, а ARJ - 16-килобайтный.

Затем, после построения хеш-таблиц, алгоритм выделяет (путем поиска в словаре) самую длинную начальную подстроку входного потока, совпадающую с одной из подстрок в словаре, и выдает на выход пару (length, distance), где length - длина найденной в словаре подстроки, а distance - расстояние от нее до входной подстроки (то есть фактически индекс подстроки в буфере, вычтенный из его размера).

В случае, если такая подстрока не найдена, в выходной поток просто копируется очередной символ входного потока.

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

Таким образом, алгоритм Лемпеля-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таблице (length + distance).

Очевидно, что эти потоки являются потоками символов с двумя новыми алфавитами, и к ним можно применить один из упоминавшихся выше методов (RLE, кодирование Хаффмана или арифметическое кодирование).

Так, мы приходим к схеме двухступенчатого кодирования - наиболее эффективной из практически используемых в настоящее время. При реализации этого метода необходимо добиться согласованного вывода обоих потоков в один файл. Эта проблема обычно решается путем поочередной записи кодов символов из обоих потоков.

Пример:

Первая ступень

abcabcabcabcabc - 1 а 1 b 1 c 3 3 6 3 9 3 12 3

Вторая ступень - исключение большой группы повторяющихся последовательностей

1 а 1 b 1 c 12 3
и сжатие RLE, кодирование Хаффмана, арифметическое кодирование.

Библиографический Список

1. Вирт Н. Алгоритмы и структуры данных/Н. Вирт. М.: Мир,1989.

2. Сибуя М. Алгоритмы обработки данных/М. Сибуя, Т. Ямамото. М.: Мир,1986.

3. Костин А.Е. Организация и обработка структур данных в вычислительных системах: учеб.пособ. для вузов/А.Е. Костин, В.Ф. Шаньгин . М.: Высш.шк., 1987.

4. Кнут Д. Искусство программирования для ЭВМ.Т.1: Основные алгоритмы:пер. с англ./Д. Кнут. М.:Мир,1978.

5. Кнут Д. Искусство программирования для ЭВМ.Т.3: Сортировка и поиск.: пер. с англ./Д.Кнут. М.:Мир,1978.

6. Кормен Т. Алгоритмы: построение и анализ./Т. Кормен, Ч. Лейзерсон, Р.Ривест. М.: МЦНМО, 2000

7. Кричевский Р.Е. Сжатие и поиск информации/Р.Е. Кричевский. М.: Радио и связь, 1989.

оглавление

4. ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.. 3

4.1. Характерные особенности полустатических структур. 3

4.2. Строки. 3

4.2.1. Логическая структура строки. 3

4.2.2. Операции над строками. 4

4.2.3. Представление строк в памяти. 6

5. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ.. 17

5.1. Связное представление данных в памяти. 17

5.2. Стеки. 18

5.2.1. Логическая структура стека. 18

5.2.2. Машинное представление стека и реализация операций. 19

5.2.3. Стеки в вычислительных системах. 20

5.3. Очереди FIFO.. 22

5.3.1. Логическая структура очереди. 22

5.3.2. Машинное представление очереди FIFO и реализация операций. 23

5.3.3. Очереди с приоритетами. 24

5.3.4. Очереди в вычислительных системах. 25

5.4. Деки. 25

5.4.1. Логическая структура дека. 25

5.4.2. Деки в вычислительных системах. 27

5.5. Связные линейные списки. 27

5.5.1. Машинное представление связных линейных списков. 27

5.5.2. Реализация операций над связными линейными списками. 29

5.6 Мультисписки. 40

5.7. Нелинейные разветвленные списки. 42

5.7.1. Основные понятия. 42

5.7.2. Представление списковых структур в памяти. 44

5.7.3. Операции обработки списков. 45

5.8. Управление динамически выделяемой памятью.. 54

6. ДЕРЕВЬЯ.. 59

6.1. Бинарные деревья. 61

6.2. “Прошитые” деревья. 62

6.3. Графы.. 62

6.4. Алгоритмы поиска путей в графе. 64

7. КЛАССЫ И ОБЪЕКТЫ.. 70

8. РЕКУРСИЯ.. 71

8.1. Некоторые задачи, где можно применить рекурсию.. 72

8.2. Использование рекурсии в графике. 77

9. АЛГОРИТМЫ СЖАТИЯ ИНФОРМАЦИИ.. 83

9.1. Что такое архивирование и зачем оно нужно. 83

9.2. Терминология. 85

9.3. Методы кодирования. 85

9.4. Модели входного потока. 86

9.5. Моделирование и энтропия. 86

9.6. Адаптированные и неадаптированные модели. 87

9.7. Алгоритмы архивации данных. 88

9.8. Сжатие способом кодирования серий (RLE) 89

9.9. Алгоритм Хаффмана. 90

9.10. Арифметическое кодирование. 92

9.11. Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW) 93

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 97

ОГЛАВЛЕНИЕ. 98

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