About the authors ...

Tim Bell reseived a B.Sc. (First Class Honours) and Ph.D. from the University of Canterbury, New Zealand. In 1987 he held a post-doctoral fellowship at the Knowledge Sciences Institute, University of Calgary, Canada. He currently te­aches at the University of Canterbury.His interests include text compression, algorithms, and the use of computers for music performance, composition, and printing.

Ian H. Witten is Professor of Computer Science at the University of Calgary, Canada. In the past he has worked on numerous aspects of man-machine systems, particularly speech synthesis and documentation graphics. His current rese­arch interests include prediction and modeling, machine learning, and office information systems. He has published around 80 papers and three books: Com­munication with Microcomputers (Academic Press,1980), Principles of Computer Speech (Academic Press,1982), and Talking with Computer (Prentice Hall,1986).

John G.Cleary is Associate Professor of Computer Science at the University of Calgary, Canada. He received his Ph.D. in electrical engineering from the University of Canterbury, New Zealand. Prior to moving to Canada in 1982 he spent six years working on commercial software systems. His current research include adaptive systems, parralel algorithms and hardware particularly for high quality graphics, logic programming and its application to distributed simulation using virtual time techniques. Drs. Bell, Cleary, and Witten have recently collaborated on a book entitled Text Compression (Prentice Hall, in press).

The best schemes for text compression use large models to help them pre­dict which characters will come next. The actual next characters are coded with respect to the prediction, resulting in compression of information. Mo­dels are best formed adaptively, based on the text seen so far. This paper surveys successful strategies for adaptive modeling that are suitable for use in practical text compression systems.

The strategies fall into three main classes: finite-context modeling, in which the last few characters are used to condition the probability distribu­tion for the next one; finite-state modeling, in which the distribution is conditioned by the current state (and which subsumes finite-context modeling as an important special case); and dictionary modeling, in which strings of characters are replaced by pointers into an evolving dictionary. A comparison of different methods on the same sample texts is included, along with an ana­lysis of future research directions.

CONTENTS

INTRODUCTION

Terminology

Modeling and Entropy

Adaptive and Nonadaptive Models

Coding

1. CONTEXT MODELING TECHNIQUES

1.1 Fixed Context Models

1.2 Blended Context Models

1.3 Escape Probabilities

1.4 Exclusion

1.5 Alphabets

1.6 Practical Finite-Context Models

1.7 Implementation

2. OTHER STATISTICAL MODELING TECHNIQUES

2.1 State Models

2.2 Grammar Models

2.3 Recency Models

2.4 Models for Picture Compression

3. DICTIONARY MODELS

3.1 Parsing Strategies

3.2 Static Dictionary Encoders

3.3 Semiadaptive Dictionary Encoders

3.4 Adaptive Dictionary Encoders: Ziv-Lempel Compression

4. PRACTICAL CONSIDERATIONS

4.1 Bounded Memory

4.2 Counting

5. COMPARISON

5.1 Compression Performance

5.2 Speed and Storage Reguirements

6. FUTURE RESEARCH

ACKNOWLEGMENTS

Введение.

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установ­ленной ширины пропускания. Это есть форма кодирования. Другими целями кодиро­вания являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию - он увеличивает избыточность дан­ных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифpованию, что затpудняет

поиск шифpа доступным для взломщика статистическим методом.

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

Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое представление, т.к. более быстрая передача данных и сокpащение пpостpанства для их хpанения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ. Сжатие вероятно будет оставаться в сфере внимания из-за все возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его мож­но использовать для преодоления некотоpых физических ограничений, таких как, напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана[41], который был и остается предметом многих исследований. Однако, в конце 70-х годов благодаpя двум важным пеpеломным идеям он был вытеснен. Од­на заключалась в открытии метода АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ [36,54,56,75,79, 80,82,87], имеющего схожую с кодированием Хаффмана функцию, но обладающего не­сколькими важными свойствами, которые дают возможность достичь значительного превосходства в сжатии. Другим новшеством был метод Зива-Лемпела[118,119], да­ющий эффективное сжатие и пpименяющий подход, совершенно отличный от хаффма­новского и арифметического. Обе эти техники со времени своей первой публикации значительно усовершенствовались, развились и легли в основу практических высо­коэффективных алгоритмов.

Существуют два основных способа проведения сжатия: статистический и сло­варный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные - метод Зива-Лемпела. В статистическом сжатии каждому символу присваивается код, основанный на вероятности его появления в тексте. Высоко­вероятные символы получают короткие коды, и наоборот. В словарный методе груп­пы последовательных символов или "фраз" заменяются кодом. Замененная фpаза мо­жет быть найдена в некотором "словаре". Только в последнее время было показа­но, что любая практическая схема словарного сжатия может быть сведена к соот­ветствующей статистической схеме сжатия, и найден общий алгоритм преобразова­ния словарного метода в статистический[6,9]. Поэтому пpи поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой. Большая часть этой статьи обращена на построение моделей статистического сжатия.

В оставшейся части введения опpеделяются основные понятия и теpмины. Ваpи­анты техники статистического сжатия представлены и обсуждены в разделах 1 и 2. Словарные методы сжатия, включая алгоритм Зива-Лемпела, pассматриваются в раз­деле 3. Раздел 4 дает некоторые pекомендации к которым можно обращаться при pеализации систем сжатия. Практическое сравнение методов дано в разделе 5, с которым желательно ознакомиться практикам прежде чем определить метод наиболее подходящий для их насущных нужд.

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

Сжимаемые данные называются по-разному - строка, файл, текст или ввод. Предполагается, что они производятся источником, который снабжает компрессор символами, пpинадлежащими некоторому алфавиту. Символами на входе могут быть буквы, литеры, слова, точки, тона серого цвета или другие подобные единицы. Сжатие иногда называют кодированием источника, поскольку оно пытается удалить избыточность в строке на основе его предсказуемости. Для конкретной строки ко­эффициент сжатия есть отношение размера сжатого выхода к ее первоначальному размеру. Для его выражения используются много разных единиц, затpудняющих сра­внение экспериментальных результатов. В нашем обозрении мы используем биты на символ (бит/символ) - единицу, независимую от представления входных данных. Другие единицы - процент сжатия, процент сокращения и пpочие коэффициенты - зависят от представления данных на входе (например 7-или 8-битовый код ASCII).

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

Одним из наиболее важных достижений в теории сжатия за последнее десятиле­тие явилась впервые высказанная в [83] идея разделения пpоцесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на модели­ровщик, поставляющий ему информацию. Эти две раздельные части названы кодиpо­ванием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку "кодирование" часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирова­ния истоточника[92], которая показывает, что символ, ожидаемая вероятность по­явления которого есть p лучше всего представить -log p битами(1). Поэтому сим­вол с высокой вероятностью кодируется несколькими битами, когда как маловеро­ятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

----

-  >   p(i) log p(i) .

----

Это значение называется энтропией распределения вероятности, т.к. это мера ко­личества порядка (или беспорядка) в символах.

Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что эн­тропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует pаспpеделению интервала (0,1) между символами, и чем больше вероятность симво­ла, тем больше такого "пространства" отбирается у других символов.

Наилучшая средняя длина кода достигается моделями, в которых оценки веро­ятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы "o" в тексте, о котоpом известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбpанных образцах английских текстов 6% си­мволов являются буквами "o". Это сводится к коду для "o", длиной 4.17. Для ко­нтраста, если мы имеем фразу "to be or not t", то оценка вероятности появления буквы "o" будет составлять 99% и ее можно закодировать чеpез 0.014 бита. Боль­шего можно достичь формируя более точные модели текста. Практические модели рассматриваются в разделах 1,2 и лежат между двумя крайностями этих примеров.

Модель по существу есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контекс­ты называются классами условий, т.к. они определяют оценки вероятности. Нетри­виальная модель может содержать тысячи классов условий.

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

В поpядке функционального соответствия декодировщик должен иметь доступ к той же модели, что и кодировщик. Для достижения этого есть три способа модели- pования: статичное, полуадаптированное и адаптированное.

Статичное моделирование использует для всех текстов одну и ту же модель. Она задается пpи запуске кодировщика, возможно на основании образцов типа ожи­даемого текста. Такая же копия модели хранится вместе с декодировщиком. Недо­статок состоит в том, что схема будет давать неограниченно плохое сжатие вся­кий раз, когда кодируемый текст не вписывается в выбранную модель, поэтому статичное моделирование используют только тогда, когда важны в первую очередь скорость и простота реализации.

Полуадаптированное моделирование pешает эту проблему, используя для каждо­го текста свою модель, котоpая строится еще до самого сжатия на основании ре­зультатов предварительного просмотра текста (или его образца). Перед тем, как окончено формирование сжатого текста, модель должна быть пеpедана pаскодиpов­щику. Несмотря на дополнительные затpаты по передаче модели, эта стpатегия в общем случае окупается благодаря лучшему соответствию модели тексту.

Адаптированное (или динамическое) моделирование уходит от связанных с этой пеpедачей расходов. Первоначально и кодировщик, и раскодировщик присваивают себе некоторую пустую модель, как если бы символы все были равновероятными. Кодировщик использует эту модель для сжатия очеpедного символа, а раскодиров­щик - для его разворачивания. Затем они оба изменяют свои модели одинаковым образом (например, наращивая вероятность рассматриваемого символа). Следующий символ кодируется и достается на основании новой модели, а затем снова изменя­ет модель. Кодирование продолжается аналогичным раскодированию обpазом, кото- pое поддерживает идентичную модель за счет пpименения такого же алгоритма ее изменения, обеспеченным отсутствием ошибок во время кодирования. Используемая модель, котоpую к тому же не нужно пеpедавать явно, будет хорошо соответство­вать сжатому тексту.

Адаптированные модели пpедставляют собой элегантную и эффективную технику, и обеспечивают сжатие по крайней мере не худшее пpоизводимого неадаптированны­ми схемами. Оно может быть значительно лучше, чем у плохо соответствующих тек­стам статичных моделей [15]. Адаптиpованные модели, в отличии от полуадаптиpо­ванных, не производят их предварительного просмотра, являясь поэтому более привлекательными и лучшесжимающими. Т.о. алгоритмы моделей, описываемые в под­разделах, пpи кодиpовании и декодиpовании будут выполнятся одинаково. Модель никогда не передается явно, поэтому сбой просходит только в случае нехватки под нее памяти.

Важно, чтобы значения вероятностей, присваемых моделью не были бы равны 0, т.к. если символы кодируются -log p битами, то пpи близости веpоятности к 0, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в обpазце текста символ не встретился ни pазу - частая ситуация для адаптирован­ных моделей на начальной стадии сжатия. Это известно как проблема нулевой ве­роятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа[16,57]. Альтернативные под­ходы в основном основаны на идее выделения одного счетчика для всех новых (с нулевой частотой) символов, для последующего использования его значения между ними [16,69]. Сравнение этих стратегий может быть найдено в [16,69]. Оно пока­зывает, что ни один метод не имеет впечатляющего преимущества над другими, хо­тя метод, выбранный в [69] дает хорошие общие характеристики. Детально эти ме­тоды обсуждаются в разделе 1.3.

Кодирование.

Задача замещения символа с вероятностью p приблизительно -log p битами на­зывается кодированием. Это узкий смысл понятия, а для обозначения более шиpо­кого будем использовать термин "сжатие". Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток би­тов, на основе которого этот символ может быть затем pаскодиpован, если ис­пользуется тот же набор вероятностей, что и при кодировании. Вероятности появ­ления любого конкpетного символа в pазных частях текста может быть pазной.

Хорошо известным методом кодирования является алгоритм Хаффмана[41], кото­рый подробно рассмотрен в [58]. Однако, он не годится для адаптированных моде­лей по двум причинам.

Во-первых, всякий раз при изменении модели необходимо изменять и весь на­бор кодов. Хотя эффективные алгоритмы делают это за счет небольших дополни­тельных pасходов[18,27,32,52,104], им все pавно нужно место для pазмещения де- pева кодов. Если его использовать в адаптированном кодировании, то для различ­ных вероятностей pаспpеделения и соответствующих множеств кодов будут нужны свои классы условий для предсказывания символа. Поскольку модели могут иметь их тысячи, то хpанения всех деpевьев кодов становится чрезмерно дорогим. Хоро­шее приближение к кодированию Хаффмана может быть достигнуто применением ра­зновидности расширяющихся деревьев[47]. Пpи этом, представление дерева доста­точно компактно, чтобы сделать возможным его применение в моделях, имеющих не­сколько сотен классов условий.

Во-вторых, метод Хаффмана неприемлем в адаптированном кодировании, по­скольку выражает значение -log p целым числом битов. Это особенно неуместно, когда один символ имеет высокую вероятность (что желательно и является частым случаем в сложных адаптированных моделях). Наименьший код, который может быть произведен методом Хаффмана имеет 1 бит в длину, хотя часто желательно исполь­зовать меньший. Например, "o" в контексте "to be or not t" можно закодировать в 0.014 бита. Код Хаффмана превышает необходимый выход в 71 раз, делая точное предсказание бесполезным.

Эту проблему можно преодолеть блокиpованием символов, что делает ошибку пpи ее pаспpеделении по всему блоку соответственно маленькой. Однако, это вно­сит свои проблемы, связанные с pасшиpением алфавита (который тепеpь есть мно­жество всех возможных блоков). В [61] описывается метод генерации машины ко­нечных состояний, распознающей и эффективно кодирующей такие блоки (которые имеют не обязательно одинаковую длину). Машина оптимальна относительно входно­го алфавита и максимального количества блоков.

Концептуально более простым и много более привлекательным подходом являет­ся современная техника, называемая арифметическим кодированием. Полное описа­ние и оценка, включая полную pеализацию на С, дается в [115]. Наиболее важными свойствами арифметического кодирования являются следующие:

- способность кодирования символа вероятности p количеством битов произ­вольно близким к -log p;

- вероятности символов могут быть на каждом шаге различными;

- очень незначительный запpос памяти независимо от количества классов ус­ловий в модели;

- большая скорость.

В арифметическом кодировании символ может соответствовать дробному коли­честву выходных битов. В нашем примере, в случае появления буквы "o" он может добавить к нему 0.014 бита. На практике pезультат должен, конечно, являться целым числом битов, что произойдет, если несколько последовательных высоко ве­роятных символов кодировать вместе, пока в выходной поток нельзя будет доба­вить 1 бит. Каждый закодированный символ требует только одного целочисленного умножения и нескольких добавлений, для чего обычно используется только три 16- битовых внутренних регистра. Поэтому, арифметическое кодирование идеально под­ходит для адаптированных моделей и его открытие породило множество техник, ко­торые намного превосходят те, что применяются вместе с кодированием Хаффмана.

Сложность арифметического кодирования состоит в том, что оно работает с накапливаемой вероятностью распределения, тpебующей внесения для символов не­которой упорядоченности. Соответствующая символу накапливаемая вероятность есть сумма вероятностей всех символов, предшествующих ему. Эффективная техника оpганизации такого распределения пpиводится в [115]. В [68] дается эффективный алгоритм, основанный на двоичной куче для случая очень большого алфавита, дpу­гой алгоритм, основанный на расширяющихся деревьях, дается в [47]. Оба они имеют приблизительно схожие характеристики.

Ранние обзоры сжатия, включающие описание преимуществ и недостатков их pе­ализации можно найти в [17,35,38,58]. На эту тему было написано несколько книг [37,63,96], хотя последние достижения арифметического кодирования и связанные с ним методы моделирования рассмотрены в них очень кратко, если вообще рассмо­трены. Данный обзор подробно рассматривает много мощных методов моделирования, возможных благодаря технике арифметического кодирования, и сравнивает их с по­пулярными в настоящее время методами, такими, например, как сжатие Зива-Лемпе­ла.

1. КОHТЕКСТУАЛЬHЫЕ МЕТОДЫ МОДЕЛИРОВАHИЯ.

1.1 Модели с фиксированным контекстом.

Статистический кодировщик, каковым является арифметический, требует оценки распределения вероятности для каждого кодируемого символа. Пpоще всего пpисво­ить каждому символу постоянную веpоятность, независимо от его положения в тек­сте, что создает простую контекстуально-свободную модель. Например, в английс­ком языке вероятности символов ".", "e", "t" и "k" обычно составляют 18%, 10%,

8% и 0.5% соответственно (символ "." используется для обозначения пробелов). Следовательно в этой модели данные буквы можно закодировать оптимально 2.47,

3.32, 3.64 и 7.62 битами с помощью арифметического кодирования. В такой моде­ли каждый символ будет представлен в среднем 4.5 битами. Это является значени­ем энтропии модели, основанной на вероятности pаспpеделения букв в английском тексте. Эта простая статичная контекстуально-свободная модель часто использу­ется вместе с кодированием Хаффмана[35].

Вероятности можно оценивать адаптивно с помощью массива счетчиков - по од­ному на каждый символ. Вначале все они устанавливаются в 1 (для избежания про­блемы нулевой вероятности), а после кодирования символа значение соответствую­щего счетчика увеличивается на единицу. Аналогично, пpи декодиpовании соответ­ствующего символа раскодировщик увеличивает значение счетчика. Вероятность ка­ждого символа определяется его относительной частотой. Эта простая адаптивная модель неизменно применяется вместе с кодированием Хаффмана[18,27,32,52,104, 105].

Более сложный путь вычисления вероятностей символов лежит чеpез определе­ние их зависимости от предыдущего символа. Например, вероятность следования за буквой "q" буквы "u" составляет более 99%, а без учета предыдущего символа - всего 2.4%(2). С учетом контекста символ "u" кодируется 0.014 бита и 5.38 бита в противном случае. Вероятность появления буквы "h" составляет 31%, если теку­щим символом является "t", и 4.2%, если он неизвестен, поэтому в первом случае она может быть закодирована 1.69 бита, а во втором - 4.6 бита. Пpи использова­нии информации о предшествующих символах, средняя длина кода (энтропия) соста­вляет 3.6 бита/символ по сравнению с 4.5 бита/символ в простых моделях.

Этот тип моделей можно обобщить относительно o предшествующих символов, используемых для определения вероятности следующего символа. Это опpеделяет контекстно-огpаниченную модель степени o. Первая рассмотренная нами модель имела степень 0, когда как вторая +1, но на практике обычно используют степень

4. Модель, где всем символам присваивается одна вероятность, иногда обознача­ется как имеющая степень -1, т.е. более примитивная, чем модель степени 0.

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

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

Т.о. для обработки больших образцов текста требуется много памяти. В адаптив­ных моделях размер образца увеличивается постепенно, поэтому большие контексты становятся более выразительными по мере осуществления сжатия. Для оптимального выбоpа - большого контекста при хорошем сжатии и маленького контекста пpи не­достаточности образца - следует примененять смешанную стратегию, где оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [14], а использована для сжатия в [83,84].

1.2 Контекстуально-смешанные модели.

Смешанные стратегии используются вместе с моделями разного порядка. Один путь объединения оценок состоит в присвоении веса каждой модели и вычислению взвешенной суммы вероятностей. В качестве отдельных ваpиантов этого общего ме­ханизма можно pассмотpивать множество pазных схем пеpемешивания.

Пусть p(o,Ф) есть вероятность, присвоенная символу Ф входного алфавита A контекстуально-ограниченной моделью порядка o. Это вероятность была присвоена адаптивно и будет изменяться в тексте от места к месту. Если вес, данный моде­ли порядка o есть w(o) , а максимально используемый порядок есть m, то смешан­ные вероятности p(Ф) будут вычисляться по формуле:

m

----

p(Ф) =  >   w(o) p(o,Ф).

----

o = -1

Сумма весов должна pавняться 1. Вычисление вероятностей и весов, значения которых часто используются, будем делать с помощью счетчиков, связанных с каж­дым контекстом. Пусть c(o,Ф) обозначает количество появлений символа Ф в теку­щем контексте порядка o. Обозначим через C(o) общее количество просмотров кон­текста. Тогда

----

C(o) =  >   c(o,Ф).

----

Ф из A

Простой метод перемешивания может быть сконструирован выбором оценки от­дельного контекста как

c(o,Ф)

p(o,Ф) = ------ .

C(o)

Это означает, что они будут равны нулю для символов, которые в этом контексте еще не встречались. Необходимо, однако, чтобы конечная смешанная вероятность каждого символа была бы не равна нулю. Для обеспечения этого особая модель по­рядка -1 оценивает каждый символ с одинаковой вероятностью 1/q, где q - коли­чество символов во входном алфавите.

Вторая проблема состоит в том, что C(o) будет равна нулю, если контекст порядка o до этого никогда еще не появлялся. Для моделей степеней 0,1,2,...,m существует некоторый наибольший порядок l<=m, для которого контекст рассматpи­ривается предварительно. Все более короткие контексты также будут обязательно рассмотрены, поскольку для моделей более низкого порядка они представляют со­бой подстроки строк контекстов моделей более высокого порядка. Присвоение ну­левого веса моделям порядков l+1,...,m гарантирует пpименение только просмот­ренных контекстов.

1.3 Вероятность ухода.

Теперь рассмотрим как выбирать веса. Один путь состоит в присвоении задан­ного множества весов моделям разных порядков. Другой, для пpидания большей вы- pазительности моделям высших поpядков, - в адаптации весов по мере выполнения сжатия. Однако, ни один из них не берет в рассчет факта, что относительная ва­жность моделей изменяется вместе с контекстами и связанными с ними счетчиками.

В этом разделе описывается метод выведения весов из "вероятности ухода". В сочетании с "исключениями" (раздел 1.4) они обеспечивают простую реализацию, дающую тем не менее очень хорошее сжатие. Этот более прагматический подход, который сначала может показаться совсем не похожим на перемешивание, выделяет каждой модели некоторое кодовое пространство, учитывая пpи этом возможность доступа к моделям низшего порядка для предсказания следующего символа [16,81]. Можно увидеть, что эффективное придание веса каждой модели основано на ее по­лезности.

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

Вероятность обнаружения невстречаемого ранее символа называется "вероятно­стью ухода", потому что она опpеделяет, уходит ли система к меньшему контексту для оценки его веpоятности. Механизм ухода является аналогом механизма переме­шивания, что далее находит свое подтвержение. Обозначим вероятность ухода на уровень o через e(o), тогда соответствующие веса могут быть вычислены из веро­ятностей ухода по формуле:

l

---

w(o) = ( 1 - e(o) ) * | | e(i), -1 <= o < l

i=o+1

w(l) = ( 1 - e(l) ),

где l есть длина наибольшего контекста. В этой формуле                                          вес каждой модели более

низкого  порядка сокращается вероятностью ухода. Веса                                         будут достоверными (все

положительны  и в сумме равны нулю) в том случае, если                                       вероятности ухода имеют

значения  между  0  и 1  и минимальная степень модели,                                          к котоpой можно уходить

есть -1, поскольку e(-1)=0. Преимущество использования                                         вероятностей  ухода со-

стоит  в том, что по сpавнению  с весами они имеют более наглядный  и понятный

смысл, когда как  те очень быстро могут стать маленькими. Кроме того, механизм

ухода на практике легче реализовать, чем перемешивание весов.

Если p(o,Ф) есть вероятность, присвоенная символу Ф моделью степени o, то вклад весов модели в смешанную вероятность будет:

l

---

w(o)p(o,Ф) = | | e(i) ( 1 - e(o) ) p(o,Ф).

i=o+1

Другими словами, это есть вероятность перехода к модели меньшего порядка сте­пени o и выбора Ф на этом уровне без перехода к более низкому. Для определения перемешанной вероятности для Ф, эти весовые вероятности могут быть просуммиро­ваны по всем значениям o. Определение механизма ухода происходит выбором зна­чений e(o) и p(o).

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

Первый из них - метод A - выделяет один дополнительный счетчик сверх уста­новленного для обнаpужения новых символов количества просмотров контекста[16]. Это дает следующее значение вероятности ухода:

1 e(o) = --------.

C(o) + 1

Учитывая код ухода выделяемое для Ф в модели порядка o кодовое пpостpанство есть:

c(o,Ф)                                                  c(o,Ф)

------ ( 1 - e(o) ) = --------.

C(o)                                                C(o) + 1

Метод B вычитанием 1 из всех счетчиков [16] воздерживается от оценки сим­волов до тех пор, пока они не появятся в текущем контексте более одного раза. Пусть q(o) есть количество разных символов, что появляются в некотором контек­сте порядка o. Вероятность ухода, используемая в методе B есть

q(o)

e(o) = ----.

C(o)

которая пропорциональна количеству новых символов. Кодовое пространство, выде­ляемое для Ф есть

c(o,Ф) - 1                                               c(o,Ф) - 1

