Моделирование для сжатия текстов. Разделы 3-6

>> Универсальные алгоритмы сжатия данных: обзоры

Моделирование для сжатия текстов

(Modeling for Text Compression)

T. Bell, I.H. Witten, J.G. Cleary

(разделы 3-6)

Содержание

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

1. Контекстуальные метода моделирования

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

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

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

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

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

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

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 LZMW

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

3.4.11 LZJ

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

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

3.4.12 LZFG

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

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

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

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

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

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

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

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

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

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

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

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

4.2 Подсчет

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

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

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

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

5. СРАВHЕHИЕ

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

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

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

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

Схема	Авторы	Заданные параметры
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	- сжатие Зива-Лемпела.

Литература

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 for 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.

Об авторах, выходные данные

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.

Сноски:
³ Очевидно, что такой разбор никакой не «тщательный», а именно «жадный» (greedy parsing).
⁴ “Cross-product” – это векторное произведение по-русски.
⁵ Интересно, что, похоже, сами авторы PPM не могут разобраться, как же расшифровывается эта аббревиатура. В статьях с их участием встречается как “prediction by partial matching”, так и “prediction by partial match”. В первой статье 1984 года используется именно “...matching”.
⁶ «Тираж» – это уж совсем жестоко. Часто говорят «кодирование длин серий».

наверх

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)

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

Проекты

Projects

Разделы

Новости:

Новости: