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-техники на практике не в их приб- лижении к оптимальности, а по более прозаической причине - некоторые варианты позволяют осуществлять высоко эффективную реализацию.