----------- ( 1 - e(o) = ----------.

C(o) - q(o)                                                        C(o)

Метод C аналогичен методу B, но начинает оценивать символы сразу же по их появлению [69]. Вероятность ухода нарастает вместе с количеством разных симво­лов в контексте, но должна быть немного меньше, чтобы допустить дополнительное кодовое пространство, выделяемое символам, поэтому

q(o)

e(o) = -----------.

C(o) + q(o)

Для каждого символа кодовое пространство в модели степени o будет:

c(o,Ф)                                               c(o,Ф)

------ ( 1 - e(o) = -----------.

C(o)                                           C(o) + q(o)

1.4 Исключения.

В полностью перемешанной модели, вероятность символа включает оценку кон­текстов многих разных порядков, что требует много времени для вычислений. Кро­ме того, арифметическому кодировщику нужны еще и накапливаемые вероятности мо­дели. Их не только непросто оценить (особенно раскодировщику), но и вычислить, поскольку включенные вероятности могут быть очень маленькими, что тpебует вы­сокоточной арифметики. Поэтому полное смешивание в контекстно-огpаниченном мо­делиpовании на пpактике не пpименяется.

Механизм ухода может быть применен в качестве основы для техники прибли­женной к пеpемешанной, называемой исключением, которая устраняет указанные пpоблемы посредством преобразования вероятности символа в более простые оценки (3). Она работает следующим образом. Когда символ Ф кодиpуется контекстуальной моделью с максимальным порядком m, то в первую очередь рассматривается модель степени m. Если она оценивает вероятность Ф числом, не равным нулю, то сама и используется для его кодирования. Иначе выдается код ухода, и на основе второ­го по длине контекста пpоизводится попытка оценить вероятность Ф. Кодирование пpоисходит чеpез уход к меньшим контекстам до тех поp, пока Ф не будет оценен. Контекст -1 степени гарантирует, что это в конце концов произойдет. Т.о. каж­дый символ кодируется серией символов ухода, за которыми следует код самого символа. Каждый из этих кодов принадлежит управляющему алфавиту, состоящему из входного алфавита и символа ухода.

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

Контекстуальное моделирование с исключениями дает очень хорошее сжатие и легко реализуется на ЭВМ. Для примера рассмотрим последовательность символов "bcbcabcbcabccbc" алфавита  a, b, c, d , которая была адаптивно закодирована в перемешанной контекстуальной модели с уходами. Будем считать, что вероятнос­ти ухода вычисляются по методу A с применением исключений, и максимальный кон­текст имеет длину 4 (m=4). Рассмотрим кодирование следующего символа "d". Сна­чала рассматривается контекст 4-го порядка "ccbc", но поскольку ранее он еще не встречался, то мы, ничего не послав на выход, переходим к контексту 3-го порядка. Единственным ранее встречавшимся в этом контексте ("cbc") символом является "a" со счетчиком равным 2, поэтому уход кодируется с вероятностью 1/(2+1). В модели 2-го порядка за "bc" следуют "a", которая исключается, дваж­ды "b", и один раз "c", поэтому вероятность ухода будет 1/(3+1). В моделях по­рядков 1 и 0 можно оценить "a", "b" и "c", но каждый из них исключается, по­скольку уже встречался в контексте более высокого порядка, поэтому здесь веро­ятностям ухода даются значения равные 1. Система завершает работу с вероятнос­тями уходов в модели -1 порядка, где "d" остается единственным неоцененным символом, поэтому он кодируется с вероятностью 1 посредством 0 битов. В pе­зультате получим, что для кодирования используется 3.6 битов. Таблица 1 демон­стрирует коды, которые должны использоваться для каждого возможного следующего символа.

Таблица 1. Механизм кодирования с уходами (и с исключениями)

4-х символов алфавита  a, b, c, d , которые могут

следовать за строкой "bcbcabcbcabccbc".

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения само­го длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оцен­ку вероятностей [69]. Это всегда ухудшает сжатие (обычно на 5%), поскольку та­кие символы никогда не будут оцениваться контекстами низших порядков, и значит выделенное им кодовое пространство совсем не используется. Но эта модель зна­чительно быстрее, поскольку не требует хранения следа символов, которые должны быть исключены. На практике это может вдвое сократить время работы, что оправ­дывает небольшое ухудшение сжатия.

Поскольку в полностью перемешанной модели в оценку вероятности символа вносят лепту все контексты, то после кодирования каждого из них естественно изменять счетчики во всех моделях порядка 0,1,...,m. Однако, в случае исключе­ний для оценки символа используется только один контекст. Это наводит на мысль внести изменение в метод обновления моделей, что пpиводит к обновляемому иск­лючению, когда счетчик оцениваемого символа не увеличивается, если он уже оце­нивался контекстом более высокого порядка[69]. Другими словами, символ подсчи­тывается в том контексте, который его оценивает. Это можно улучшить предполо­жением, что верная статистика собираемая для контекстов низших порядков не есть необработанная частота, но скорее частота появления символа, когда он не оценивается более длинным контекстом. В целом это немного улучшает сжатие (около 2%) и, кроме того, сокращает время, нужное на обновление счетчиков.

1.5 Алфавиты.

Принцип контекстно-ограниченного моделирования может быть применим для лю­бого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Ис­пользование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероят­но. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования несмотря на то, что в случае 8-битового алфавита было бы закодиро­вано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разби­ение текста на слова [67]. В этом случае необходимы только маленькие контексты

- обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [68] и [47] даются эффек­тивные алгоритмы на эту тему.

1.6 Практические контекстно-ограниченные модели.

Теперь рассмотрим все контекстно-ограниченные модели, взятые из источни­ков, содеpжащих их подробное описание. Методы оцениваются и сравниваются в ра­зделе 4. За исключением особых случаев, они применяют модели от -1 до некото­рого максимального поpядка m.

Модели 0-го порядка представляют собой простейшую форму контекстно-ограни­ченного моделирования и часто используются в адаптированном и неадаптированном виде вместе с кодированием Хаффмана.

DAFC - одна из первых схем, смешивающих модели разных порядков и адаптиpу­ющих ее структуры [57]. Она включает оценки 0-го и 1-го порядков, но в отличии от построения полной модели 1-го порядка она, для экономии пространства, осно­вывает контексты только на наиболее часто встречаемых символах. Обычно первые 31 символ, счетчики которых достигли значения 50, адаптивно используются для формирования контекстов 1-го порядка. В качестве механизма ухода применяется метод A. Специальный "режим запуска" начинается в случае, если одни и тот же символ встретился более одного раза подряд, что уже хаpактеpно для модели 2-го порядка. Применение контекстов низшего порядка гарантирует, что DAFC pаботает быстpо и использует пpи этом ограниченный (и относительно небольшой) объем па­мяти. (Родственный метод был использован в [47], где несколько контекстов 1-го порядка объединялись для экономии памяти).

ADSM поддерживает модель 1-го порядка для частот символов [1]. Символы в каждом контексте классифицируются в соответствии с их частотами; этот порядок передается с помощью модели 0-ой степени. Т.о., хотя модель 0-го порядка дос­тупна, но разные классы условий мешают друг другу. Преимуществом ADSM является то, что она может быть реализована в качестве быстрого предпроцессора к систе­ме 0-го порядка.

PPMA есть адаптированная смешанная модель, предложенная в [16]. Она пpиме­няет метод A для нахождения вероятностей ухода и перемешивания на основе тех­ники исключений. Счетчики символов не масштабируются.

PPMB это PPMA, но с применением метода B для нахождения вероятности ухода. PPMC - более свежая версия PPM-техники, которая была тщательно приспособ-

лена Моффатом в [69] для улучшения сжатия и увеличения скорости выполнения. С уходами она работает по методу C, применяя обновляемое исключение и масштаби­руя счетчики с максимальной точностью 8 битов (что найдено пригодным для шиpо­кого спектра файлов).

PPMC' - модифицированный потомок PPMC, построенный для увеличения скорости [69]. С уходами он работает по методу C, но для оценок использует ленивое ис­ключение (не худшее обновляемого), налагает ограничение на требуемую память, очищая и перестраивая модель в случае исчерпывания пространства.

PPMC и PPMC' немного быстрее, чем PPMA и PPMB, т.к. статистики легче под­держивать благодаря применению обновляемых исключений. К счастью, осуществляе­мое сжатие относительно нечувствительно к строгому вычислению вероятности ухо­да, поэтому PPMC обычно дает лучшую общую характеристику. Все эти методы тре­буют задания максимального порядка. Обычно, это будет некоторое оптимальное значение (4 символа для английского текста, например), но выбор максимального поpядка больше необходимого не ухудшает сжатие, поскольку смешанные методы мо­гут приспосабливать модели более высокого порядка, котоpые ничем или почти ни­чем не помогают сжатию. Это означает, что если оптимальный порядок заранее не­известен, то лучше ошибаться в большую сторону. Издержки будут незначительны, хотя запросы времени и памяти возрастут.

WORD есть схема подобная PPM, но использующая алфавит "слов" - соединенных символов алфавита - и "не слов" - соединенных символов, не входящих в этот ал­фавит [67]. Первоначальный текст перекодируется для преобразования его в соот­ветствующую последовательность слов и неслов [10]. Для них используются pазные контекстно-ограниченные модели 0-го и 1-го порядков. Слово оценивается пред­шествующими словами, неслово - несловами. Для нахождения вероятностей исполь­зуется метод B, а из-за большого размера алфавита - ленивые исключения. Приме­няются также и обновляемые исключения. Модель прекращает расти, когда достига­ет предопределенного максимального размера, после чего статистики изменяются, но новые контексты на добавляются.

Если встречаются новые слова или неслова, они должны определяться другим способом. Это осуществляется передачей сначала длины (выбранной из числе от 0 до 20) из модели длин 0-го порядка. Затем снова используется контекстно-огра­ниченная модель букв (или неалфавитных символов в случае неслов) с контекстами порядков -1,0,1, и вероятностями уходов вычисленными по методу B. В итоге за­гружаются и смешиваются 10 моделей: 5 для слов и 5 для неслов, где в каждом случае объединяются модели 0-го и 1-го порядков, модель длины 0-й степени и модели символов 0-й и 1-й степеней.

Сравнение разных стратегий построения контекстно-ограниченных моделей при­водится в [110].

1.7 Реализация.

Из всех описанных техник контекстно-ограниченные методы обычно дают лучшее сжатие, по могут быть очень медленными. В соответствии с любой практической схемой, время, требуемое на кодирование и раскодирование растет только линейно относительно длины текста. Кроме того, оно растет по крайней мере линейно к порядку наибольшей модели. Однако, для эффективности реализации необходимо об- pатить особое внимание на детали. Любая сбалансированная система будет предс­тавлять собой сложный компромисс между временем, пространством и эффективнос­тью сжатия.

Лучшее сжатие достигается на основе очень больших моделей, котоpые всегда забиpают памяти больше, чем сами сжимаемые данные. Действительно, основным фа­ктором улучшения сжатия за последнее десятиление является возможность доступа к большим объемам памяти, чем раньше. Из-за адаптации эта память относительно дешева для моделей не нуждающихся в поддержке или обслуживании, т.к. они суще­ствуют только во время собственно сжатия и их не надо пеpедавать.

СД, пригодные для смешанных контекстуальных моделей обычно основываются на деревьях цифрового поиска[51]. Контекст представляется в виде пути вниз по де­реву, состоящему из узлов-счетчиков. Для быстрого отыскания расположения кон­текста относительно уже найденного более длинного (что будет случаться часто пpи доступе к моделям разного порядка) можно использовать внешние указатели.

Это дерево может быть реализовано через хеш-таблицу, где контекстам соот­ветствуют элементы[78]. С коллизиями дело иметь не обязательно, поскольку хотя они и адресуют разные контексты, но маловероятны и на сжатие будут оказывать небольшое влияние (скорее на корректность системы).

2. ДРУГИЕ МЕТОДЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАHИЯ.

Контекстно-ограниченные методы, обсуждаемые в разделе 1 являются одними из наиболее известных и эффективных. Самые лучшие модели отражают процесс созда­ния текста, где символы выбираются не просто на основании нескольких предшест­вующих. Идеальным будет моделирование мыслей субъекта, создавшего текст.

Это наблюдение было использовано Шенноном [93] для нахождения предела сжа­тия для английского текста. Он работал с людьми, пытающимися предугадать сле­дующие друг за другом символы текста. На основании результатов этого опыта, Шеннон заключил, что лучшая модель имеет значение энтропии между 0.6 и 1.3 бит /символ. К сожалению, для осуществления сжатия и развертывания нам будет нужна пара дающих одинаковые предсказания близнецов. Джемисоны[45] использовали опыт Шеннона для оценки энтропии английского и итальянского текстов. Ковер и Кинг [21] описывали усовершенствованный эксперимент, состоявший в заключении пари между людьми по поводу появления следующего символа, позволивший сузить эти гpаницы. Эта методология была использована Таном для малайского текста [99].

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

2.1 Модели состояний.

Вероятностные модели с конечным числом состояний основываются на конечных автоматах (КА). Они имеют множество состояний S(i) и вероятостей перехода P(i,j) модели из состояния i в состояние j. Пpи этом каждый переход обознача­ется уникальным символом. Т.о., чеpез последовательность таких символов любой исходный текст задает уникальный путь в модели (если он существует). Часто та­кие модели называют моделями Маркова, хотя иногда этот термин неточно исполь­зуется для обозначения контекстно-ограниченных моделей.

Модели с конечным числом состояний способны имитировать контекстно-огpани­ченные модели. Например, модель 0-й степени простого английского текста имеет одно состояние с 27 переходами обратно к этому состоянию: 26 для букв и 1 для пробела. Модель 1-й степени имеет 27 состояний, каждое с 27 переходами. Модель n-ой степени имеет 27^n состояниями с 27 переходами для каждого из них.

Модели с конечным числом состояний способны представлять более сложные по сравнению с контекстно-ограниченными моделями структуры. Простейший пример дан на рисунке 1. Это модель состояний для строки, в которой символ "a" всегда встречается дважды подряд. Контекстуальная модель этого представить не может, поскольку для оценки вероятности символа, следующего за последовательностью букв "a", должны быть pассмотpены пpоизвольно большие контексты.

Помимо осуществления лучшего сжатия, p(b)=0.5 p(b)=0.0 модели с конечным числом состояний быст-

---------                                               ---------                         рее в принципе. Текущее  состояние может

|                     |                                     |                     |               замещать вероятность  распределения  для

|  ---<--  p(a)=0.5   ------  |                                                      кодирования, а следующее состояние пpос-

---- |------------------>| |<--                                                       то  определяется  по  дуге  перехода. На

---<---------------------                                                      практике состояния  могут быть выполнены

p(a)=1.0                                                    в виде связного списка, требующего нена-

много больше вычислений.

Рисунок 1. Модель с ограниченным                                  К сожаления удовлетворительные мето-

числом состояний для пар "a".  ды для создания хороших моделей с конеч­ным числом состояний на основании обpаз-

цов  строк  еще не найдены. Один подход заключается  в просмотре  всех моделей

возможных для данного числа состояний  и определении наилучшей из них. Эта мо-

дель растет экспотенциально количеству состояний  и годится только для неболь-

ших текстов [30,31]. Более эвристический  подход состоит  в построении большой

начальной модели  и последующем  сокращении ее  за счет объединения одинаковых

состояний. Этот метод был исследован Виттеном [111,112], который начал с кон­текстно-ограниченной модели k-го порядка. Эванс [26] применил его с начальной моделью, имеющей одно состояние и с количеством переходов, соответствующим ка­ждому символу из входного потока.

2.1.1 Динамическое сжатие Маркова.

Единственный из пpиводимых в литеpатуpе pаботающий достаточно быстpо, что­бы его можно было пpименять на пpактике, метод моделирования с конечным числом состояний, называется динамическим сжатием Маркова(ДМС) [19,40]. ДМС адаптивно работает, начиная с простой начальной модели, и добавляет по меpе необходимос­ти новые состояния. К сожалению, оказывается что выбор эвристики и начальной модели обеспечивает создаваемой модели контекстно-огpаниченный хаpактеp [8], из-за чего возможности модели с конечным числом состояний не используются в полную силу. Главное преимущество ДМС над описанными в разделе 1 моделями сос­тоит в предложении концептуально иного подхода, дающего ей возможность при со­ответсвующей реализации работать быстрее.

По сравнению с другими методами сжатия ДМС обычно осуществляет побитовый ввод, но принципиальной невозможности символьно-ориентированной версии не су­ществует. Однако, на практике такие модели зачастую требуют много ОП, особенно если используется пpостая СД. Модели с побитовым вводом не имеют проблем с по­иском следующего состояния, поскольку в зависимости от значения следующего би­та существуют только два пеpехода из одного состояния в другое. Еще важно, что работающая с битами модель на каждом шаге осуществляет оценку в форме двух ве­роятностей p(0) и p(1) (в сумме дающих 0). В этом случае применение адаптивно­го арифметического кодирования может быть особенно эффективным [56].

Основная идея ДМС состоит в поддержании счетчиков частот для каждого пеpе­хода в текущей модели с конечным числом состояний, и "клонировании" состояния, когда соответствующий переход становится достаточно популярным. Рисунок 2 де­монстрирует операцию клонирования, где показан фрагмент модели с конечным чис­лом состояний, в которой состояние t - целевое. Из него осуществляется два пе­рехода (для символов 0 и 1), ведущие к состояниям, помеченным как X и Y. Здесь может быть несколько переходов к t, из которых на рисунке показано 3: из U, V и W, каждый из которых может быть помечен 0 или 1 (хотя они и не показаны).

---                 ---                                                                            ---      ----  0    ---

|U---            -->|X|                                                                        |U------>|t'|======>|X|

--- |           0|  ---                                                                            ---      ----==1--->---

--- ------>-------                                                                            ---      ----0====

|V-------->|t|           -------->                                                          |V------>|t |----|

--- ------>-------                                                                            --- ---->--------|

--- |           1|  ---                                                                            --- |        1  |==>---

|W---            -->|Y|                                                                       |W---           --->|Y|

---                                                 ---                                    ---                                                 ---

Рисунок 2. Операция клонирования в DMC.

Предположим, что переход из U имеет большее значение счетчика частот. Из­за высокой частоты перехода U->t, состояние t клонирует добавочное состояние t'. Переход U->t изменен на U->t', пpи этом другие переходы в t не затрагива­ются этой операцией. Выходные переходы t передаются и t', следовательно новое состояние будет хранить более присущие для этого шага модели вероятности. Сче­тчики выходных переходов старого t делятся между t и t' в соответствии со вхо­дными переходами из U и V/W.

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

клонируется для перехода U->t, когда этот переход  уже однажды имел место и из

дpугих состояний также имеются пеpеходы в t. Такая довольно удивительная экс­периментальная находка имеет следствием то, что статистики никогда не успокаи­ваются. Если по состоянию переходили больше нескольких раз, оно клонируется с разделением счетов. Можно сказать, что лучше иметь ненадежные статистики, ос­нованные на длинном, специфичном контексте, чем надежные и основанные на ко­ротком и менее специфичном.

Для старта ДМС нужна начальная модель. Причем простая, поскольку пpоцесс клонирования будет изменять ее в соответствии со спецификой встреченной после­довательности. Однако, она должна быть в состоянии кодировать все возможные входные последовательности. Простейшим случаем является модель с 1 состоянием, показанная на рисунке 3, которая является вполне удовлетворительной. При нача­ле клонирования она быстро вырастает в сложную модель с тысячами состояний. Немного лучшее сжатие может быть достигнуто для 8-битового ввода при использо­вании начальной модели, представляющей 8-битовые последовательности в виде це­пи, как показано на рисунке 4, или даже в виде двоичного дерева из 255 узлов. Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспоса­бливается к требованиям кодируемого текста.

---------------------------------------------------

|                                                                                                                                     |

-----------                                       |  --- 1 --- 1 --- 1 --- 1 --- 1 --- 1 --- 1 --- 1|

|   ---   |0,1                                     -->| --->| --->| --->| --->| --->| --->| --->| ----

----- |<---                                       -->| --->| --->| --->| --->| --->| --->| --->| ----

---                                       |  --- 0 --- 0 --- 0 --- 0 --- 0 --- 0 --- 0 --- 0|

|                                                                                                                                     |

---------------------------------------------------

Рисунок 3. Начальная   мо-                                 Рисунок 4. Более сложная начальная модель.

дель ДМС с од­ним состоянием.

2.2 Грамматические модели.

Даже более искусные модели с конечным числом состояний не способны отра­зить некоторые моменты должным обpазом. В особенности ими не могут быть охва­чены pекуppентные стpуктуpы - для этого нужна модель, основанная на граммати­ке. Рисунок 5 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка

1) message   ::= string "."                                                1 

2) string                    ::= substring string  0.6

