Обратимое сжатие или сжатие без наличия помех

Введение.

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

-S 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(ф) =    S w(o) p(о,ф)

о = -1

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

C(о) = S C(о,ф)

Ф из А

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

p(o,Ф)= c(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), тогда соответствующие веса могут быть вычислены из вероятностей ухода по формуле:

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

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

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

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

w(o)p(o,Ф) = l
П
i=o+1 e(i) ( 1 - e(o) ) p(o,Ф).

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

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

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

e(o) = 1

C(o) + 1

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

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

C(o) C(o) + 1

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

e(o) = q(o)

C(o)

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

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

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

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

e(o) = q(o)

C(o) + q(o)

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

c(o,Ф) ( 1 - e(o) ) = c(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".

Символ	Кодирование
a	a 2/3	( Всего = 2/3 ; 0.58 битов )
b	<ESC> b 1/3 2/4	( Всего = 1/6 ; 2.6 битов )
c	<ESC> c 1/3 1/4	( Всего = 1/12; 3.6 битов )
d	<ESC> <ESC> <ESC> <ESC> d 1/3 1/4 1 1 1	( Всего = 1/12; 3.6 битов )

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

Рисунок 1. Модель с ограниченным числом состояний для пар "a".

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

К сожаления удовлетворительные методы для создания хороших моделей с конечным числом состояний на основании об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 (хотя они и не показаны).

Рисунок 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 узлов. Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспосабливается к требованиям кодируемого текста.

Рисунок 3. Начальная модель ДМС с одним состоянием.

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

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

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

Рисунок 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-схемы.

Имя	Авторы	Отличия
LZ77	Ziv and Lempel [1977]	Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.
LZR	Roden et al. [1981]	Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.
LZSS	Bell [1986]	Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов.
LZB	Bell [1987]	Аналогично LZSS, но для указателей применяется разное кодирование.
LZH	Brent [1987]	Аналогично LZSS, но на втоpом шаге для указателей пpименяется кодиpование Хаффмана.
LZ78	Ziv and Lempel [1978]	Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку.
LZW	Welch [1984]	Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.
LZC	Thomas et al. [1985]	Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.
LZT	Tischer [1987]	Аналогично LZC, но фразы помещаются в LRU-список.
LZMW	Miller and Wegman [1984]	Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.
LZJ	Jakobsson [1985]	Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.
LZFG	Fiala and Greene [1989]	Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна.

описанных Зивом и Лемпелом [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 - первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на 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 в триаде могут возрастать на произвольно большое значение, они представляются целыми кодами переменной длины. Этот метод использован Элиасом [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. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ.

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. Экспериментельно оцениваемые схемы сжатия.

Схема	Авторы	Заданные параметры
DIGM	Snyderman and Hunt [1970]	- Без параметров.
LZB	Bell [1987]	N = 8192 Количество символов в окне. p = 4 Минимальная длина соответствия.
LZFG	Fiala and Greene [1989]	M = 4096 Максимальное число фраз в словаре.
HUFF	Gallager [1978]	- Без параметров.
DAFC	Langdon and Rissanen [1987]	Contexts = 32 Количество контекстов в модели 1-го порядка. Threshold =50 Количество появлений символа, прежде, чем он станет контекстом.
ADSM	Abramson [1989]	- Без параметров.
PPMC	Moffat [1988b]	m = 3 Максимальный размер контекста. Неограниченная память.
WORD	Moffat [1987]	- Без параметров.
DMC	Cormack and Horspool [1987]	t = 1 Предпосылка изменений на текущем пути для клонирования. T = 8 Предпосылка изменений на остальных путях для клонирования.
MTF	Moffat [1987]	size = 2500 Количество слов в списке.

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

Text Type Format Content Size Sample

bib bibliography UNIX "refer" format, ASCII 725 references for books and papers on Computer Science 111.261 characters %A Witten, I.H.; %D 1985; %T Elements of computer typography; %J IJMMS; %V 23

book1 fiction book Unformatted ASCII Thomas Hardy: "Far from the Madding Crowd" 768.771 characters a caged canary - all probably from the window of the house just vacated. There was also a cat in a willow basket, from the partly-opened lid of which she gazed with half-closed eyes, and affectionately-surveyed the small birds around.

book2 non-fiction book UNIX "troff" format, ASCII Witten: "Principles of computer speech" 610.856 characters Figure 1.1 shows a calculator that speaks. .FC "Figure 1.1" Whenever a key is pressed the device confirms the action by saing the key's name. The result of any computation is also spoken aloud.

geo geophysical data 32 bit numbers Seismic data 102.400 characters d3c2 0034 12c3 00c1 3742 007c 1e43 00c3 2543 0071 1543 007f 12c2 0088 eec2 0038 e5c2 00f0 4442 00b8 1b43 00a2 2143 00a2 1143 0039 84c2 0018 12c3 00c1 3fc2 00fc 1143 000a 1843 0032 e142 0050 36c2 004c 10c3 00ed 15c3 0008 10c3 00bb 3941 0040 1143 0081 ad42 0060 e2c2 001c 1fc3 0097 17c3 00d0 2642 001c 1943 00b9 1f43 003a f042 0020 a3c2 00d0 12c3 00be 69c2 00b4 cf42 0058 1843 0020 f442 0080 98c2 0084

news electronic news USENET batch file A variety of topics 377.109 characters In article <18533@amdahl.amdahl.com> thon@uts.amdahl.com (Ronald S. Karr) writes:
>Some Introduction:
>However, we have conflicting ideas concerning what to do with sender
>addresses in headers.
We do, now, support the idea that a pure !-path >coming it can be left as a !-path, with the current hostname prepended

obj1 object code Executable file for VAX Compilation of "progp" 21.504 characters 0b3e 0000 efdd 2c2a 0000 8fdd 4353 0000 addd d0f0 518e a1d0 500c 50dd 03fb 51ef 0007 dd00 f0ad 8ed0 d051 0ca1 dd50 9850 7e0a bef4 0904 02fb c7ef 0014 1100 ba09 9003 b150 d604 04a1 efde 235a 0000 f0ad addd d0f0 518e a1d0 500c 50dd 01dd 0bdd 8fdd 4357 0000 04fb d5ef 000a 7000 c5ef 002b 7e00 8bdd 4363 0000 addd d0f0 518e a1d0 500c 50dd 04fb e7ef 0006 6e00 9def 002b 5000 5067 9def 002b 5200 5270 dd7e

obj2 object code Executable file for Apple Macintosh "Knowledge Support System" program 246.814 characters 0004 019c 0572 410a 7474 6972 7562 6574 0073 0000 0000 00aa 0046 00ba 8882 5706 6e69 6f64 0077 0000 0000 00aa 0091 00ba 06ff 4c03 676f 00c0 0000 0000 01aa 0004 01ba 06ef 0000 0000 0000 00c3 0050 00d3 0687 4e03 7765 00c0 0000 0000 00c3 0091 01d3 90e0 0000 0000 0015 0021 000a 01f0 00f6 0001 0000 0000 0000 0400 004f 0000 e800 0c00 0000 0000 0500 9f01 1900 e501 0204 4b4f 0000 0000 1e00 9f01 3200 e501

paper1 technical paper UNIX "troff" format, ASCII Witten,Neal and Cleary:"Arithmetic coding for data compression" 53.161 characters Such a \fIfixed\fR model is communicated in advance to both encoder and decoder, after which it is used for many messages.
.pp
Alternatively, the probabilities the model assigns may change as each symbol is transmitted, based on the symbol frequencies seen \fIso far\fR in this

paper2 technical paper UNIX "troff" format, ASCII Witten: "Computer (In)security" 82.199 characters Programs can be written which spread bugs like an epidemic. They hide in binary code, effectively undetectable (because nobody ever examins binaries). They can remain dormant for months or years, perhaps quietly and imperceptibly infiltrating their way into the very depths of a system, then suddenly pounce,

pic black and white facsimile picture 1728x2376 bit map 200 pixels per inch CCITT facsimile test, picture 5 (page of textbook) 513.216 characters

progc program Source code in "C", ASCII Unix utility "compress" version 4.0 39.611 characters
compress() { register long fcode; register code_int i = 0; register int c; register code_int ent;

progl program Source code in LISP, ASCII System software 71.646 characters
(defun draw-aggregate-field (f) (draw-field-background f) ; clear background, if any (draw-field-border f) ; draw border, if any (mapc 'draw-field (aggregate-field-subfields f)) ; draw subfields (w-flush (window-w (zone-window (field-zone f)))) t) ; flush it out

progp program Source code in Pascal, ASCII Program to evaluate compression performance of PPM 49.379 characters
if E > Maxexp then {overflow-set to most negative value} begin S:=MinusFiniteS; Closed:=false; end

trans transcript of terminal session "EMACS" editor controlling terminal with ASCII code Mainly screen editing, browsing and using mail 93.695 characters
WFall Term\033[2'inFall Term\033[4'\033[60;1HAuto-saving...\033[28;4H\033[ 60;15Hdone\033[28;4H\033[60;1H\033[K\0\0\033[28;4HterFall Term\033[7' Term \033[7'\033[12'\t CAssignment\033[18'lAssignment\033[19'aAssignment\033 [20'Sassignment\033[21'sAssignment\033[22'Assignment\033[8@\0t \033[ 23'pAssignment\033[24'reAssignment\033[26'sAssignment\033[27'eAssignment

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

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

Текст	Размер	DIGM	LZB	LZFG	HUFF	DAFC	ADSM	PPMC	WORD	DMC	MTF
bib	111261	6.42	3.17	2.90	5.24	3.84	3.87	*2.11	2.19	2.28	3.12
book1	768771	5.52	3.86	3.62	4.56	3.68	3.80	*2.48	2.70	2.51	2.97
book2	610856	5.61	3.28	3.05	4.83	3.92	3.95	2.26	2.51	*2.25	2.66
geo	102400	7.84	6.17	5.70	5.70	*4.64	5.47	4.78	5.06	4.77	5.80
news	377109	6.03	3.55	3.44	5.23	4.35	4.35	*2.65	3.08	2.89	3.29
obj1	21504	7.92	4.26	4.03	6.06	5.16	5.00	*3.76	4.50	4.56	5.30
obj2	246814	6.41	3.14	2.96	6.30	5.77	4.41	*2.69	4.34	3.06	4.40
paper1	53161	5.80	3.22	3.03	5.04	4.20	4.09	*2.48	2.58	2.90	3.12
paper2	82199	5.50	3.43	3.16	4.65	3.85	3.84	2.45	*2.39	2.68	2.86
pic	513216	8.00	1.01	*0.87	1.66	0.90	1.03	1.09	0.89	0.94	1.09
progc	39611	6.25	3.08	2.89	5.26	4.43	4.20	*2.49	2.71	2.98	3.17
progl	71646	6.30	2.11	1.97	4.81	3.61	3.67	*1.90	1.90	2.17	2.31
progp	49379	6.10	2.08	1.90	4.92	3.85	3.73	*1.84	1.92	2.22	2.34
trans	93695	6.78	2.12	*1.76	5.58	4.11	3.88	1.77	1.91	2.11	2.87
В среднем	224402	6.46	3.18	2.95	4.99	4.02	3.95	*2.48	2.76	2.74	3.24

Опыт показывает, что более изощренные статистические модели достигают лучшего сжатия, хотя 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 model	- контекстно-зависимая модель степени o.
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

Abramson D.M. 1989. An adaptive dependency source model for data compression. Commun.ACM 32,1(Jan.),77-83.
Angluin D.,and Smith C.H. 1983. Inductive inference:Theory and methods. Comput.Surv. 15, 3(Sept.),237-269.
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.
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.
Bell T.C. 1986. Better OPM/L test compression. IEEE Trans. Commun. COM-34. 12(Dec.),1176-1182.
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.
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.
Bell T.C. and Moffat A.M. 1989. A note on the DMC data compression scheme. Computer J. 32,1(Feb.), 16-20.
Bell T.C. and Witten I.H. 1987. Greedy macro text compression. Res. Rept.87/285/33. Department of Computers Science, University of Calgary.
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.
Bookstein A. and Fouty G. 1976. A mathematical model for estimating the effectivness of bigram coding. Inf. Process. Manage.12.
Brent R.P. 1987. A linear algorithm for data compression. Aust. Comput. J. 19,2,64-68.
Cameron R.D. 1986. Source encoding using syntactic information source model. LCCR Tech. Rept. 86-7, Simon Fraser University.
Cleary J.G. 1980. An associative and impressible computer. Ph.D. dissertation. Univ. of Canterbury, Christchurch, New Zealand.
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.
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.
Cooper D. and Lynch M.F. 1982. Text compression using variable-to-fixed-length encoding. J. Am. Soc. Inf. Sci. (Jan.), 18-31.
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.
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].
Cortesi D. 1982. An effective text-compression algorithm. Byte 7,1(Jan.),397-403.
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.
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.
Elias P. 1975. Universal codeword sets and representations of the integers. IEEE Trans.Inf.Theory IT-21,2(Mar.),194-203.
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.
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.
Evans T.G. 1971. Grammatical inference techniques in pattern analysis. In Software Engineering, J. Tou. Ed.Academic Press, New York, pp.183-202.
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.
Fiala E.R. and Greene D.H. 1989. Data compression with finite windows. Commun.ACM 32,4(Apr.),490-505.
Flajolet P. 1985. Approximate counting: A detailed analysis. Bit 25,113-134.
Gaines B.R. 1976. Behavior/structure transformations under uncertainty. Int.J.Man-Mach.Stud. 8, 337-365.
Gaines B.R. 1977. System identification, approximation and complexity. Int.J.General Syst. 3,145-174.
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.
Gold E.M. 1978. On the complexity of automation identification from given data. Inf.Control 37,302-320.
Gonzalez-Smith M.E. and Storer J.A. 1985. Parralel algorithms for data compression. J.ACM 32,2,344-373.
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.
Guazzo M. 1980. A general minimum-redundancy source-coding algorithm. IEEE Trans.Inf.Theory IT-26, 1(Jan.),15-25.
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.
Helman D.R. and Langdon G.G. 1988. Data compression. IEEE Potentials (Feb.),25-28.
Horspool R.N. and Cormack G.V. (1983). Data compression based on token recognition. Unbublished.
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.
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.
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.
Jagger D. 1989. Fast Ziv-Lempel decoding using RISC architecture. Res.Rept.,Dept.of Computer Science, Univ.of Canterbury, New Zealand.
Jakobsson M. 1985. Compression of character string by an adaptive dictionary. BIT 25, 4, 593-603.
Jamison D. and Jamison K. 1968. A note on the entropy of partial-known languages. Inf.Control 12, 164-167.
Jewell G.C. 1976. Text compaction for information retrieval systems. IEEE Syst., Man and Cybernetics Soc.Newsletter 5,47.
Jones D.W. 1988. Application of splay trees to data compression. Commun.ACM 31,8(Aug.),996-1007.
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.
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.
Katajainen J., Renttonen M. and Teuhola J. 1986. Syntax-directed compression of program files. Software-Practice and Experience 16,3,269-276.
Knuth D.E. 1973. The Art of Computer Programming. Vol.2, Sorting and Searching. Addison-Wesley, Reading,MA.
Knuth D.E. 1985. Dynamic Huffman coding. J.Algorithms 6,163-180.
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.
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.
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.
Langdon G.G. and Rissanen J.J. 1982. A simple general binary source code. IEEE Trans.Inf.Theory IT-28 (Sept.),800-803.
Langdon G.G. and Rissanen J.J. 1983. A doubly-adaptive file compression algorithms. IEEE Trans.Commun. COM-31, 11(Nov.),1253-1255.
Lelewer D.A. and Hirschberg D.S. 1987. Data compression. Comput.Surv. 13,3(Sept.),261-296.
Lempel A. and Ziv J.1976. On the complexity of finite sequences. IEEE Trans.Inf.Theory IT-22,1(Jan.),75-81.
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.
Llewellyn J.A. 1987. Data compression for a source with Markov characteristics. Comput.J. 30,2,149-156.
Lynch M.F. 1973. Compression of bibliographic files using an adaption of run-length coding. Inf.Storage Retrieval 9,207-214.
Lynch T.J. 1985. Data Compression - Techniques and Application. Lifetime Learning Publications, Belmont, CA.
Mayne A. and James E.B. 1975. Information compression by factorizing common strings. Comput.J.18,2,157-160.
G. & C. Merriam Company 1963. Webster's Seventh New Collegiate Dictionary. Springfield, MA.
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
Moffat A. 1987. Word based text compression. Res.Rept.,Dept.of Computer Science, Univ.of Melbourne,Victoria,Australia.
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.
Moffat A. 1988b. A note on the PPM data compression algorithm. Res.Rept.88/7,Dept.of Computer Science, Univ.of Melbourne, Victoria,Australia.
Morris R. 1978. Counting large numbers of events in small registers. Commun.ACM 21,10(Oct.),840-842.
Morrison D.R. 1968. PATRICIA - Practical Algorithm To Retvieve Information Coded In Alphanume- ric. J.ACM 15,514-534.
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.
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.
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.
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.
Pike J. 1981. Text compression using a 4 bit coding system. Comput.J.24,4.
Rabiner L.R. and Juang B.H. 1986. An Introduction to Hidden Markov models. IEEE ASSP Mag.(Jan.).
Raita T. and Teuhola J.(1987). Predictive text compression by hashing. ACM Conference on Information Retrieval,New Orleans.
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.
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.
Rissanen J.J. 1983. A universal data compression system. IEEE Trans.Inf.Theory IT-29,5(Sept.),656-664.
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.
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.
Roberts M.G. 1982. Local order estimating Markovian analysis for noiseless source coding and authorship identification. Ph.D.dissertation.Stanford Univ.
Roden M., Pratt V.R. and Even S. 1981. Linear algorithm for data compression via string matching. J.ACM 28,1(Jan.),16-24.
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.
Rubin F. 1979. Arithmetic stream coding using fixed precision registers. IEEE Trans.Inf.Theory IT-25,6(Nov.),672-675.
Ryabko B.Y. 1980. Data compression by means of a "book stack". Problemy Peredachi Informatsii 16,4.
Schieber W.D. and Thomas G.W. 1971. An algorithm for compaction of alphanumeric data. J.Library Automation 4,198-206.
Schuegraf E.J. and Heaps H.S. 1973. Selection of equifrequent word fragments for information retrieval. Inf.Storage Retrieval 9,697-711.
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.
Shannon C.E. 1948. A mathematical theory of communication. Bell Syst.Tech.J.27(Jul.),398-403.
Shannon C.E. 1951. Prediction and entropy of printed English. Bell Syst.Tech.J.(Jan.),50-64.
Snyderman M. and Hunt B. 1970. The myriad virtues of text compaction. Datamation 1(Dec.),36-40.
Storer J.A. 1977. NP-completeness results concerning data compression. Tech.Rept.234.Dept.of Electrical Engineering and Computer Science, Princeton Univ.,Princeton,NJ.
Storer J.A. 1988. Data Compression: Methods and Theory. Computer Science Press, Rockville,MD.
Storer J.A. and Szymanski T.G. 1982. Data compression via textual substitution. J.ACM 29,4(Oct.),928-951.
Svanks M.I. 1975. Optimizing the storage of alphanumeric data. Can.Datasyst.(May),38-40.
Tan C.P. 1981. On the entropy of the Malay language. IEEE Trans.Inf.Theory IT-27,3(May),383-384.
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.
Tischer P. 1987. A modified Lempel-Ziv-Welch data compression scheme. Aust.Comp.Sci.Commun. 9,1,262-272.
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.
Tropper R. 1982. Binary-coded text, a compression method. Byte 7,4(Apr.),398-413.
Vitter J.S. 1987. Design and analysis of dynamic Huffman codes. J.ACM 34,4(Oct.),825-845.
Vitter J.S. 1989. Dynamic Huffman coding. ACM Trans.Math.Softw. 15,2(Jun.),158-167.
Wagner R.A. 1973. Common phrase and minimum-space text storage. Commun.ACM 16,3, 148-152.
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.
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".
White H.E. 1967. Printed English compression by dictionary encoding. In Proceedings of the Institute of Electrical and Electronics Engineering 55, 3,390-396.
Williams R. 1988. Dynamics-history predictive compression. Inf.Syst. 13,1,129-140.
Witten I.H. 1979. Approximate, non-deterministic modelling of behavior sequences. Int.J.General Systems 5(Jan.),1-12.
Witten I.H. 1980. Probabilistic behavior/structure transformations using transitive Moore models. Int.J.General Syst.6,3,129-137.
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.
Witten I.H.
Witten I.H., Neal R. and Cleary J.G. 1987. Arithmetic coding for data compression. Commun.ACM 30,6(Jun.),520-540.
Wolff J.G. 1978. Recording of natural language for economy of transmission or storage. Comput.J. 21,1,42-44.
Young D.M. 1985. MacWrite file formats. Wheels for the mind (Newsletter of the Australian Apple University Consortium), University of Western Australia, Nedlands, WA 6009, Australia, p.34
Ziv J. and Lempel A. 1977. A universal algorithms for sequental data compression. IEEE Trans.Inf.Theory IT-23,3,3(May),337-343.
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.

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 teaches 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 research interests include prediction and modeling, machine learning, and office information systems. He has published around 80 papers and three books: Communication 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).

 TIMOTHY BELL             
 Department of Computer Science,        
 University of Canterbury, Christchurch, New Zealand   
 IAN H. WITTEN            
 Department of Computer Science,        
 University of Calgary, Calgary, Alberta, Canada T2N 1N4  
 JOHN G. CLEARY            
 Department of Computer Science,        
 University of Calgary, Calgary, Alberta, Canada T2N 1N4  
    MODELING FOR TEXT COMPRESSION     
 ACM Computing Surveys. Vol.21, No.4( Dec.1989 ), pp.557-591.
    CATEGORIES AND SUBJECT DESCRIPTORS:    
  Data compaction and compression, information theory. 
      GENERAL TERMS:       
   Algorithms, Experimentation, Mearsurement.   
    ADDITIONAL KEY WORDS AND PHRASES:    
  Adaptive modeling, arithmetic coding, context modeling, 
 natural language, state modeling, Ziv-Lempel compression.