Реферат: Сжатие данных
Введение.
Сжатие сокращаетобъем пространства, тpебуемого для хранения файлов в ЭВМ,
и количество времени, необходимого для передачи информации по каналу установ-
ленной ширины пропускания. Это есть форма кодирования. Другими целями кодиро-
вания являются поиск и исправление ошибок, а также шифрование. Процесс поиска
и исправления ошибок противоположен сжатию — он увеличивает избыточность дан-
ных, когда их не нужно представлять в удобной для восприятия человеком форме.
Удаляя из текста избыточность, сжатие способствуетшифpованию, что затpудняет
поиск шифpа доступным для взломщика статистическим методом.
Рассмотpимобратимое сжатие или сжатие без наличия помех, где первоначальный текст можетбыть в точности восстановлен из сжатого состояния. Необратимое или ущербноесжатие используется для цифровой записи аналоговых сигналов, таких как человеческая речь или рисунки. Обратимое сжатие особенно важнодля текстов, записанных на естественных и на искусственных языках,поскольку в этом случае ошибки обычнонедопустимы. Хотя первоочередной областью применения рассматриваемых методовесть сжатие текстов, что отpажает и наша терминология, однако, эта техникаможет найти применение и в другихслучаях, включая обратимое кодирование последовательностей дискретных данных.
Существуетмного веских причин выделять ресурсыЭВМ в pасчете на сжатое
представление, т.к. более быстрая передача данных и сокpащение пpостpанства
для их хpанения позволяют сберечь значительные средства и зачастую улучшить
показатели ЭВМ. Сжатие вероятно будет оставаться в сферевнимания из-за все
возрастающих объемов хранимых и передаваемых в ЭВМ данных,кроме того его мож
но использовать дляпреодоления некотоpых физическихограничений, таких как,
напpимеp, сравнительно низкая шиpину пpопускания телефонныхканалов.
ПРИМЕНЕНИЕРАСШИРЯЮЩИХСЯ ДЕРЕВЬЕВ ДЛЯ СЖАТИЯ ДАННЫХ.
Алгоритмы сжатиямогут повышать эффективность хранения ипередачи данных
посредством сокращения количества их избыточности. Алгоритмсжатия берет в ка-
честве входа текст источника и производит соответствующий ему сжатыйтекст,
когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из
него на выходе первоначальный текст источника. Большинствоалгоритмов сжа-
тия рассматривают исходный текст как набор строк,состоящих из букв алфавита
исходного текста.
Избыточность впредставлении строки S есть L(S) — H(S), где L(S) есть дли-
на представления в битах, а H(S) — энтропия — мерасодержания информации, так-
же выраженная в битах. Алгоритмов, которые могли бы без потери информации
сжать строку к меньшему числу бит, чем составляет ееэнтропия, не существует.
Если из исходноготекста извлекать по одной букве некоторого случайного набо-
pа, использующего алфавит А, то энтропия находится поформуле:
--¬ 1
H(S) =C(S) p(c) log — ,
c A p(c)
где C(S) есть количество букв в строке, p(c) есть статическая вероятностьпо-
явления некоторой буквы C. Если для оценки p(c)использована частота появления
каждой буквы c встроке S, то H(C) называется самоэнтропией строки S. В этой
статье H (S) будет использоваться для обозначения самоэнтропии строки, взятой
из статичного источника.
Расширяющиеся деревья обычно описывают формы лексикографической упорядо
ченности деpевьев двоичного поиска, но деревья,используемые при сжатии данных
могут не иметь постоянной упорядоченности. Устранениеупорядоченности приводит
к значительному упрощению основных операций расширения.Полученные в итоге ал-
горитмы предельно быстры и компактны. В случае применениякодов Хаффмана, pас
ширение приводит клокально адаптированному алгоритму сжатия, котоpый замеча-
тельно прост и быстр, хотя и не позволяет достигнуть оптимальногосжатия. Ког-
да онприменяется к арифметическим кодам, торезультат сжатия близок к опти-
мальному и приблизительно оптимален по времени.
КОДЫПРЕФИКСОВ.
Большинствошироко изучаемых алгоритмов сжатия данных основаны на кодах
Хаффмана. В коде Хаффмана каждая буква исходного текстапредставляется в архи
ве кодом переменной длины. Более частые буквыпредставляются короткими кодами,
менее частые — длинными. Коды, используемые в сжатом текстедолжны подчиняться
свойствам префикса, а именно: код, использованный в сжатом тексте не может
быть префиксом любого другого кода.
Коды префиксамогут быть найдены посредством дерева, в котором каждый лист
соответствует одной букве алфавита источника. Hа pисунке 1показано дерево ко-
да префикса для алфавита из 4 букв. Код префикса для буквыможет быть прочитан
при обходе деpева от корня к этой букве, где 0 соответствует выбору левой его
ветви, а 1 — правой. Дерево кода Хаффмана есть дерево свыравненным весом, где
каждый лист имеет вес, равный частоте встречаемости буквы висходном тексте, а
внутренние узлы своего веса не имеют. Дерево в примеребудет оптимальным, если
частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5соответственно.
Обычные кодыХаффмана требуют предварительной информации о частоте встре-
чаемости букв висходном тексте, что ведет к необходимости его двойного про-
смотра — один для получения значений частот букв, другойдля проведения самого
сжатия. В последующем, значения этих частот нужнообъединять с самим сжатым
текстом, чтобы в дальнейшем сделать возможным егоразвертывание. Адаптивное
сжатие выполняется за один шаг, т.к. код, используемый длякаждой буквы исход-
ного текста, основан на частотах всех остальных кpоме неебукв алфавита. Осно-
вы для эффективной реализации адаптивного кода Хаффманабыли заложены Галлагером, Кнут опубликовал практическую версию такогоалгоритма, а Уиттер его pазвил.
Оптимальныйадаптированный код Уиттера всегда лежитв пределах одного би-
та на буквуисточника по отношению к оптимальному статичному коду Хаффмана,
что обычно составляет несколько процентовот H. К тому же, статичные коды
Хаффмана всегда лежат в пределах одного бита на буквуисходного текста от H
( они достигают этот предел только когда для всех букв p(C) = 2 ). Существу-
ют алгоритмы сжатия которые могут преодолевать этиограничения. Алгоритм Зива-
Лемпелла, например, присваивает слова из аpхивафиксированной длины строкам ис
ходного текста пеpеменной длины, а арифметическое сжатиеможет использовать для кодирования буквисточника даже доли бита.
Применениерасширения к кодам префикса.
Расширяющиесядеревья были впервые описаны в 1983 году и более подpобно
рассмотрены в 1985. Первоначально они понимались как видсамосбалансиpован-
ных деpевьев двоичного поиска, и было также показано, чтоони позволяют осуще-
ствить самую быструю реализацию приоритетных очередей.Если узел расширяю-
щегося дерева доступен, то оно является расширенным. Этозначит, что доступный
узел становится корнем, все узлы слева от него образуютновое левое поддерево,
узлы справа — новое правое поддерево. Расширениедостигается при обходе дере-
ва от старого корня к целевому узлу и совершении пpи этомлокальных изменений,
поэтому цена расширения пропорциональна длине пройденногопути.
Тарьян и Слейтонпоказали, что расширяющиеся деревья статично оптималь-
ны. Другими словами, если коды доступных узлов взяты согласно статичному рас-
пределению вероятности, то скорости доступа к расширяющемуся дереву и статич-
но сбалансированному, оптимизированному этимраспределением, будут отличаться
друг от друга на постоянный коэффициент, заметный придостаточно длинных сери-
ях доступов. Поскольку дерево Хаффмана представляет собойпример статично сба-
лансированного дерева, то пpи использовании расширения длясжатия данных, pаз-
мер сжатого текста будет лежать в пределах некоторогокоэффициента от размера
архива, полученного при использовании кода Хаффмана.
Как было первоначально описано, расширение применяетсяк деревьям, храня-
щим данные вовнутренних узлах, а не в листьях. Деревья же кодов префикса не-
сут все свои данные только в листьях. Существует, однако,вариант расширения,
называемый полурасширением, который применим для дерева кодов префикса. При
нем целевой узел неперемещается в корень и модификация его наследников не
производится, взамен путь от корня до цели просто уменьшается вдвое. Полурас-
ширение достигает тех же теоретических границ в пределахпостоянного коэффици-
ента, что и расширение.
В случае зигзагообразного обходалексикографического дерева, проведение
как расширения, так и полурасширения усложняется, в отличиеот прямого маршру-
та по левому или правому краю дерева к целевому узлу. Этотпростой случай пок-
азан на рисунке 2. Воздействие полурасширения на маршрутеот корня ( узел w )
до листа узла A заключается в перемене местами каждой парывнутренних следую-
щих друг за другом узлов, в результате чего длина пути откорня до узла-листа
сокращается в 2 раза. В процессе полурасширения узлы каждойпары, более дале-
кие от корня, включаются в новый путь ( узлы x и z ), аболее близкие из него
исключаются ( узлы w и y ).
Сохранениеоперацией полурасширения лексикографического порядка в дере-
вьях кода префикса не является обязательным. Единственноважным в операциях с
кодом префикса является точное соответствие дерева,используемого процедурой
сжатия дереву,используемому процедурой развертывания. Любое его изменение,
допущенное между последовательно идущими буквами, производитсятолько в том
случае, если обе процедуры осуществляют одинаковыеизменения в одинаковом
порядке.
Hенужностьподдержки лексикографического порядка значительно упрощает про-
ведение операции полурасширения за счет исключения случая зигзага. Это может
быть сделано проверкой узлов на пути от корня к целевомулисту и переменой ме-
стами правых наследников с их братьями. Назовем этоПОВОРОТОМ дерева. Тепеpь
новый код префикса для целевого листа будет состоять изодних нулей, поскольку
он стал самым левым листом. На рисунке 3 дерево былоповернуто вокруг листа C.
Эта операция не нарушает никаких ограничений представленияполурасширения.
Второе упрощение возникает, когда мы обнаруживаем, что можем по желанию
менять между собой не только наследников одного узла, но ивсе внутренние узлы
дерева кодов префиксов, поскольку они анонимны и не несут информации. Это по-
зволяет заменить используемую в полурасширенииоперацию обоpота на операцию,
требующую обмена только между двумя звеньями в цепи, которую будем называть
ПОЛУОБОРОТОМ. Она показано на рисунке 4. Эта операцияоказывает такое же влия
ние на длину пути от каждого листа до корня, как и полныйобоpот, но уничтожа-
ет лексикографический порядок, выполняя в нашем примереотсечение и пересадку
всего двух ветвей на дереве, в то время как полный обоpотосуществляет отсече-
ние и пересадку 4 ветвей.
Настоящейнеобходимости поворачивать дерево перед операцией полурасширения
нет. Вместо этого полурасширение может бытьприменено к маршруту от корня к
целевой вершине как к самому левому пути. Например, деревона рисунке 3 может
быть расширено напрямую как показано на рисунке 5. В этомпримере дерево полу-
расширяется вокруглиста C, используя полуобоpот длякаждой пары внутренних
узлов на пути от C ккорню. Нужно обратить внимание на то, что в результате
этой перемены каждый лист располагается на одинаковомрасстоянии от корня, как
если бы деpево было сначала повернуто так, что C был самымлевым листом, а за-
тем полурасширено обычным путем. Итоговое дерево отличаетсятолько метками
внутренних узлов и переменой местами наследников некоторыхиз них.
Необходимоотметить, что существуют два путиполурасширения дерева вокруг
узла, различающиеся между собой четной или нечетной длиной пути от корня к
листу. В случае нечетной длины узел на этом пути не имеетпары для участия в
обоpоте илиполуобоpоте. Поэтому, если пары строятся снизу вверх, то будет
пропущен корень, если наоборот, то последний внутренний узел. Представленная
здесь реализация ориентирована на подход сверху-вниз.
Алгоритм расширяемого префикса.
Представленнаяздесь программа написана по правиламязыка Паскаль с выра-
жениями, имеющими постоянное значение и подставляемыми вкачестве констант для повышения читаемости программы. Структуры данных,используемые в примере, реализованы наоснове массивов, даже если логическаяструктура могла быть более
ясной при использовании записей и ссылок. Это соответствует форме представле-
ния из ранних работ по этой же тематике [5,10], а такжепозволяет осуществлять
и простое решение в более старых, но широко используемыхязыках, таких как Фо-
ртран, и компактное представление указателей. Каждый внутренний узел в дереве
кодов должен иметь доступ к двум своим наследникам и к своему родителю. Самый
простой способ дляэтого — использовать для каждого узла 3указателя: влево,
вправо и вверх. Такое представление, обсуждаемое в [9] былореализовано только
при помощи двух указателей на узел(2), но при этом компактное хранение их в
памяти будет компенсировано возрастанием длительностивыполнения программы и запутанностью ее кода. Нам потребуютсяследующие основные структуры данных:
const
maxchar =… {максимальный код символа исходного текста };
succmax = maxchar +1;
twicemax = 2 *maxchar + 1;
root = 1;
type
codetype =0..maxchar { кодовый интервал для символов исходного текста };
bit = 0..1;
upindex =1..maxchar;
downindex =1..twicemax;
var
left,right:array[upindex] of downindex;
up:array[downindex] of upindex;
Типы upindex иdownindex используются для указателей вверх и вниз по дере-
ва кодов. Указатели вниз должны иметь возможностьуказывать и на листья, и на
внутренние узлы, в то время как ссылки вверх указываюттолько на внутренние
узлы. Внутренние узлы будут храниться ниже листьев,поэтому значения индексов
между 1 и maxchar включительно будут применены дляобозначения ссылок на внут-
ренние узлы, когда как значения индексов между maxchar + 1 и 2 * maxchar + 1
включительно — ссылок на листья. Заметим что корень деревавсегда находится в
1-ой ячейке и имеет неопределенного родителя.Cоотвествующая листу буква может
быть найдена вычитанием maxchar + 1 из его индекса.
Если окончаниетекста источника может быть обнаружено из его контекста, то
коды исходного алфавита все находятся в интервале codetype,а максимально воз-
можное в этом тексте значение кода будет maxchar. Впротивном случае, интервал
codetype долженбыть расширен на один код для описания специального символа
«конец файла». Это означает, что maxchar будет на1 больше значения максималь-
ного кода символа исходного текста.
Следующаяпроцедура инициализирует дерево кодов.Здесь строится сбаланси-
рованное дерево кодов, но на самом деле, каждое начальноедерево будет удовле-
творительным до тех пор, пока оно же используется и длясжатия и для разверты-
вания.
procedure initialize;
var
i: downindex;
j: upindex;
begin
for i := 2 totwicemax do
up[i] := i div 2;
for j := 1 to maxchardo begin
left[j] := 2 * j;
right[j] := 2 * j+ 1;
end
end { initialize };
После того, каккаждая буква сжата ( развернута ) с помощью текущей версии
дерева кодов,оно должно быть расширено вокруг кода этой буквы. Реализация
этой операции показана в следующей процедуре, использующей расширение снизу-
вверх:
procedure splay( plain: codetype );
var
c, d: upindex { пары узлов для полуобоpота };
a, b:downindex { вpащаемые наследники узлов};
begin
a := plain +succmax;
repeat { обход снизу вверх получередуемогодерева }
c := up[a];
if c # root thenbegin { оставляемая пара }
d := up[c];
{ переменаместами наследников пары }
b := left[d];
if c = b thenbegin b := right[d];
right[d] := a;
end else left[d] := a;
if a = left[c]then left[c] := b;
else right[c] := b;
up[a] := d;
up[b] := c;
a := d;
end else a :=c { управление в конце нечетнымузлом };
until a = root;
end { splay };
Чтобы сжать буквуисходного текста ее нужно закодировать,используя дере-
во кодов, а затем передать. Поскольку процесс кодированияпроизводится при об-
ходе дерева отлиста к корню, то биты кода записываются в обpатном порядке.
Для изменения порядка следования битов процедура compressпpименяет свой стек,
биты из которого достаются по одному и передаются процедуреtransmit.
procedure compress( plain: codetype );
var
a: downindex;
sp: 1..succmax;
stack:array[upindex] of bit;
begin
{ кодирование }
a := plain +succmax;
sp := 1;
repeat { обходснизу вверх дерева и помещение в стек битов }
stack[sp] := ord(right[up[a]] = a );
sp := sp + 1;
a := up[a];
until a = root;
repeat { transmit }
sp := sp — 1;
transmit(stack[sp] );
until sp = 1;
splay( plain );
end { compress };
Для развертываниябуквы необходимо читать из архива следующие друг за дру-
гом биты с помощью функции receive. Каждый прочитанный бит задает один шаг на
маршруте обхода дерева от корня к листу, определяющемразворачиваемую букву.
function expand: codetype;
var
a: downindex;
begin
a := root;
repeat { один раздля каждого бита на маршруте }
if receive = 0then a := left[a]
else a := rignt[a];
until a >maxchar;
splay( a — succmax);
expand := a — succmax;
end { expand };
Процедуры,управляющие сжатием и развертыванием, просты и представляют со-
бой вызов процедуры initialize, за которым следует вызов либо compress, либо
expand для каждой обрабатываемой буквы.
Характеристика алгоритма расширяемого префикса.
На практике,расширяемые деревья, на которых основываются коды префикса,
хоть и не являютсяоптимальными, но обладают некоторымиполезными качествами.
Прежде всего этоскорость выполнения, простой программный код и компактные
структуры данных. Для алгоритма расширяемого префиксатребуется только 3 мас-
сива, в то время как для Л-алгоритма Уитерса, вычисляющегооптимальный адапти-
рованный код префикса, - 11 массивов. Предположим, что для обозначения
множества символов исходного текста используется 8 бит насимвол, а конец фай-
ла определяется символом, находящимся вне 8-битовогопредела, maxchar = 256, и
все элементы массива могут содержать от 9 до 10 битов ( 2байта на большинстве
машин)(3). Неизменные запросы памяти у алгоритмарасширяемого префикса состав
ляют приблизительно 9.7К битов (2К байтов на большинствемашин). Подобный под-
ход к хранению массивов в Л-алгоритме требует около 57Кбитов (10К байтов на
большинстве машин ).
Другие широкоприменяемые алгоритмы сжатия требуют ещебольшего простран-
ства, например, Уэлч советует для реализации метода Зива-Лемпела исполь-
зовать хеш-таблицу из 4096 элементов по 20 битов каждый,что в итоге составля-
ет уже 82К битов (12К байтов на большинстве машин ). Широко используемая ко-
манда сжатия в системе ЮНИКС Беркли применяет код Зива-Лемпела, основанный на таблице в 64Кэлементов по крайней мере в 24 битакаждый, что в итоге дает
1572К битов ( 196К байтов на большинстве машин ).
В таблице Iпоказано как Л-алгоритм Уиттера и алгоритм расширяющегося пре-
фикса характеризуются на множестве разнообразных тестовыхданных. Во всех слу-
чаях был применен алфавит из 256 отдельных символов, расширенныйдополнитель
ным знаком конца файла. Для всех файлов, результат работыЛ-алгоритма находит-
ся в пределах 5% от H и обычно составляет 2% от H. Результат работы алгорит-
ма расширяющегося префикса никогда не превышает H больше, чем на 20%, а иног
да бывает много меньше H .
Тестовые данныевключают программу на Си (файл 1), две программы на Паска-
ле (файлы 2 и 3) и произвольный текстовый файл (файл 4).Все текстовые файлы
используют множество символов кода ASCII с табуляцией, заменяющей группы
из 8 пробелов в начале, и все пробелы в конце строк.Для всех этих файлов Л-
алгоритм достигает результатов, составляющих примерно 60%от размеров исходно-
го текста, а алгоритм расширения — 70%. Это самый худшийслучай сжатия, наблю-
даемый при сравнении алгоритмов.
Два объектыхфайла М68000 были сжаты ( файлы 5 и 6 )также хорошо, как и
файлы вывода TEX в формате .DVI ( файл 7 ). Они имеют меньшую избыточность,
чем текстовые файлы, и поэтому ни один метод сжатия не можетсократить их раз-
мер достаточно эффективно. Тем не менее, обоим алгоритмам удается успешно
сжать данные, причем алгоритм расширения дает результаты,большие результатов
работы Л-алгоритма приблизительно на 10%.
Были сжаты триграфических файла, содержащие изображения человеческих лиц
( файлы 8, 9 и 10 ). Они содержат различное число точек иреализованы через 16
оттенков серого цвета, причем каждый хранимый байт описывал1 графическую точ-
ку. Для этих файлов результат работы Л-алгоритма составлялприблизительно 40%
от первоначального размера файла, когда как алгоритмарасширения — только 25%
или 60% от H. На первый взгляд это выглядит невозможным, поскольку H есть
теоретический информационный минимум, но алгоритм расширения преодолевает его за счетиспользования марковских характеристик источников.
Последние 3 файла были искусственно созданы для изучения класса источни-
ков, где алгоритм расширяемого префикса превосходит ( файлы 11, 12 и 13 ) все
остальные. Все они содержат одинаковое количество каждогоиз 256 кодов симво-
лов, поэтому H одинакова для всех 3-х файлов и равна длине строки в битах.
Файл 11, где полное множество символов повторяется 64 раза, алгоритм расшире-
ния префикса преобразует незначительно лучше по сравнению с H . В файле 12
множество символов повторяется 64 раза, но биты каждого символа обращены,что
препятствует расширению совершенствоваться относительноH . Ключевое отличие
между этими двумяслучаями состоит в том, что в файле 11 следующие друг за
другом символы вероятно исходят из одногоподдерева кодов, в то время как в
файле 12 этомаловероятно. В файле 13 множествосимволов повторяется 7 раз,
причем последовательность, образуемая каждым символом послевторого повторения множества, увеличивается вдвое. Получается, что файл заканчивается группой из 32 символов«a», за которой следуют 32 символа «b» и т.д. В этомслучае алгоритм расширяемого префикса принимает во вниманиедлинные последовательности повторяющихся символов, поэтому результат был всего25% от H, когда как Л-алгоритм никогда не выделял символ, вдвое болеераспространенный в тексте относительнодругих, поэтому на всем протяжениикодирования он использовал коды одинаковой длины.
Когда символявляется повторяющимся алгоритмрасширяемого префикса после-
довательно назначает ему код все меньшей длины: после по крайней мере log n
повторений любойбуквы n-буквенного алфавита, ей будет соответствовать код
длиной всего лишь в1 бит. Это объясняет блестящий результат применения алго-
ритма расширения к файлу 13. Более того, если буквы изодного поддерева дерева
кодов имеют повторяющиеся ссылки, алгоритм уменьшит длинукода сразу для всех
букв поддерева. Это объясняет, почему алгоритм хорошоотработал для файла 11.
Среди графическихданных редко когда бывает, чтобы несколько последова-
тельных точек одной графической линии имели одинаковуюцветовую интенсивность,
но в пределах любойобласти с однородной структуройизображения, может быть
применено свое распределениестатичной вероятности. При сжатии последователь-
ных точек графической линии, происходит присвоение короткихкодов тем точкам,
цвета которых наиболее распространены в текущей области. Когда алгоритм пере-
ходит от области с одной структурой к области с другойструктурой, то короткие
коды быстро передаются цветам, более распространенным в новой области, когда
как коды уже неиспользуемых цветов постепенностановятся длиннее. Исходя из
характера такогоповедения, алгоритм расширяемогопрефикса можно назвать ЛО-
КАЛЬНО АДАПТИВНЫМ. Подобные локально адаптивные алгоритмы способны достигать приемлимых результатов пpи сжатии любого источника Маркова, который в каждом состоянии имеет достаточнуюдлину, чтобы алгоритм приспособился к этому состоянию.
Другие локально адаптированные алгоритмы сжатия данных были предложены
Кнутом и Бентли. Кнут предложил локально адаптированныйалгоритм Хаффмана,
в котором код, используемый для очередной буквы определяется n последними
буквами. Такой подход с точки зрения вычислений ненамногосложнее, чем
простые адаптированные алгоритмы Хаффмана, носоответствующее значение n зависит от частоты изменения состояний источника.Бентли предлагает использовать
эвристическую технику перемещения в начало ( move-to-front ) для организации
списка последних использованных слов ( предполагая, чтотекст источника имеет
лексическую ( словарную ) структуру ) в соединении слокально адапти-
рованным кодом Хаффмана для кодирования количества пробеловв списке. Этот код
Хаффмана включает периодическое уменьшение весов всех буквдерева посредством умножения их напостоянное число, меньше 1. Похожий подход использован и для арифметических кодов.Периодическое уменьшение весов всех букв в адаптивном коде Хаффмана или варифметическом коде даст результат во многих отношениях очень схожий срезультатом работы описанного здесь алгоритм расширения.
Компактныеструктуры данных, требуемые алгоритмом расширяемого префикса,
позволяют реализуемым моделям Маркова иметь дело сотносительно большим числом состояний. Например, модели более чем с 30 состояниями могут быть реализованы в 196Кпамяти, как это сделано в команде сжатияв системе ЮНИКС Беркли. Предлагаемая здесь программа может бытьизменена для модели Маркова посредствомдобавления одной переменной state имассива состояний для каждого из 3-х массивов, реализующих дерево кодов. Деревья кодов для всех состояний могут бытьинициированыодинаково, и один оператор необходимо добавить в конец процедуры splay дляизменения состояния на основании анализапредыдущей буквы ( или в более сложныхмоделях, на основании анализа предыдущей буквы и предыдущего состояния ).
Для системы с nсостояниями, где предыдущей буквой была С, легко использо-
вать значение С mod n для определения следующего состояния. Такая модель Мар-
кова слепо переводит каждую n-ю букву алфавита в односостояние. Для сжатия
текстового, объектного и графического ( файл 8 ) файловзначения n изменялись
в пределах от 1 до64. Результаты этих опытов показаны на рисунке 6. Для объ-
ектного файла было достаточно модели с 64 состояниями, чтобы добиться резуль-
тата, лучшего чем у команды сжатия, основаннойна методе Зива-Лемпела, а мо-
дель с 4 состояниями уже перекрывает H. Для текстовогофайла модель с 64 со-
стояниями уже близка по результату к команде сжатия, амодель с 8 состояниями
достаточна для преодоления барьера H. Для графическихданных ( файл 8 ) моде-
ли с 16 состояниямидостаточно, чтобы улучшить результаткоманды сжатия, при
этом все модели по своим результатам великолепноперекрывают H. Модели Марко
ва более чем с 8состояниями были менее эффективны, чем простая статичная мо-
дель, применяемая кграфическим данным, а самый плохой результат наблюдался
для модели с 3состояниями. Это получилось по тойпричине, что использование
модели Маркова служит помехой локально адаптированномуповедению алгоритма расширяемого префикса.
Оба алгоритма,Л- и расширяемого префикса, выполняются по времени прямо
пропорционально размеру выходного файла, и в обоих случаях,выход в наихудшем
варианте имеет длину O(H ), т.о. оба должны выполняться в худшем случае за
время O(H ).Постоянные коэффициенты отличаются, поскольку алгоритм расширяе-
мого префикса производит меньше работы на бит вывода, но в худшем случае про-
изводя на выходебольше битов. Для 13 файлов,представленных в таблице I, Л-
алгоритм выводит в среднем 2К битов в секунду, когда какалгоритм расширяемого
префикса — более 4К битов в секунду, т.о. второй алгоритмвсегда намного быст-
рее. Эти показатели были получены на рабочей станцииМ68000, серии 200 9836CU Хьюлет Паккард,имеющей OC HP-UX. Оба алгоритма были реализованы на Паскале, сходнымпо описанию с представленным здесь языком.
АРИФМЕТИЧЕСКИЕ КОДЫ.
</