Введення.
Стиснення скорочує обсяг простору, т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ас
ширення призводить до локально адаптованого алгоритму стиснення, якому помічаючи-
тельно простий і швидкий, хоча і не дозволяє досягти оптимального стиснення. Ко-
та він застосовується до арифметичним кодами, то результат стиснення близький до опти-
бітної і приблизно оптимальний за часом.
Коди префікса.
Більшість широко досліджуваних алгоритмів стиснення даних засновані на кодах
Хаффмана. У коді Хаффмана кожна літера вихідного тексту представляється у архі
ве кодом змінної довжини. Більш часті літери передаються короткими кодами,
менш часті - довгими. Коди, що використовуються в стислому тексті повинні підкорятися
властивостям префікса, а саме: код, використаний в стислому тексті не може
бути префіксом будь-якого іншого коду.
Коди префікса можуть бути знайдені за допомогою дерева, в якому кожен лист
відповідає одній букві алфавіту джерела. 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 і find-
range назад один одному, і update може виконувати будь-яка зміна порядку ал-
фавіта, поки зберігається ця зворотній зв'язок. У будь-який момент часу findletter
(F, c, min, max) буде повертати букву c і пов'язаний з нею накопичений
частотний інтервал [min, max), де f [min, max). Зворотній функція find-
range (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;
end (findsymbol);
Щоб знайти пов'язаний з буквою частотний інтервал, процес, описаний в
findsymbol повинен відбуватися у зворотному напрямку. Спочатку єдність-
ною інформацією, відомої про букву вузла дерева i, є частота цієї букви -
freq [i]. Це означає, що інтервал [0, freq [i]) буде відповідати будь-
або букві, якщо весь алфавіт складається з неї однієї. Дано: інтервал [a, b) свя-
зан з деяким листом піддамся