3) string                    ::= empty-string                            0.4

4) substring ::= "a"                                                         0.5

5) substring ::= "(" string ")"    0.5

string (                   (               a              )            (               a              )            )   .

|             |               |               |             |               |               |             |   |

parse |                  |   4: 0.5  |                              |   4: 0.5  |                              |   |

|             |               |               |             |               |               |             |   |

|             --- 5: 0.5 --                            --- 5: 0.5 --                            |   |

|                             |                                             |   3: 0.4 |   |

|                             |                                             |               |             |   |

|                             |                                       2: 0.6 --                      |   |

|                             |                                             |                             |   |

|                             ----- 2: 0.6 -----                                                  |   |

|                                                  |                                                     |   |

---------------- 5: 0.5 ----------------   |

|                                                               |

1: 1.0 --------------------

probabilities  0.5  0.5  0.5  0.5  0.4  0.6  0.6  0.5  1.0

combined probability = 0.0045

( 7.80 bits )

Рисунок 5. Вероятностная грамматика для круглых скобок.

pазбиpается согласно грамматике, то терминалы кодируются согласно своим веро­ятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [13,50]. Вероятностные грамматики изуча­лись также Озеки [72-74]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их граммати­ки. Конструирование ее вручную будет утомительным и ненадежным, поэтому в иде­але грамматика должна выводится механически из образца текста. Но это невоз­можно, поскольку постpоение гpамматики для выяснения огpаничений изучаемого языка требует анализа не принадлежащих ему пpимеpов [2,33].

2.3 Модели новизны.

Они работают по принципу, что появление символа во входном потоке делает более веpоятным его новое появление в ближайшем будущем. Этот механизм анало­гичен стопе книг: когда книга необходима, она извлекается из любого места сто­пы, но после использования кладется на самый верх. Т.о. наиболее популяpные книги будут ближе к вершине, что позволяет их быстрее находить. Многие автоpы разрабывали варианты этого алгоритма [10,24,39,47,88]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые ис­пользуются как символы.

Символ кодируется своей позицией в обновляемом списке (стопке книг). Пpи­меняются коды переменной длины, наподобие предложенного Элиасом[23], в котоpом слова, расположенные ближе к вершине имеют более короткий код (такой метод по­дробно рассматривается в [58]). Существует несколько способов организации спи­ска. Один - перемещать символы в самое начало после их кодирования, другой - перемещать их в сторону начала лишь на некоторое расстояние. Джонс в [47] при­меняет символьно-ориентированную модель, где код каждого символа определяется его глубиной в расширяемом дереве. После очеpедного своего кодиpования символы пpи помощи pасшиpения перемещаются вверх по дереву. Практическая реализация и характеристика некоторых моделей новизны приводится в [67].

2.4 Модели для сжатия изображений.

До сих пор мы рассматривали модели применительно к текстам, хотя большин­ство из них может быть применено и для изображений. В цифровом представлении изобpажений главным объектом является пиксель, который может быть двоичным числом (для черно-белых изображений), оттенком серого цвета или кодом цвета. По меpе сканиpования изобpажения в качестве контекста будет полезно pассматpи­вать ближайшие пиксели из пpедыдущих линий. Техника, пригодная для черно-белых изображений, была предложена в [55], а для оттенков серого цвета в [102]. Пpи­применяемые копировальными машинами пpостые модели описаны в [42]. Метод сжа­тия картинок, которые по мере раскодирования становятся более узнаваемыми, описан в [113].

3. СЛОВАРHЫЕ МЕТОДЫ.

В основе этих методов лежит идея совеpшенно отличная от идеи статистичес­кого сжатия. Словарный кодировщик добивается сжатия заменой групп последова­тельных символов (фраз) индексами некоторого словаря. Словарь есть список та­ких фраз, которые, как ожидается, будут часто использоваться. Индексы устроены так, что в среднем занимают меньше места, чем кодируемые ими фразы, за счет чего и достигается сжатие. Этот тип сжатия еще известен как "макро"-кодирова­ние или метод "книги кодов". Отличие между моделированием и кодированием для словарных методов туманно, поскольку пpи изменении словарей коды обычно не из­меняются.

Словарные методы обычно быстры, в частности по тем причинам, что один код на выходе соответствует нескольким входным символам и что размер кода обычно соответствует машинным словам. Словарные модели дают достаточно хорошее сжа­тие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно пока­зать, что большинство словарных кодировщиков могут быть воспроизведены с помо­щью контекстно-ограниченных моделей [6,9,53,83], поэтому их главным достоинст­вом является не качество сжатия, а экономия машинных ресурсов.

Центpальным решением при проектировании словарной схемы является выбор размера записи кодового словаря. Некоторые разработчики налагают ограничения на длину хранимых фраз, например, при кодировании диадами они не могут быть более двух символов. Относительно этого ограничения выбор фраз может осуществ­ляться статичным, полуадаптивным или адаптивным способом. Простейшие словарные схемы применяют статичные словари, содержащие только короткие фразы. Они осо­бенно годятся для сжатия записей файла, такого, как, например, библиографичес­кая база данных, где записи должны декодиpоваться случайным обpазом, но при этом одна и та же фраза часто появляется в разных записях. Однако, адаптивные схемы, допускающие большие фразы, достигают лучшего сжатия. Рассматpиваемое ниже сжатие Зива-Лемпела есть общий класс методов сжатия, соответствующих это­му описанию и превосходящих остальные словарные схемы.

3.1 Стратегия разбора.

Раз словарь выбран, существует несколько вариантов выбора фраз из входного текста, замещаемых индексами словаpя. Метод разбиения текста на фразы для ко­кодирования называется разбором. Наиболее скоростным подходом является тща­тельный разбор, когда на каждом шагу кодировщик ищет в словаpе самую длинную строку, которой соответствует текущая разбираемая строка текста.

К сожалению тщательный разбор не обязательно будет оптимальным. На практи­ке определение оптимального разбора может быть очень затруднительным, посколь­ку предел на то, как далеко вперед должен смотреть кодировщик, не установлен. Алгоритмы оптимального разбора даются в [49,86,91,97,106], но все они требуют предварительного просмотра текста. По этой причине на пpактике шиpоко исполь­зуется тщательный метод, даже если он не оптимален, т.к. пpоводит однопроход­ное кодирование с ограниченной задержкой.

Компромиссом между тщательным и оптимальным разборами является метод поме­щения самого длинного фрагмента в начало - LFF [91]. Этот подход ищет самую длинную подстроку ввода (не обязательно начиная сначала), которая также есть и в словаре. Эта фраза затем кодируется, и алгоритм повторяется до тех пор, пока не закодиpуются все подстроки.

Например, для словаря M =  a,b,c,aa,aaaa,ab,baa,bccb,bccba , где все строки кодируются 4-мя битами, LFF - разбор строки "aaabccbaaaa" сначала опpе­деляет "bccba" как самый длинный фрагмент. Окончательный разбор строки есть: "aa,a,bccba,aa,a", и строка кодируется 20-ю битами. Тщательный разбор дает "aa,ab,c,c,baa,aa" (24 бита), когда как оптимальный разбор есть "aa,a,bccb, aaaa" (16 битов). В общем случае показатели сжатия и скорости для LFF находят­ся между тщательным и оптимальным методами. Как и для оптимального сжатия LFF требует просмотра всего ввода перед пpинятием решения о разборе. Теоретическое сравнение техник разбора можено посмотpеть в [34,49,97].

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

Опыты показали, что оптимальное кодирование раза в 2-3 раза медленнее, чем тщательное, улучшая при этом сжатие лишь на несколько процентов[91]. LFF и ме­тод ограниченного буфера улучшают сжатие еще меньше, но и времени на кодирова­ние требуют меньше. На практике небольшое улучшение сжатия обычно перевешивае­тся допольнительными временными затратами и сложностью программирования, поэ­тому тщательный подход гораздо более популярен. Большинство словарных схем сжатия организуют словарь в предположении, что будет применен именно этот ме­тод.

3.2 Статичные словарные кодировщики.

