Введення.

Стиснення скорочує обсяг простору, тpебуемого для зберігання файлів в ЕОМ, і
кількість часу, необхідного для передачі інформації по каналу встановленої
ширини пропускання. Це є форма кодування. Іншими цілями кодування
є пошук і виправлення помилок, а також шифрування. Процес пошуку і
виправлення помилок протилежний стиснення - він збільшує надмірність даних,
коли їх не потрібно представляти в зручній для сприйняття людиною формі. Видаляючи
з тексту надмірність, стиснення сприяє шіфpованію, що затpудняет пошук
шіфpа доступним для зломщика статистичним методом.
Рассмотpім оборотне стиснення або стиснення без наявності перешкод, де початковий
Текст може бути в точності відновлений з стиснутого стану. Необоротне або
хибне стиск використовується для цифрового запису аналогових сигналів, таких як
людська мова або малюнки. Оборотне стиснення особливо важливо для текстів,
записаних на природних і на штучних мовах, оскільки в цьому випадку
помилки зазвичай неприпустимі. Хоча першочерговим областю застосування
розглянутих методів є стиснення текстів, що отpажает і наша термінологія,
однак, ця техніка може знайти застосування і в інших випадках, включаючи оборотне
кодування послідовностей дискретних даних.
Існує багато вагомих причин виділяти ресурси ЕОМ у pасчете на стислий
уявлення, тому що більш швидка передача даних і сокpащеніе пpостpанства для
їх хpаненія дозволяють зберегти значні кошти і часто поліпшити
показники ЕОМ. Стиснення ймовірно буде залишатися в сфері уваги через все
зростаючих обсягів збережених і переданих в ЕОМ даних, крім того його можна
використовувати для подолання деякими фізичних обмежень, таких як,
напpимеp, порівняно низька ширина пpопусканія телефонних каналів.


ЗАСТОСУВАННЯ РОЗШИРЮЄТЬСЯ ДЕРЕВ для стиснення даних.

Стиснення можуть підвищувати ефективність збереження і передачі даних
за допомогою скорочення кількості їх надмірності. Алгоритм стиснення бере в
як входу текст джерела і виробляє відповідний йому стислий текст,
коли як розгортаються алгоритм має на вході стислий текст і отримує з
нього на виході початковий текст джерела. Більшість алгоритмів стиснення
розглядають вихідний текст як набір рядків, що складаються з літер алфавіту
вихідного тексту.
Надмірність в поданні рядка S є L (S) - H (S), де L (S) є довжина
подання до бітах, а H (S) - ентропія - міра змісту інформації, також
виражена в бітах. Алгоритмів, які могли б без втрати інформації стиснути
рядок до меншого числа бітів, ніж складає її ентропія, не існує. Якщо з
вихідного тексту витягувати по одній літері деякого випадкового наборів,
використовує алфавіт А, то ентропія знаходиться за формулою:

- ¬ 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асшіреніе призводить до локально адаптованого алгоритму стиснення, якому
чудово простий і швидкий, хоча і не дозволяє досягти оптимального стиснення.
Коли він застосовується до арифметичним кодами, то результат стиснення близький до
оптимальному і приблизно оптимальний за часом.

Коди префікса.

Більшість широко досліджуваних алгоритмів стиснення даних засновані на кодах
Хаффмана. У коді Хаффмана кожна літера вихідного тексту представляється в архіві
кодом змінної довжини. Більш часті літери передаються короткими кодами,
менш часті - довгими. Коди, що використовуються в стислому тексті повинні підкорятися
властивостям префікса, а саме: код, використаний в стислому тексті не може бути
префіксом будь-якого іншого коду.
Коди префікса можуть бути знайдені за допомогою дерева, в якому кожен лист
відповідає одній букві алфавіту джерела. 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азмер стислого тексту буде лежати в межах визначеного коефіцієнта від
розміру архіву, отриманого при використанні коду Хаффмана.
Як було спочатку описано, розширення застосовується до дерев, що зберігають
дані у внутрішніх вузлах, а не в листі. Дерева ж кодів префікса несуть всі
свої дані тільки в листках. Існує, однак, варіант розширення, званий
полурасшіреніем, який застосовується для дерева кодів префікса. При ньому цільової
вузол не переміщається в корінь і модифікація його спадкоємців не проводиться,
натомість шлях від кореня до мети просто зменшується вдвічі. Полурасшіреніе досягає
тих же теоретичних кордонів у межах постійного коефіцієнта, що і
розширення.
У разі зигзагоподібного обходу лексикографічного дерева, проведення як
розширення, так і полурасшіренія ускладнюється, на відміну від прямого маршруту по
лівому або правому краю дерева до цільового вузла. Цей простий випадок показаний на
малюнку 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 to twicemax do
up [i]: = i div 2;
for j: = 1 to maxchar do 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 then begin (залишаємо пара)
d: = up [c];
(Переміна місцями спадкоємців пари)
b: = left [d];
if c = b then begin 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);

