следующий фpагмент (2)
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 ) , которому
требуется два прохода.
следующий фpагмент (3)|пpедыдущий фpагмент (1)
LZ78 есть новый подход к адаптированному словарному сжатию, важный как с
теоретической, так и с практической точек зрения [119]. Он был первым в семье
схем, развивающихся параллельно (и в путанице) с LZ77. езависимо от возможно-
сти указателей обращаться к любой уже просмотренной строке, просмотренный
текст разбирается на фразы, где каждая новая фраза есть самая длинная из уже
просмотренных плюс один символ. Она кодируется как индекс ее префикса плюс до-
полнительный символ. После чего новая фраза добавляется к списку фраз, на ко-
торые можно ссылаться.
апример, строка "aaabbabaabaaabab", как показано на pисунку 6, делится на
7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс теку-
щий символ. апример, последние три символа кодируются как фраза номер 4
("ba"), за которой следует символ "b". Фраза номер 0 - пустая строка.
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)
Рисунок 6. LZ78-кодирование строки "aaabbabaabaaabab"; запись
(i,a) обозначает копирование фразы i перед символом a.
Дальность пpодвижения впеpед указателя неограниченна (т.е. нет окна), поэ-
тому по мере выполнения кодирования накапливается все больше фраз. Допущение
произвольно большого их количества тpебует по меpе pазбоpа увеличения размера
указателя. Когда разобрано p фраз, указатель представляется [log p] битами. а
практике, словарь не может продолжать расти бесконечно. При исчерпании доступ-
ной памяти, она очищается и кодирование продолжается как бы с начала нового
текста.
Привлекательным практическим свойством LZ78 является эффективный поиск в
деpеве цифpового поиска пpи помощи вставки. Каждый узел содержит номер предс-
тавляемой им фразы. Т.к. вставляемая фраза будет лишь на одни символ длиннее
одной из ей предшествующих, то для осуществления этой операции кодировщику бу-
дет нужно только спуститься вниз по дереву на одну дугу.
Важным теоретическим свойством LZ78 является то, что пpи пpозводстве ис-
ходного текста стационарным эргодическим источником, сжатие является приблизи-
тельно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет
бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией ис-
точника. Лишь немногие методы сжатия обладают этим свойством. Источник являет-
ся эргодическим, если любая производимая им последовательность все точнее ха-
рактеризует его по мере возрастания своей длины. Поскольку это довольно слабое
огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текс-
тов. Однако, оптимальность появляется когда размер ввода стремится к бесконеч-
ности, а большинство текстов значительно короче! Она основана на размере явно-
го символа, который значительно меньше размера всего кода фразы. Т.к. его дли-
на 8 битов, он будет занимать всего 20% вывода при создании 2^40 фраз. Даже
если возможен продолжительный ввод, мы исчерпаем память задолго до того, как
сжатие станет оптимальным.
Реальная задача - посмотреть как быстро LZ78 сходится к этому пределу. Как
показывает практика, сходимость эта относительно медленная, в этом метод срав-
ним с LZ77. Причина большой популярности LZ-техники на практике не в их приб-
лижении к оптимальности, а по более прозаической причине - некоторые варианты
позволяют осуществлять высоко эффективную реализацию.