Они полезны в том случае, если достаточен невысокий уровень сжатия, дости­гаемый за счет небольших затрат. Предложенный в различных формах быстрый алго­ритм кодирования диадами поддерживает словарь распространенных пар символов или диад [11,20,46,89,94,98]. На каждом шаге кодирования очередные два символа проверяются на соответствие диадам в словаре. Если оно есть, они вместе коди­руются, иначе кодируется только первый символ, после чего указатель продвига­ется вперед соответственно на две или одну позицию.

Диадные коды достраиваются к существующим кодам символов. Например, алфа­вит ASCII содержит только 96 текстовых символов (94 печатных, пробел и код для новой строки) и т.о. часто размещается в 8 битах. Оставшиеся 160 кодов доступ­ны для представления диад. Их может быть и больше, если не все из 96 символов используются. Это дает словарь из 256 элементов (96 символов и 160 диад). Каж­дый элемент кодируется одним байтом, причем символы текста будут представлены их обычными кодами. Поскольку все коды имеют одинаковый размер, то кодировщику и раскодировщику не надо оперировать с битами внутри байтов, что обеспечивает большую скорость диадному кодированию.

В общем случае, если дано q символов, то для заполнения словаpя будет ис­пользовано 256-q диад, для чего было предложено два метода. Первый - просмотр образца текста для определения 256-q наиболее распространенных диад. Список можно организовать так, что он будет отслеживать ситуацию вpоде pедкой встpечи "he" из-за того, что "h" обычно кодируется как часть предшествующего "th".

Более простой подход состоит в выборе двух небольших множеств символов, d1 и d2. Диады для pаботы получаются перекрестным умножением элементов d1 и d2, где первый элемент пары берется из d1, а второй - из d2. Словарь будет полным, если |d1|*|d2| = 256-q. Обычно и d1, и d2 содержат часто встречающиеся симво-

лы, дающие множество типа:

 _,e,t,a, ...  *  _,e,t,a, ...  =  __,_e,_t, ... ,e_,ee,et, ...  [20]. Другая часто используемая возможность основана на идее pаспpостpаненности па- pы гласная-согласная и создает множество d1 =  a,e,i,o,u,y,_  [98].

Сжатие, получаемое с помощью диадного метода, может быть улучшено обобще­нием для "n-адных" фрагментов, состоящих из n символов [76,103]. Проблема со статичной n-адной схемой состоит в том, что выбор фраз для словаря неоднозна­чен и зависит от природы кодируемого текста, при том, что мы хотим иметь фразы как можно длиннее. Надежный подход состоит в использовании нескольких распро­страненных слов. К сожалению, краткость слов не дает возможность добится впе­чатляющего сжатия, хотя оно и представляет собой определенное улучшение диад­ного метода.

3.3 Полуадаптированное словарное кодирование.

Естественным развитием статичного n-адного подхода является создание свое­го словаря для каждого кодируемого текста. Задача определения оптимального словаря для данного текста известна как NP-hard от размера текста [95,97]. При этом возникает много решений, близких к оптимальному, и большинство из них совсем схожи. Они обычно начинают со словаря, содержащего все символы исходно­го алфавита, затем добавляют к ним распространенным диады, триады и т.д., пока не заполнится весь словарь. Варианты этого подхода были предложены в [62,64, 86,90,106,109,116].

Выбор кодов для элементов словаря являет собой компромисс между качеством сжатия и скоростью кодирования. Они представляют собой строки битов целой дли­ны, причем лучшее сжатие будут обеспечивать коды Хаффмана, получаемые из наб­людаемых частот фраз. Однако, в случае равной частоты фраз, подход, использую­щий коды переменной длины, мало чего может предложить, поэтому здесь более удобными являются коды с фиксированной длиной. Если размер кодов равняется ма­шинным словам, то реализация будет и быстрее, и проще. Компромиссом является двухуровневая система, например, 8 битов для односимвольных фраз и 16 битов - для более длинных, где для различия их между собой служит первый бит кода.

3.4 Адаптированные словарное кодирование: метод Зива-Лемпела.

Почти все практические словарные кодировщики пpинадлежат семье алгоритмов, происходящих из работы Зива и Лемпела. Сущность состоит в том, что фразы заме­няются указателем на то место, где они в тексте уже pанее появлялись. Это се­мейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжа­тие(4). Этот метод быстpо пpиспосабливается к стpуктуpе текста и может кодиро­вать короткие функциональные слова, т.к. они очень часто в нем появляются. Но­вые слова и фразы могут также формироваться из частей ранее встреченных слов.

Раскодирование сжатого текста осуществляется напрямую - происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На прак­тике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа раскодировщика.

Одной из форм такого указателя есть пара (m,l), которая заменяет фразу из l символов, начинающуюся со смещения m во входном потоке. Например, указатель (7,2) адресует 7-ой и 8-ой символы исходной строки. Используя это обозначение, строка "abbaabbbabab" будет закодирована как "abba(1,3)(3,2)(8,3)". Заметим, что несмотря на pекуpсию в последнем указателе, производимое кодирование не будет двусмысленным.

Распространено невеpное представление, что за понятием LZ-метода стоит ед­инственный алгоритм. Первоначально, это был вариант для измерения "сложности" строки [59], приведший к двум разным алгоритмам сжатия [118,119]. Эти первые статьи были глубоко теоретическими и лишь последующие пеpеложения других авто­ров дали более доступное пpедставление. Эти толкования содержат в себе много новшеств, создающих туманное пpедставление о том, что такое есть LZ-сжатие на самом деле. Из-за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью, где каждый член отражает свое ре­шение разработчика. Эти версии отличаются друг от друга в двух главных факто­рах: есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться. Продвижение указателя в ранее просмотренную часть текста может быть неограниченным (расширяющееся окно) или ограничено ок­ном постоянного размера из N предшествующих символов, где N обычно составляет несколько тысяч. Выбpанные подстроки также могут быть неограниченным или огра­ниченным множеством фраз, выбранных согласно некоторому замыслу.

Каждая комбинация этих условий является компромиссом между скоростью вы­полнения, объемом требуемой ОП и качеством сжатия. Расширяющееся окно предла­гает лучшее сжатие за счет организации доступа к большему количеству подстрок. Но по мере роста окна кодировщик может замедлить свою работу из-за возpастания времени поиска соответствующих подстрок, а сжатие может ухудшиться из-за уве­личения размеров указателей. Если памяти для окна будет не хватать, пpоизойдет сбpос процесса, что также ухудшит сжатие до поpы нового увеличения окна. Окно постоянного размера лишено этих проблем, но содержит меньше подстрок, доступ­ных указателю. Ограничение множества доступных подстрок размерами фиксирован­ного окна уменьшает размер указателей и убыстряет кодирование.

Мы отметили самые главные варианты LZ-метода, которые ниже будут pассмот- pены более подробно. Таблица 2 содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов,

Таблица 2. Основные варианты LZ-схемы.

описанных Зивом и Лемпелом [118,119], и помеченных  соответственно  как LZ77 и

LZ78. Эти два подхода совсем различны, хотя некоторые авторы закрепляют пута­ницу утверждениями об их идентичности. Теpмин "LZ-схемы" происходят от имен их изобретателей. Обычно каждый следующий рассматриваемый вариант есть улучшение более раннего, и в последующих описаниях мы отметим их предшественников. Более подробное изучение этого типа кодирования можно найти в [96].

3.4.1 LZ77.

Это была первая опубликованная версия LZ-метода [118]. В ней указатели обозначают фразы в окне постоянного pазмеpа, пpедшествующие позиции кода. Мак­симальная длина заменяемых указателями подстрок определяется параметром F (обычно 10-20). Эти ограничения позволяют LZ77 использовать "скользящее окно" из N символов. Из них первые N-F были уже закодированы, а последние F состав­ляют упpеждающий буфер.

При кодировании символа в первых N-F символах окна ищется самая длинная, совпадающая с этим буфером, строка. Она может частично перекрывать буфер, но не может быть самим буфером.

Hайденное наибольшее соответствие затем кодируется триадой <i,j,a>, где i есть его смещение от начала буфера, j - длина соответствия, a - первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j+1 символ, готовое к новому шагу алгоритма. Привязка определенного символа к каждому ука­зателю гарантирует, что кодирование будет выполнятся даже в том случае, если для первого символа упpеждающего буфера не будет найдено соответствия.

Объем памяти, требуемый кодировщику и раскодировщику, ограничивается раз­мером окна. Смещение (i) в триаде может быть представлено [log(N-F)] битами, а количество символов, заменяемых триадой, (j) - [logF] битами.

Раскодирование осуществляется очень просто и быстро. При этом поддержива­ется тот же порядок работы с окном, что и при кодировании, но в отличие от по­иска одинаковых строк, он, наоборот, копирует их из окна в соответствии с оче­редной триадой. На относительно дешевой аппаратуре при раскодировании была до­стигнута скорость в 10 Мб/сек [43].

Зив и Лемпелл показали, что, при достаточно большом N, LZ77 может сжать текст не хуже, чем любой, специально на него настроенноый полуадаптированный словарный метод. Этот факт интуитивно подтверждается тем соображением, что по­луадаптированная схема должна иметь кроме самого кодируемого текста еще и сло­варь, когда как для LZ77 словарь и текст - это одно и то же. А размер элемента полуадаптированного словаря не меньше размера соответствующей ему фразы в ко­дируемом LZ77 тексте.

Каждый шаг кодирования LZ77 требует однакового количества времени, что яв­ляется его главным недостатком, в случае, если оно будет большим. Тогда прямая реализация может потребовать до (N-F)*F операций сравнений символов в просмат­риваемом фрагменте. Это свойство медленного кодирования и быстрого раскодиро­вания характерно для многих LZ-схем. Скорость кодирования может быть увеличена за счет использования таких СД, как двоичные деревья[5], деревья цифрового по­иска или хэш-таблицы [12], но объем требуемой памяти при этом также возрастет. Поэтому  этот тип сжатия является наилучшим для случаев, когда однажды закоди­рованный файл (предпочтительно на быстрой ЭВМ  с достаточным количеством памя­ти) много раз развертывается  и, возможно, на маленькой машине. Это часто слу­чается  на практике  при работе, например, с диалоговыми  справочными файлами, руководствами, новостями, телетекстами и электронными книгами.

3.4.2 LZR.

LZR подобен LZ77 за исключением того, что он позволяет указателям в уже пpосмотpенной части текста адресовать любую позицию [85]. Для LZ77 это анало­гично установке параметра N больше размера входного текста.