Щоб стиснути букву вихідного тексту її потрібно закодувати, використовуючи дерево
кодів, а потім передати. Оскільки процес кодування проводиться при обході
дерева від листа до кореня, то біти коду записуються у зворотному порядку.
Для зміни по?? ядка проходження бітів процедура compress застосовуються свій стек,
біти з якого дістаються з одного і передаються процедурі 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 = 0 then 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. Обидва алгоритми були реалізовані на Паскалі, схожих по
опису за представленим тут мовою.

Арифметичні Коди.

Текст, отриманий при стисненні арифметичних даних, розглядається як
дробу, де кожна буква в алфавіті зв'язується з деякими подінтервалом
відкритого справа інтервалу [0,1). Текст джерела можна розглядати як
буквальне уявлення дробу, що використовує систему числення, де кожна
буква в алфавіті використовується як числа, а інтервал значень, пов'язаних з
ній залежить від частоти зустрічальності цієї букви. Перша буква стислого тексту
(сама "значуща" цифра) може бути декодувати знаходженням букви, полуінтеpвал
якої включає значення пpедставляющей текст дробу. Після визначення
черговий букви вихідного тексту, дріб перераховується для знаходження
наступної. Це здійснюється вирахуванням з дробу основи пов'язаної з знайденої
буквою підобласті, і діленням результату на ширину її полуінтервала. Після
завершення цієї операції можна декодувати наступну літеру.
Як приклад арифметичного кодування розглянемо алфавіт з 4-х букв
(A, B, C, D) з вірогідністю (0.125, 0.125, 0.25, 0.5). Інтервал [0,1) може
бути розділений таким чином:
A = [0, 0.125), B = [0.125, 0.25), C = [0.25, 0.5), D = [0.5, 1).
Розподіл інтервалу легко здійснюється за допомогою накопичення ймовірностей
кожної літери алфавіту і її попередників. Дан стислий текст 0.6 (
представлений у вигляді десяткового дробу), тоді перший його буквою повинна бути D,
тому що це число лежить в інтервалі [0,5, 1). Перерахунок дає результат:
(0.6 - 0.5)/0.5 = 0.2
Другий буквою буде B, тому що нова дріб лежить в інтервалі [0.125, 0.25).
Перерахунок дає:
(0.2 - 0.125)/0.125 = 0.6.
Це означає, що 3-я буква є D, і вихідний текст за відсутності інформації про
його довжини, буде повторюється рядком DBDBDB ...
Першочерговою проблемою тут є висока точність арифметики для
розуміння і опеpіpованія з суцільним двійкового потоку, яким виглядає стислий
текст, що розглядається в якості числа. Ця проблема була вирішена в 1979 році.
Ефективність стиснення методом статичного арифметичного кодування буде дорівнює
H, тільки при використанні арифметики необмеженої точності. Але й
обмеженою точності більшості машин достатньо, щоб дозволяти здійснювати
дуже гарне стиснення. Цілих змінних довжиною 16 бітів, 32-бітових творів
і подільних достатньо, щоб результат адаптивного арифметичного стискання лежав у
кількох відсотках від межі і був чи не завжди трохи краще, ніж у
оптимального адаптованого коду Хаффмана, запропонованого Уітер.
Як і у випадку кодів Хаффмана, статичні арифметичні коди вимагають двох
проходів або початкового знання частот букв. Адаптовані арифметичні
коди вимагають ефективного алгоритму для підтримки і зміни інформації про
що біжить, і накопичуваної частотах у міру обробки букв. Найпростіший шлях для
цього - завести лічильник для кожної літери, що збільшує своє значення на одиницю
кожного разу, коли зустрінута сама ця буква або будь-яка з наступних після неї в
алфавіті. Відповідно до цього підходу, частота букви є різниця між
числом її появ і числом появ її попередників. Цей простий підхід
може зажадати O (n) операцій над буквою n-арного алфавіту. У реалізованому на
Сі Уіттеном, Нейлом і Клірі алгоритмі стиснення арифметичних даних, середня
значення було покращено за допомогою використання дисципліни move-to-front, що
скоротило кількість лічильників, значення яких ізмененяются кожного разу, коли
обробляється буква.
Подальше поліпшення організації розподілу накопиченої частоти вимагає
корінного відходу від простих СД. Вимоги, яким повинна відповідати ця СД краще
вивчити, якщо виразити її через абстрактний тип даних з наступними п'ятьма
операціями: initialize, update, findletter, findrange і maxrange. Операція
ініціалізації встановлює частоту всіх букв в 1, і будь-яка не рівне нулю
значення буде діяти до тих пір, поки алгоритм кодування і
розкодування використовують однакові початкові частоти. Початкове значення
частоти, що дорівнює нулю, присвоюватиметься символу як порожнього інтервалу,
т.ч. попереджаючи його від передачі або отримання.
Операція update (c) збільшує частоту букви с. Опції findletter і findrange
назад один одному, і update може виконувати будь-яка зміна порядку алфавіта,
поки зберігається ця зворотній зв'язок. У будь-який момент часу findletter (f, c,
min, max) буде повертати букву c і пов'язаний з нею накопичений частотний
інтервал [min, max), де f [min, max). Зворотній функція findrange (c, min,
max) буде повертати значення min і max для даної літери c.
Функція maxrange повертає суму всіх частот всіх букв алфавіту, вона потрібна
для перерахування накопичених частот в інтервалі [0, 1).

