Алгоритм LZ78 - Анализ алгоритма Лемпеля-Зива

Этот алгоритм генерирует на основе входных данных словарь фрагментов, внося туда фрагменты данных (последовательности байт) по определенным правилам (см. ниже) и присваивает фрагментам коды (номера). При сжатии данных (поступлении на вход программы очередной порции) программа на основе LZ78 пытается найти в словаре фрагмент максимальной длины, совпадающий с данными, заменяет найденную в словаре порцию данных кодом фрагмента и дополняет словарь новым фрагментом. При заполнении всего словаря (размер словаря ограничен по определению) программа очищает словарь и начинает процесс заполнения словаря снова. Реализации этого метода различаются конструкцией словаря, алгоритмами его заполнения и очистки при переполнении [2].

Обычно, при инициализации словарь заполняется исходными (элементарными) фрагментами - всеми возможными значениями байта от 0 до 255. Это гарантирует, что при поступлении на вход очередной порции данных будет найден в словаре хотя бы однобайтовый фрагмент.

Алгоритм LZ78 резервирует специальный код, назовем его "Reset", который вставляется в упакованные данные, отмечая момент сброса словаря. Значение кода Reset обычно принимают равным 256.

Таким образом при начале кодирования минимальная длина кода составляет 9 бит. Максимальная длина кода зависит от объема словаря - количества различных фрагментов, которые туда можно поместить. Если объем словаря измерять в байтах (символах), то очевидно, что максимальное количество фрагментов равно числу символов, а, следовательно, максимальная длина кода равна log2(объем_словаря_в_байтах).

Рассмотрим алгоритм заполнения словаря на примере кодирования фрагмента. Для примера используем данные, состоящие только из символов (букв), кавычки "" не входят в данные: "aaabbabaabaaabab". Пример кодировки приведен в табл. 1

Таблица 1. LZ78-кодирование строки; где запись (i, a) обозначает копирование фразы i перед символом a.

Input:

A

Aa

B

Ba

Baa

Baaa

Bab

Phrase number:

1

2

3

4

5

6

7

Output:

(0,a)

(1,a)

(0,b)

(3,a)

(4,a)

(5,a)

(4,b)

Дальность продвижения вперед указателя неограниченна (т. е. нет окна), поэтому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества требует по мере разбора увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. На практике, словарь не может продолжать расти бесконечно. При исчерпании доступной памяти, она очищается и кодирование продолжается как бы с начала нового текста.

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

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

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

С другой стороны, важным практическим моментом является скорость упаковки, этот параметр тоже зависит от устройства словаря. Основные операции при упаковке:

    1) поиск в словаре фрагмента; 2) вставка в словарь новых фрагментов.

Необходимо, чтобы эти две операции были максимально быстрыми.

Похожие статьи




Алгоритм LZ78 - Анализ алгоритма Лемпеля-Зива

Предыдущая | Следующая