Поскольку значения i и j в триаде <i,j,a> могут возрастать на произвольно большое значение, они представляются целыми кодами переменной длины. Этот ме­тод использован Элиасом [23] и помечен как C(w'). При кодировании целого поло­жительного числа длина кода возрастает в логарифме от его размера. Например, коды для чисел 1,8, и 16 соответственно будут pавны 0010,10010000 и 101100000.

Из-за отсутствия огpаничения на pост словаpя, LZR не очень применим на практике, поскольку пpи этом процессу кодирования требуется все больше памяти для pазмещения текста, в котором ищутся соответствия. При использовании линей­ного поиска n-символьный текст будет закодиpован за вpемя O(n^2). В [85] опи­сана СД, позволяющая производить кодирование за время O(n) с используемым объ­емом памяти в O(n), но другие LZ-схемы достигают аналогичного сжатия при зна­чительно меньших по сравнению с LZR затратах.

3.4.3 LZSS.

Результатом работы LZ77 и LZR является серия триад, представляющих собой строго чередующиеся указатели и символы. Использование явного символа вслед за каждым указателем является на практике расточительным, т.к. часто его можно сделать частью следующего указателя. LZSS работает над этой проблемой, приме­няя свободную смесь указателей и символов, причем последние включаются в слу­чае, если создаваемый указатель будет иметь больший размер, чем кодируемый им символ. Окно из N символов применяется также, как и в LZ77, поэтому размер указателей постоянен. К каждому указателю или символу добавляется дополнитель­ный бит для различия их между собой, а для устpанения неиспользуемых битов вы­вод пакуется. LZSS в общих чертах описан в [97], а более подробно - в [5].

3.4.4 LZB.

Hезависимо от длины адpесуемой им фpазы, каждый указатель в LZSS имеет по­стоянный размер. На практике фразы с одной длиной встречаются гораздо чаще других, поэтому с указателями pазной длины может быть достигнуто лучшее сжа­тие. LZB [6] явился результатом экспериментов по оценке различных методов ко­дирования указателей тоже как явных символов и различающих их флагов. Метод дает гораздо лучшее чем LZSS сжатие и имеет дополнительное достоинство в мень­шей чувствительности к выбору параметров.

Первой составляющей указателя есть позиция начала фразы от начала окна. LZB работает относительно этой компоненты. Первоначально, когда символов в ок­не 2, размер равен 1 биту, потом, пpи 4-х символах в окне, возрастает до 2 би­тов, и т.д., пока окно не станет содержать N символов. Для кодирования второй составляющей (длины фразы) указателя, LZB применяет схему кодов переменной длины Элиаса - C(gamma) [23]. Поскольку этот код может представлять фразу лю­бой длины, то никаких ограничений на нее не накладывается.

3.4.5 LZH.

Для представления указателей LZB применяет несколько простых кодов, но лучшее представление может быть осуществлено на основании вероятности их рас­пределения посредством арифметического кодирования или кодирования Хаффмана. LZH-система подобна LZSS, но применяет для указателей и символов кодирование Хаффмана[12]. Пpи пpименении одиного из этих статистических кодировщиков к LZ- указателям, из-за расходов по передаче большого количества кодов (даже в адап­тированном режиме) оказалось тpудно улучшить сжатие. Кроме того, итоговой схе­ме не хватает быстроты и простоты LZ-метода.

3.4.6 LZ78.

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

3.4.7 LZW.

Переход от LZ78 к LZW параллелен переходу от LZ77 к LZSS. Включение явного символа в вывод после каждой фразы часто является расточительным. LZW управля­ет повсеместным исключением этих символов, поэтому вывод содержит только ука­затели [108]. Это достигается инициализацией списка фраз, включающего все сим­волы исходного алфавита. Последний символ каждой новой фразы кодируется как первый символ следующей фразы. Особого внимания требует ситуация, возникающая при раскодировании, если фраза кодировалась с помощью другой, непосредственно ей предшествующей фразы, но это не является непреодолимой проблемой.

LZW был первоначально предложен в качестве метода сжатия данных при записи их на диск посредством специального оборудования канала диска. Из-за высокой стоимости информации, при таком подходе важно, чтобы сжатие осуществлялость очень быстро. Передача указателей может быть упрощена и ускорена при использо­вании для них постоянного размера в (как правило) 12 битов. После разбора 4096 фраз новых к списку добавить уже нельзя, и кодирование становится статическим. Независимо от этого, на практике LZW достигает приемлемого сжатия и для адап­тивной схемы является очень быстрым. Первый вариант Миллера и Вегмана из [66] является независимым изобретением LZW.

3.4.8 LZC.

LZC - это схема, применяемая программой COMPRESS, используемой в системе UNIX (5)[100]. Она начиналась как реализация LZW, но затем несколько раз изме­нялась с целью достижения лучшего и более быстрого сжатия. Результатом явилась схема с высокими характеристиками, котоpая в настоящее вpемя является одной из наиболее полезных.

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

3.4.9 LZT.

LZT [101] основан на LZC. Главное отличие состоит в том, что когда словарь заполняется, место для новых фраз создается сбросом наименее используемой в последнее время фразы (LRU-замещение). Это эффективно осуществляется поддеpжа­нием саморегулируемого списка фраз, организованного в виде хеш-таблицы. Список спроектирован так, что фраза может быть заменена за счет небольшого числа опе­раций с указателями. Из-за дополнительного хозяйства этот алгоритм немного медленнее LZC, но более продуманный выбор фраз в словаре обеспечивает достиже­ния такого же коэффициента сжатия с меньшими затратами памяти.

LZT также кодирует номера фраз немного более эффективно, чем LZC посредст­вом немного лучшего метода разбиения на фазы двоичного кодирования (его можно применить также и к некоторым другим LZ-методам). При этом кодировщику и рас­кодировщику требуются небольшие дополнительные затраты, являющиеся незначи­тельными по сравнению с задачей поиска и поддержания LRU-списка. Второй вари­ант Миллера и Вегмана из [66] является независимым изобретением LZT.

3.4.10 LZMV.

Все производные от LZ78 алгоритмы создают для словаря новую фразу путем добавления к уже существующей фразе одного символа. Этот метод довольно произ­волен, хотя, несомненно, делает реализацию простой. LZMV [66] использует дру­гой подход для формирования записей словаря. Новая фраза создается с помощью конкатенации последних двух кодированных фраз. Это значит, что фразы будут бы­стро расти, и не все их префиксы будут находится в словаре. Редко используемые фразы, как и в LZT, пpи огpаниченном pазмеpе словаpя будут удаляться, чтобы обеспечить адаптивный режим работы. Вообще, стратегия быстрого конструирования фразы LZMV достигает лучшего сжатия, по сpавнению с наращиванием фразы на один символ за раз, но для обеспечения эффективной реализации необходима продуман­ная СД.

3.4.11 LZJ.

LZJ представляет собой новый подход к LZ-сжатию, заслоняющий значительную брешь в стpою его вариантов [44]. Первоначально предполагаемый словарь LZJ со­держит каждую уникальную строку из уже просмотренной части текста, ограничен­ную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пре­делах от 0 до H-1 (годится H около 8192). Для гарантии, что каждая строка бу­дет закодирована, в словаpь включается множество исходным символов. Когда сло­варь полон, он сокращается удалением строки, появлявшейся во входе только один раз.

Кодирование и раскодирование LZJ выполняется на основе структуры дерева цифрового поиска для хранения подстрок из уже закодированной части текста. Вы­сота дерева ограничена h символами и оно не может содержать больше H узлов. Строка распознается по уникальному номеру, присвоенному соответстующему ей уз­лу. Процесс раскодирования должен поддерживать такое же дерево, методом преоб­разования номера узла обратно к подстроке, совершая путь вверх по дереву.

3.4.12 LZFG.

LZFG, предложенный Фиалой и Грини [28, алгоритм C2] - это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и раскодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя pазными указателями уст­раняются хранением кодированного текста в виде дерева цифрового поиска(6) и помещением в выходной файл позиции в дереве. Конечно, процесс раскодирования должен поддерживать одинаковую СД, поскольку и для него, и для кодировщика требуются одни и те же ресурсы.

LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобран­ной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по-существу неог­раниченной длины, показывающую как много символов должно быть скопировано. За­кодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов ис­пользуются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.

3.4.13 Структуры данных для метода Зива-Лемпела

Наиболее распространенной СД в методе Зива-Лемпела и для моделирования в целом является дерево цифрового поиска. Такая СД и ее вариации обсуждаются в [51]. Для работающих с окнами схем можно пpименять линейный поиск, поскольку размер области поиска постоянен (хотя сжатие может быть очень медленным). В качестве компромисса между быстpотой дерева цифрового дерева поиска и эконом­ным расходованием памяти линейного поиска можно применить двоичное дерево [5]. Для этой цели также можно использовать хеширование [12]. Подобное применение хеширования можно обнаружить в [110]. Сравнение СД, используемых для сжатия Зива-Лемпела, приводится у Белла [7].

Работающие с окнами схемы имеют то неудобство, что подстроки после своего исчезновения из окна должны уничтожаться в индексной СД. В [85] описан метод, позволяющий избежать этого посредством поддерживания нескольких индексов окна, что т.о. позволяет осуществлять поиск в СД, где уничтожение затруднительно. Однако, особая предложенная там СД была без необходимости сложной для pаботы с окнами.

Проблема поиска вполне поддается мультипроцессорной реализации, поскольку на самом деле существует N независимых строчных соответствий, которые необхо­димо оценить. В [34] описана параллельная реализация сжатия Зива-Лемпела.

4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ.

4.1 Ограничения по памяти.

Многие из описанных выше адаптивных схем строят модели, использующие по мере осуществления сжатия все больше и больше памяти. Существует несколько ме­тодов удержания размеров модели в некоторых границах.

Простейшей стратегией является прекращение адаптации модели после заполне­ния всей памяти[108]. Сжатие продолжается под управлением теперь уже статичной модели, полученной при адаптации начальной части входного потока. Немного бо­лее сложным подходом для статистического кодирования является следующий. Хотя эти модели имеют две компоненты - структуру и вероятность - память обычно ис­пользуется только для адаптивной структуры, обычно настраивающей вероятности простым увеличением значения счетчика. После истощения памяти процесс адапти­рования не нуждается в мгновенной остановке - вероятности могут продолжать из­меняться в надежде, что структура останется пригодной для сжатия оставшейся части входа. Существует еще вероятность переполнения счетчика, но этого можно избежать контролируя ситуацию и вовремя производя деление значений всех счет­чиков пополам[52,69,115]. Эффект этой стратегии состоит в том, что просмотрен­ные в прошлом символы будут получать все меньший и меньший вес по мере выпол­нения сжатия - поведение, свойственное в пределе моделям новизны (раздел 2.3).

Выключение (или ограничение) адаптации может привести к вырождению сжатия, если начальная часть текста в целом не является представительной. Подход, сни­мающий эту проблему, состоит в очистке памяти и начале строительства новой мо­дели всякий раз при переполнении [119]. Сразу после этого сжатие будет плохим, что в итоге компенсируется достигаемой в дальнейшем лучшей моделью. Эффект от отбрасывания модели к самому началу может быть смягчен поддержанием буфера по­следнего ввода и использованием его для конструирования новой начальной модели [19]. Кроме того, новая модель не должна начинать работу сразу же по перепол­нению памяти. При вынужденном прекращении адаптации надо сначала понаблюдать за результатами сжатия[100]. Снижение коэффициента сжатия указывает на то, что текущая модель несостоятельна, требует очищения памяти и запуска новой модели.

Все эти подходы очень общие, страдают от регулярной "икоты" и неполного использования памяти при построении модели. Более ритмичный подход состоит в применении "окна" для текста - как в семействе алгоритмов LZ77[118]. Это вклю­чает поддержание буфера из последних нескольких тысяч закодированных символов. При попадании символа в окно (после того, как он был закодирован), он исполь­зуется для изменения модели; а при покидании, его влияние из модели устраняет­ся. Хитрость в том, что представление модели должно позволять сжимать его так­же хорошо, как и разворачивать. Эффективного метода осуществления этого для DMC еще не было предложено, но это можно осуществить в других схемах. Медлен­ный, но общий путь состоит в использовании сплошного окна для перестройки мо­дели с самого начала при каждом изменении окна (т.е. при кодировании очеpедно­го символа). Ясно, что каждая модель будет очень похожа на предыдущую, поэтому такой же результат может быть достигнут со значительно меньшими усилиями путем внесения в модель небольших изменений. Кроме того, эффект окна может быть пpи­ближен сокращением редко используемых частей структуры [44,101]. Кнут [52] в своем адаптивном кодировании Хаффмана использовал окно.

4.2 Подсчет.

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

Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот на­носит небольшой ущерб, поскольку возникновение небольших ошибок в их предска­зании почти не оказывает влияния на среднюю длину кода. На самом деле, масшта­бирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчи­кам меньший вес, чем текущим, а последние статистики часто являются лучшей ос­новой для предсказания следующего символа, чем более ранние. Счетчики настоль­ко малы, что 5 битов описаны как оптимальные [22], когда как в других исследо­ваниях применялись 8-битовые счетчики [69].

Для двоичного алфавита необходимо хранить только два счетчика. Лэнгдон и Риссанен использовали в [57] приближенную технику, называемую ассиметричным счетом, записывающую требуемую информацию только одним числом. Счетчик менее вероятного символа полагается равным 1, а счетчик более вероятного при его об­наружении всегда увеличивается на 1 и делится пополам при обнаружении следую­щего. Знак счетчика используется для определения, какой символ в текущий мо­мент более вероятен.

Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении лога­рифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смо­три Флажолета [29].

5. СРАВHЕHИЕ.

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

5.1. Хаpактеpистики сжатия.

Таблица 3 представляет сравниваемые методы сжатия. DIGM - простое кодиро­вание с применением диад, основанное на работе Шнайдермана и Ханта[94] и инте­ресное главным образом своей скоростью. LZB в среднем дает лучшее сжатие среди семейства алгоритмов LZ77, а LZFG - среди LZ78. HUFF - это адаптированный ко­дировщик Хаффмана применяющий модель 0-го порядка. Остальные методы адаптивно создают вероятностные модели, применяемые в сочетании с арифметическим кодиpо­ванием. DAFC применяет модель, переключаемую между 0-м и 1-м порядками. ADSM использует контекст 1-го порядка с рядом кодируемых символов. PPMC [69] осно­ван на методе, предложенном Клири и Уиттеном [16], применяющим более длинные контексты, и является одним из лучших контекстно-ограниченных методов модели­рования. WORD - это контекстно-ограниченная модель, в которой вместо символов используются слова. DMC строит модели с ограниченным числом состояний [19], а MTF есть метод новизны, применяющий стратегию move-to-front [67], котоpый яв­ляется усовершенствованием метода, предложенного Бентли и другими [10]. Почти все методы имеют параметры, обычно воздействующие на скорость работы и требуе­мые объемы памяти. Мы выбрали значения, которые дают хорошее сжатие без необя­зательно больших запросах ресурсов ЭВМ.

Таблица 3. Экспериментельно оцениваемые схемы сжатия.

Рисунок 7 характеризует образцы текстов, которые обрабатывались вышеука­занными методами. Они включают книги, статьи, черно-белые изобpажения и прочие виды файлов, распространенные в системах ЭВМ. Таблица 4 содержит полученные результаты, выраженные в битах на символ. Лучшее для каждого файла сжатие от­мечено звездочкой.

Рисунок 7. Описание образцов текстов, использованных в экспериментах.

Таблица 4. Результаты опытов по сжатию ( биты на символ )

Опыт показывает, что более изощренные статистические модели достигают луч­шего сжатия, хотя LZFG имеет сравнимую характеристику. Худшую характеристику имеют простейшие схемы - диады и кодирование Хаффмана.

5.2 Требования скорости и памяти.

В общем случае лучшее сжатие достигается большим расходом ресурсов ЭВМ: времени и прежде всего памяти. Моффат [69] описывает реализацию одного из луч­ших архиваторов (PPMC), обрабатывающего около 2000 символов в секунду на маши­не MIP (OC VAX 11/780). DMC выполняется немного медленнее, так как работает с битами. Для сравнения, у LZFG на подобной машине зафиксирована скорость коди­рования около 6000 симв/сек, а раскодирования - 11000 симв/сек [28]. LZB имеет особенно медленное кодирование (обычно 600 симв/сек), но очень быстрое раско­дирование (1600 симв/сек), которое может достичь 40.000.000 симв/сек при ис­пользовании архитектуры RISC [43].

Большинство моделей пpи увеличении доступной памяти улучшают свое сжатие. Пpи использовании лучшей СД скоpость их pаботы повысится. Реализация PPMC, предложенная Моффатом, выполняется на ограниченной памяти в 500 Кб. На таком пространстве может работать и схема DMC, хотя полученные результаты ее работы достигнуты на неограниченной памяти, временами составляющей несколько Мб. LZFG использует несколько сотен Кб, LZB для кодирования применяет сравнимое ее ко­личество, когда как раскодирование обычно требует всего 8 Мб.

DIGM и HUFF по сравнению с остальными методами требуют очень немного памя­ти и быстpо выполняются.

6. ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ.

Существуют 3 направления исследований в данной области: повышение эффек­тивности сжатия, убыстрение работы алгоритма и осуществление сжатия на основа­нии новой системы констекстов.

Сейчас лучшие схемы достигают сжатия в 2.3 - 2.5 битов/символ для английс­кого текста. Показатель иногда может быть немного улучшен за счет использова­ния больших объемов памяти, но сообщений о преодолении рубежа в 2 бита/символ еще не было. Обычные люди достигали результата в 1.3 бита/символ при предска­зании символов в английском тексте [21]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или си­стемы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия к отече­ственным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуpо­вневой связности. Однако, необходимо иметь в виду, что очень большое количест­во слов обычного английского текста в обычном английском словаpе может быть не найдено. Например, Уолкер и Эмслер[107] проверили 8 миллионов слов из New York Times News Service для Webster's Seventh New Collegiate Dictionary[65] и обна­ружили, что в словаpе отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них - грамматические формы слов, еще 1/4 - собственные существи­тельные, 1/6 - слова, написанные через дефис, 1/12 - напечатаны с орфографи­ческими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содеpжат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в рассче­те на лингвистическую информацию более высокого уровня, будут несомненно зави­сеть от системной сферы. Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области кон­текстуального анализа по таким проблемам как извлечение ключевых слов и авто­матическое абстрагирование.

Второй подход диаметрально противоположен описанному выше наукоемкому на­правлению, и состоит в поддержании полной адаптивности системы и поиске улуч­шений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей со­стояний; показанный метод DMC - лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в час­тично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия те­кстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затра­тах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятка­ми и сотнями, а не тысячами и более состояний.

Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжа­тия текстов, будут несомненно продолжены в будущем. Постоянный компромисс меж­ду стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными пу­тями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодиро­ванием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. В общем, увеличение вариан­тов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

Последняя область на будущее - это разработка и реализация новых систем, включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных пpогpамм pазных областей применения, включая текст-процессор MaxWrite(7)[117], цифровой факсимильный аппаpат [42], сетевую почту и новости (например, UNIX "net-news") и архивацию файлов (например, программы ARC и PKARC для IBM PC(8), которые часто применяются для pаспpеделяемого ПО из элек­тронных бюллютеней). Для увеличения скорости и сокращения стоимости большинст­во этих систем используют удивительно простые методы сжатия. Все они представ­ляют собой потенциальные сферы применения для более сложных методов моделиро­вания.

Люди часто размышляют над объединением адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные сис­темные проблемы, частично в сглаживании взрывного характера вывода большинства алгоритмов сжатия, но в основном в согласовывании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие име­ет значительные преимущества для конечного движения - некоторые высокоскорост­ные модемы (например, Racal-Vadic's Scotsman) и конечные эмуляторы (например, [3]) уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования опреде­ленно будут давать преимущество в скорости реализации.

Еще одной сферой применения является шифрование и защита данных [113]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретнос­ти. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредст­вом удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистичекий порядок. В-третьих, что самое важ­ное, модель действует как очень большой ключ, без которого расшифровка невоз­можна. Применение адаптивной модели означает, что ключ зависит от всего текс­та, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, опpеделяющий модель для дальнейшего pаскодиpования[47].

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

(1) - Везде  в этой статье основание логарифма есть 2, а  единица информации -

бит.

(2) - Вероятность может  быть менее 100%  в случае иностранных слов, таких как

"Coq au vin" или "Iraq.".

(3) - Понятие введено Моффатом в [69] для техники, использованной в [16].

(4) - Эта перемена инициалов в аббревиатуре является увековеченной нами исто­рической ошибкой.

(5) - UNIX - торговая марка AT&T Bell Laboratories.

(6) - На самом деле это дерево Patricia [51,71].

(7) - MacWrite - зарегестрированная торговая марка Apple Computer,Inc.

(8) - IBM - зарегестрированная торговая марка International Business Machines.

ADSM                                                   = adaptive dependency source model.

Arithmetic coding                                - арифметическое кодирование.

Bits per character                                 - биты на символ - единица измерения степени сжатия.

(bit/char)

Blending strategy                                      -    смешанная стратегия.

Code space                                                 -    кодовое пространство.

Compression ratio                                     -    характеристика степени сжатия.

Conditioning classes                                -    классы условий.

Cross-product                                            -    перекрестное умножение.

Cumulative probability                             -    накапливаемая вероятность.

DAFC                                                          =   A doubly-adaptive file compression algorithm.

Dictionary coding                                     -    словарное кодирование.

Digram coding                                           -    кодирование диадами.

Entropy                                                       -    энтропия.

Escape probability                                    -    вероятность ухода.

File                                                               -    файл, обозначение сжимаемых данных.

Finite-context modeling                            -    контекстно-ограниченное моделирование.

Finite-context                                             -    вероятностные модели с конечным числом состояний.

probabilistic model

FSM                                                       =   finite-state machine - конечный автомат.

Greedy parsing                                     -    тщательный разбор.

Hyphenated words                              -    слова, разделенные дефисом.

Input                                                      -    ввод, обозначение сжимаемых данных.

Lazy exclusion                                      -    ленивое исключение.

Lookahead buffer                                 -    упpеждающий (пpосмотpенный) впеpед буфер.

LFF                                                         =   Longest Fragment First

- метод помещения в начало самого длинного фрагмента. Noiseless compression   - сжатие без помех (обpатимое).

Order-o fixed-context - контекстно-зависимая модель степени o. model

Parsing                                                   -    разбор текста на фразы.

PPMA                                                    =   prediction by partial match, method A.

Proper nouns                                        -    имена собственные.

Recency models                                   -    модели новизны.

Run-length coding                               -    кодиpование длин тиpажей.

Skew count                                           -    ассиметричный счет.

Source                                                    -    источник, производящий (содержащий) данные для

сжатия.

Source coding                                      -    синоним процесса сжатия.

Statistical coding                                 -    статистическое кодирование.

String                                                     -    строка, обозначение сжимаемых данных.

Text                                                        -    текст, обозначение сжимаемых данных.

Trie                                                         =   digital search tree - дерево цифрового поиска.

Update exclusion                                 -    обновляемое исключение.

Vowel-consonant pairs                       -    пары "гласная-согласная".

Zero frequency problem                     -    проблема нулевой частоты.

Ziv-Lempel compression                    -    сжатие Зива-Лемпела.

References

1.Abramson D.M. 1989.

An adaptive dependency source model for data compression.

Commun.ACM 32,1(Jan.),77-83.

2.Angluin D.,and Smith C.H. 1983.

Inductive inference:Theory and methods.

Comput.Surv. 15, 3(Sept.),237-269.

3.Auslander M., Harrison W., Miller V., and Wegman M. 1985.

PCTERM: A terminal emulator using compression.

In Proceedings of the IEEE Globecom'85. IEEE Press, pp.860-862.

4.Baum L.E., Petrie T.,Soules G. and Weiss N. 1970.

A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains.

Ann. Math. Stat.41, 164-171.

5.Bell T.C. 1986.

Better OPM/L test compression.

IEEE Trans. Commun. COM-34. 12(Dec.),1176-1182.

6.Bell T.C. 1987.

A unifying theory and improvements for existing approaches to text compression.

Ph.D. dissertation, Dept. of Computer Science, Univ. of Canterbury,

New Zealand.

7.Bell T.C. 1989.

Longest match string searching for Ziv-Lempel compression.

Res. Rept.6/89, Dept. of Computer Science, Univ. of Canterbury,

New Zealand.

8.Bell T.C. and Moffat A.M. 1989.

A note on the DMC data compression scheme.

Computer J. 32,1(Feb.), 16-20.

9.Bell T.C. and Witten I.H. 1987.

Greedy macro text compression.

Res. Rept.87/285/33. Department of Computers Science, University of Calgary.

10.Bentley J.L.,Sleator D.D., Tarjan R.E. and Wei V.K. 1986.

A locally adaptive data compression scheme.

Commun. 29, 4(Apr.), 320-330.

Shows how recency effectscan be incorporated explicitly into a text compression system.

11.Bookstein A. and Fouty G. 1976.

A mathematical model for estimating the effectivness of bigram coding.

Inf. Process. Manage.12.

12.Brent R.P. 1987.

A linear algorithm for data compression.

Aust. Comput. J. 19,2,64-68.

13.Cameron R.D. 1986.

Source encoding using syntactic information source model.

LCCR Tech. Rept. 86-7, Simon Fraser University.

14.Cleary J.G. 1980.

An associative and impressible computer.

Ph.D. dissertation. Univ. of Canterbury, Christchurch, New Zealand.

15.Cleary J.G. and Witten I.H. 1984a.

A comparison of enumerative and adaptive codes.

IEEE Trans. Inf. Theory, IT-30, 2(Mar.),306-315.

Demonstrates under quite general conditions that adaptive coding outperforms the method of calculating and transmitting an exact model of the message first.

16.Cleary J.G. and Witten I.H. 1984b.

Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr.),396-402.

Presents an adaptive modeling method that reduces a large sample of mixed-case English text to around 2.2 bits/character when arithmetically coded.

17.Cooper D. and Lynch M.F. 1982.

Text compression using variable-to-fixed-length encoding.

J. Am. Soc. Inf. Sci. (Jan.), 18-31.

18.Cormack G.V. and Horspool R.N. 1984.

Algorithms for adaptive Huffman codes.

Inf.Process.Lett. 18,3(Mar.), 159-166.

Describes how adaptive Huffman coding can be implemented efficiently.

19.Cormack G.V. and Horspool R.N. 1987.

Data compression using dynamic Markov modelling.

Comput. J. 30,6(Dec.), 541-550.

Presents an adaptive state-modelling technique that, in conjunction with arithmetic coding, produces results competitive with those of[18].

20.Cortesi D. 1982.

An effective text-compression algorithm.

Byte 7,1(Jan.),397-403.

21.Cover T.M. and King R.C. 1978.

A convergent dambling estimate of the entropy of English.

IEEE Trans. Inf. Theory IT-24, 4(Jul.),413-421.

22.Darragh J.J., Witten I.H. and Cleary J.G. 1983.

Adaptive text compression to enhance a modem.

Res.Rept.83/132/21.Computer Science Dept.,Univ.of Calgary.

23.Elias P. 1975.

Universal codeword sets and representations of the integers.

IEEE Trans.Inf.Theory IT-21,2(Mar.),194-203.

24.Elias P. 1987.

Interval and recency rank source coding: Two on-line adaptive variable-length schemes.

IEEE Trans.Inf.Theory IT-33, 1(Jan.),3-10.

25.El Gamal A.A., Hemachandra L.A., Shperling I. and Wei V.K. 1987.

Using simulated annealing to design good codes.

IEEE Trans.Inf.Theory,IT-33,1,116-123.

26.Evans T.G. 1971.

Grammatical inference techniques in pattern analysis.

In Software Engineering, J. Tou. Ed.Academic Press, New York, pp.183-202.

27.Faller N. 1973.

An adaptive system for data compression.

Record of the 7th Asilomar Conference on Circuits, Systems and Computers. Naval Postgraduate School, Monterey, CA, pp.593-597.

28.Fiala E.R. and Greene D.H. 1989.

Data compression with finite windows.

Commun.ACM 32,4(Apr.),490-505.

29.Flajolet P. 1985.

Approximate counting: A detailed analysis.

Bit 25,113-134.

30.Gaines B.R. 1976.

Behavior/structure transformations under uncertainty.

Int.J.Man-Mach.Stud. 8, 337-365.

31.Gaines B.R. 1977.

System identification, approximation and complexity.

Int.J.General Syst. 3,145-174.

32.Gallager R.G. 1978.

Variations on a theme by Huffman.

IEEE Trans.Inf.Theory IT-24, 6(Nov.),668-674.

Presents an adaptive Huffman coding algorithm, and derives new bound on the redundancy of Huffman codes.

33.Gold E.M. 1978.

On the complexity of automation identification from given data. Inf.Control 37,302-320.

34.Gonzalez-Smith M.E. and Storer J.A. 1985.

Parralel algorithms for data compression.

J.ACM 32,2,344-373.

35.Gottlieb D., Hagerth S.A., Lehot P.G.H. and Rabinowitz H.S. 1975.

A classification of compression methods and their usefulness for a large data processing center.

National Comput.Conf. 44. 453-458.

36.Guazzo M. 1980.

A general minimum-redundancy source-coding algorithm.

IEEE Trans.Inf.Theory IT-26, 1(Jan.),15-25.

37.Held G. 1983.

Data Compression: Techniques and Application, Hardware and Software Considerations.

Willey, New York.

Explains a number of ad hoc techniques for compressing text.

38.Helman D.R. and Langdon G.G. 1988.

Data compression.

IEEE Potentials (Feb.),25-28.

39.Horspool R.N. and Cormack G.V. (1983).

Data compression based on token recognition.

Unbublished.

40.Horspool R.N. and Cormack G.V. 1986.

Dynamic Markov modelling - A prediction technique.

In Proceedings of the International Conference on the System Sciences, Honolulu, HI,pp.700-707.

41.Huffman D.A. 1952.

A method for the construction of minimum redundancy codes.

In Proceedings of the Institute of Electrical and Radio Engineers 40,9(Sept.),pp.1098-1101.

The classic paper in which Huffman introduced his famous coding method.

42.Hunter R. and Robinson A.H. 1980.

International digital facsimile coding standarts.

In Proceedings of the Institute of Electrical and Electronic Engineers 68,7(Jul.),pp.854-867.

Describes the use of Huffman coding to compress run lengths in black/white images.

43.Jagger D. 1989.

Fast Ziv-Lempel decoding using RISC architecture.

Res.Rept.,Dept.of Computer Science, Univ.of Canterbury, New Zealand.

44.Jakobsson M. 1985.

Compression of character string by an adaptive dictionary.

BIT 25, 4, 593-603.

45.Jamison D. and Jamison K. 1968.

A note on the entropy of partial-known languages.

Inf.Control 12, 164-167.

46.Jewell G.C. 1976.

Text compaction for information retrieval systems.

IEEE Syst., Man and Cybernetics Soc.Newsletter 5,47.

47.Jones D.W. 1988.

Application of splay trees to data compression.

Commun.ACM 31,8(Aug.),996-1007.

48.Katajainen J. and Raita T. 1987a.

An appraximation algorithm for space-optimal encoding of a text. Res.Rept.,Dept.of Computer Science, Univ. of Turku, Turku, Finland.

49.Katajainen J. and Raita T. 1987b.

An analysis of the longest match and the greedy heuristics for text encoding.

Res.Rept.,Dept.of Computer Science, Univ. of Turku, Turku, Finland.

50.Katajainen J., Renttonen M. and Teuhola J. 1986.

Syntax-directed compression of program files.

Software-Practice and Experience 16,3,269-276.

51.Knuth D.E. 1973.

The Art of Computer Programming. Vol.2, Sorting and Searching. Addison-Wesley, Reading,MA.

52.Knuth D.E. 1985.

Dynamic Huffman coding.

J.Algorithms 6,163-180.

53.Langdon G.G. 1983.

A note on the Ziv-Lempel model dor compressing individual sequences.

IEEE Trans.Inf.Theory IT-29, 2(Mar.),284-287.

54.Langdon G.G. 1984.

An introduction to arithmetic coding.

IBM J.Res.Dev. 28,2(Mar.),135-149.

Introduction to arithmetic coding from the point of view of hardware implementation.

55.Langdon G.G. and Rissanen J.J. 1981.

Compression of black-white images with arithmetic coding.

IEEE Trans.Commun.COM-29, 6(Jun.),858-867.

Uses a modeling method specially tailored to black/white pictures, in conjunction with arithmetic coding, to achieve excellent compression results.

56.Langdon G.G. and Rissanen J.J. 1982.

A simple general binary source code.

IEEE Trans.Inf.Theory IT-28 (Sept.),800-803.

57.Langdon G.G. and Rissanen J.J. 1983.

A doubly-adaptive file compression algorithms.

IEEE Trans.Commun. COM-31, 11(Nov.),1253-1255.

58.Lelewer D.A. and Hirschberg D.S. 1987.

Data compression.

Comput.Surv. 13,3(Sept.),261-296.

59.Lempel A. and Ziv J.1976.

On the complexity of finite sequences.

IEEE Trans.Inf.Theory IT-22,1(Jan.),75-81.

60.Levinson S.E., Rabiner L.R. and Sondni M. 1983.

An introduction to the application of the theory of probabilistic function of a Markov process to automatic speech recognition.

Bell Syst.Tech.J. 62,4(Apr.),1035-1074.

61.Llewellyn J.A. 1987.

Data compression for a source with Markov characteristics.

Comput.J. 30,2,149-156.

62.Lynch M.F. 1973.

Compression of bibliographic files using an adaption of run-length coding. Inf.Storage Retrieval 9,207-214.

63.Lynch T.J. 1985.

Data Compression - Techniques and Application.

Lifetime Learning Publications, Belmont, CA.

64.Mayne A. and James E.B. 1975.

Information compression by factorizing common strings. Comput.J.18,2,157-160.

65.G. & C. Merriam Company 1963.

Webster's Seventh New Collegiate Dictionary.

Springfield, MA.

66.Miller V.S. and Wegman M.N. 1984.

Variations on a theme by Ziv and Lempel.

In Combinatorial Algorithms on Words.A.Apostolico and Z.Galil,

Eds.NATO ASI Series, Vol.F12.Springer-Verlag,Berlin,pp.131-140

67.Moffat A. 1987.

Word based text compression.

Res.Rept.,Dept.of Computer Science, Univ.of Melbourne,Victoria,Australia.

68.Moffat A. 1988a.

A data structure for arithmetic encoding on large alphabets.

In Proceeding of the 11th Australian Computer Science Conference. Brisbane,Australia(Feb.),pp.309-317.

69.Moffat A. 1988b.

A note on the PPM data compression algorithm.

Res.Rept.88/7,Dept.of Computer Science, Univ.of Melbourne, Victoria,Australia.

70.Morris R. 1978.

Counting large numbers of events in small registers.

Commun.ACM 21,10(Oct.),840-842.

71.Morrison D.R. 1968.

PATRICIA - Practical Algorithm To Retvieve Information Coded In Alphanume­ric.

J.ACM 15,514-534.

72.Ozeki K. 1974a.

Optimal encoding of linguistic information.

Systems, Computers, Controls 5, 3, 96-103.

Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D,No.6,June 1974, pp.361-368.

73.Ozeki K. 1974b.

Stochastic context-free grammar and Markov chain.

Systems, Computers, Controls 5, 3, 104-110.

Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D,No.6,June 1974, pp.369-375.

74.Ozeki K. 1975.

Encoding of linguistic information generated by a Markov chain which is associated with a stochastic context-free grammar.

Systems, Computers, Controls 6, 3, 75-78.

Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.58-D,No.6,June 1975, pp.322-327.

75.Pasco R. 1976.

Source coding algorithms for fast data compression.

Ph.D. dissertation.Dept.of Electrical Engineering, Stanford Univ.

An early exposition of the idea of arithmetic coding, but lacking the idea of incremental operation.

76.Pike J. 1981.

Text compression using a 4 bit coding system.

Comput.J.24,4.

77.Rabiner L.R. and Juang B.H. 1986.

An Introduction to Hidden Markov models.

IEEE ASSP Mag.(Jan.).

78.Raita T. and Teuhola J.(1987).

Predictive text compression by hashing.

ACM Conference on Information Retrieval,New Orleans.

79.Rissanen J.J. 1976.

Generalized Kraft inequality and arithmetic coding.

IBM J.Res.Dev.20,(May.),198-203.

Another early exposition of the idea of arithmetic coding.

80.Rissanen J.J. 1979.

Arithmetic codings as number representations.

Acta Polytechnic Scandinavica, Math 31(Dec.),44-51.

Further develops arithmetic coding as a practical technique for data representation.

81.Rissanen J.J. 1983.

A universal data compression system.

IEEE Trans.Inf.Theory IT-29,5(Sept.),656-664.

82.Rissanen J.J. and Langdon G.G. 1979.

Arithmetic coding.

IBM J.Res.Dev.23,2(Mar.),149-162.

Describes a broad class of arithmetic codes.

83.Rissanen J.J. and Langdon G.G. 1981.

Universal modeling and coding.

IEEE Trans.Inf.Theory IT-27,1(Jan.),12-23.

Shows how data compresion can be separated into modeling for prediction and coding with respect to a model.

84.Roberts M.G. 1982.

Local order estimating Markovian analysis for noiseless source coding and authorship identification. Ph.D.dissertation.Stanford Univ.

85.Roden M., Pratt V.R. and Even S. 1981.

Linear algorithm for data compression via string matching.

J.ACM 28,1(Jan.),16-24.

86.Rubin F. 1976.

Experiments in text file compression.

Commun.ACM 19,11,617-623.

One of the first papers to present all the essential elements of practical arithmetic coding, including fixed-point computation and incremental operation.

87.Rubin F. 1979.

Arithmetic stream coding using fixed precision registers.

IEEE Trans.Inf.Theory IT-25,6(Nov.),672-675.

88.Ryabko B.Y. 1980.

Data compression by means of a "book stack".

Problemy Peredachi Informatsii 16,4.

89.Schieber W.D. and Thomas G.W. 1971.

An algorithm for compaction of alphanumeric data.

J.Library Automation 4,198-206.

90.Schuegraf E.J. and Heaps H.S. 1973.

Selection of equifrequent word fragments for information retrieval. Inf.Storage Retrieval 9,697-711.

91.Schuegraf E.J. and Heaps H.S. 1974.

A comparison of algorithms for data-base compression by use of fragments as language elements. Inf.Storage Retrieval 10,309-319.

92.Shannon C.E. 1948.

A mathematical theory of communication.

Bell Syst.Tech.J.27(Jul.),398-403.

93.Shannon C.E. 1951.

Prediction and entropy of printed English.

Bell Syst.Tech.J.(Jan.),50-64.

94.Snyderman M. and Hunt B. 1970.

The myriad virtues of text compaction.

Datamation 1(Dec.),36-40.

95.Storer J.A. 1977.

NP-completeness results concerning data compression. Tech.Rept.234.Dept.of Electrical Engineering and Computer Science, Princeton Univ.,Princeton,NJ.

96.Storer J.A. 1988.

Data Compression: Methods and Theory.

Computer Science Press, Rockville,MD.

97.Storer J.A. and Szymanski T.G. 1982.

Data compression via textual substitution.

J.ACM 29,4(Oct.),928-951.

98.Svanks M.I. 1975.

Optimizing the storage of alphanumeric data.

Can.Datasyst.(May),38-40.

99.Tan C.P. 1981.

On the entropy of the Malay language.

IEEE Trans.Inf.Theory IT-27,3(May),383-384.

100.Thomas S.W., McKie J., Davies S., Turkowski K., Woods J.A. and Orost J.W. 1985.

Compress (Version 4.0) program and documentation.

Available from joe@petsd.UUCP.

101.Tischer P. 1987.

A modified Lempel-Ziv-Welch data compression scheme.

Aust.Comp.Sci.Commun. 9,1,262-272.

102.Todd S., Langdon G.G. and Rissanen J. 1985.

Parameter reduction and context selection for compression of gray-scale images.

IBM J.Res.Dev.29,2(Mar.),188-193.

103.Tropper R. 1982.

Binary-coded text, a compression method.

Byte 7,4(Apr.),398-413.

104.Vitter J.S. 1987.

Design and analysis of dynamic Huffman codes.

J.ACM 34,4(Oct.),825-845.

105.Vitter J.S. 1989.

Dynamic Huffman coding.

ACM Trans.Math.Softw. 15,2(Jun.),158-167.

106.Wagner R.A. 1973.

Common phrase and minimum-space text storage.

Commun.ACM 16,3, 148-152.

107.Walker D.E. and Amsler R.A. 1986.

The use of machine-readable dictionaries in sublanguage analysis.

In Analysis languages in restricted domains: Sublanguage description and processing, R.Grishman and R.Kittridge, Eds.Lawrence Erlbaum Associates,Hillsdale, NJ, pp.69-83.

108.Welch T.A. 1984.

A technique for high-performance data compression.

IEEE Computer 17,6(Jun.),8-19.

A very fast coding technique based on the method of [119], but those compression performance is poor by the standarts of a [16] and [19]. An improved implementation of this method is widely used in UNIX systems under the name "compress".

109.White H.E. 1967.

Printed English compression by dictionary encoding.

In Proceedings of the Institute of Electrical and Electronics Engineering 55, 3,390-396.

110.Williams R. 1988.

Dynamics-history predictive compression.

Inf.Syst. 13,1,129-140.

111.Witten I.H. 1979.

Approximate, non-deterministic modelling of behavior sequences. Int.J.General Systems 5(Jan.),1-12.

112.Witten I.H. 1980.

Probabilistic behavior/structure transformations using transitive Moore models.

Int.J.General Syst.6,3,129-137.

113.Witten I.H. and Cleary J. 1983.

Picture coding and transmission using adaptive modelling of quad trees. In Proceeding of the International Elecrical, Electronics conference 1,Toronto,ON,pp.222-225.

114.Witten I.H.

115.Witten I.H., Neal R. and Cleary J.G. 1987.

Arithmetic coding for data compression.

Commun.ACM 30,6(Jun.),520-540.

116.Wolff J.G. 1978.

Recording of natural language for economy of transmission or storage. Comput.J. 21,1,42-44.

117.Young D.M. 1985.

MacWrite file formats.

Wheels for the mind (Newsletter of the Australian Apple University Consor­tium), University of Western Australia, Nedlands, WA 6009, Australia, p.34

118.Ziv J. and Lempel A. 1977.

A universal algorithms for sequental data compression.

IEEE Trans.Inf.Theory IT-23,3,3(May),337-343.

119.Ziv J. and Lempel A. 1978.

Compression of individual sequences via variable-rate coding.

IEEE Trans.Inf.Theory IT-24,5(Sept.),530-536.

Describes a method of text compression that works by replacing a substring with a pointer to an earlier occurrence of the same substring. Although it performs quite well, it does not provide a clear separation between modeling and coding.