Застосування розширення до арифметичним кодами.

Ключем до реалізації СД, накопичує значення частот і в гіршому випадку
що вимагає для кожної букви менш, ніж O (n) операцій для n-літерного алфавіту,
є представлення букв алфавіту як листя дерева. Кожен лист
дерева має вагу, рівний частотою зустрічаються букви, вага кожного вузла
представляє собою суму ваг його спадкоємців. Малюнок 7 демонструє таку
дерево для 4-х-літерного алфавіту (A, B, C, D) з вірогідністю (0.125,
0.125, 0.25, 0.5) і частотами (1, 1, 2, 4). Функція maxrange на такому дереві
обчислюється елементарно - вона просто повертає вагу кореня. Опції update і
findrange можуть бути обчислені методом обходу дерева від листа до кореня, а функція
findletter - від кореня до листа.

СД для представлення дерева накопичуються частот по суті такі ж, як
і розглянуті раніше для представлення дерева кодів префіксів, з додаванням
масиву, що зберігає частоти кожного вузла.

const
maxchar = ... (Maximum source character code);
succmax = maxchar + 1;
twicemax = 2 * maxchar + 1;
root = 1;
type
codetype = 0 .. maxchar (source character code range);
bit = 0 .. 1;
upindex = 1 .. maxchar;
downindex = 1 .. twicemax;
var
up: array [downindex] of upindex;
freq: array [downindex] of integer;
left, right: array [upindex] of downindex;

Ініціалізація цієї структури включає в себе не тільки побудова деревоподібній
СД, але і ініціалізацію частот кожного аркуша та вузла таким чином:

procedure initialize;
var
u: upindex;
d: downindex;

begin
for d: = succmax to twicemax do freq [d]: = 1;
for u: = maxchar downto 1 do begin
left [u]: = 2 * u;
right [u]: = (2 * u) + 1;
freq [u]: = freq [left [u]] + freq [right [u]];
up [left [u]]: = u;
up [right [u]]: = u;
end;
end (initialize);

Для того, щоб відшукати букву і відповідний їй інтервал накопиченої
частоти, коли відома окрема накопичена частота, необхідно обійти дерево
починаючи з кореня у напрямку до букви, виробляючи побіжне обчислення інтервалу
частот, що відповідає поточній гілці дерева. Інтервал, відповідний кореня,
є [0, freq [root]], він повинен містити f. Якщо окремий вузол деpева i пов'язаний
з інтервалом [a, b), де a - b = freq [i], то інтервалами, пов'язаними з двома
піддерев будуть інтервали [a, a + freq [left [i]]) і [a + freq [left [i]], b). Вони
не перетинаються, тому шлях вниз по дереву буде таким, що f міститься в
подінтервале, пов'язаному з кожним вузлом на цьому шляху. Це показано в
наступній процедурі:

procedure findsymbol (f: integer; var c: codetype; var a, b: integer);
var
i: downindex;
t: integer;

begin
a: = 0;
i: = root;
b: = freq [root];
repeat
t: = a + freq [left [i]];
if f
i: = left [i];
b: = t;
end else begin (повоpот напpаво)
i: = right [i];
a: = t;
end;
until i> maxchar;
c: = i - succmax;