Метод Лемпела-Зива и родственные методы

МЕТОД ЛЕМПЕЛА-ЗИВА И РОДСТВЕННЫЕ МЕТОДЫ

<!-- Сжатие LZ77, LZ78 и LZW (LZ77, LZ78 & LZW Compress) -->

Семейство LZ-компрессоров. Замещающие компрессоры.

Основная идея, используемая в замещающих компрессорах, состоит в замене появления определенной фразы или группы байт во фрагменте данных ссылкой на предыдущее появление этой фразы. Существуют два основных класса методов, названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля (Abraham Lempel), впервые предложивших их в 1977 и 1978.

Алгоритм LZ78

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

·  если последовательность находится в словаре, то в выходной файл заносится код для этой записи;

·  если последовательность представляет собой расширенный вариант последовательности из словаря, то она добавляется в таблицу.

Например, если программа сжатия уже имеет последовательность ABC в словаре и увидит последовательность ABCA, то она вначале занесет в выходной файл код из словаря для ABC, затем для символа A, после чего последовательность ABCA будет добавлена в словарь. Если же она позже встретит ABCAB, то выведет код для ABCA, затем код для символа B и добавит ABCAB в словарь. Каждый раз, когда программа встречает последовательность из словаря, она выдает код и добавляет новую запись, которая на один байт длиннее. Таким образом, каждый раз при повторении последовательности байтов, словарь должен будет расти, чтобы включить продолжение этой последовательности. Обратите внимание на то, что программа должна встретиться с последовательностью ABCABC по крайней мере 6 раз (по числу букв), прежде чем в словаре будет создана запись, содержащая всю последовательность.

Фактически, предшествующий абзац немного искажает реальную картину. Программа сжатия обрабатывает в каждый момент времени лишь один, а не несколько байтов, хотя конечный результат остается по-прежнему таким же. Первоначально словарь содержит всевозможные однобайтовые значения, пронумерованные от 0 до 255, и одну дополнительную запись с номером 256 (о ней я расскажу немного позже). Давайте посмотрим, как программа сжатия LZ читает каждый байт abcabc.

Таблица 1. Пример сжатия

В таблице 1 Вы найдете более длинный пример работы алгоритма