Стиснення даних

Стиснення скорочує обсяг простору, тpебуемого для зберігання файлів в ЕОМ, і.

кількість часу, який буде необхідний передачі на каналі встановленої.

ширини пропускання. Це є форма кодування. Іншими цілями кодування.

є пошук і освоєння виправлення помилок, і навіть шифрування. Процес пошуку миру і.

виправлення помилок протилежний стиску — він збільшує надмірність даних,.

коли їх треба подавати да зручною до людиною формі. Видаляючи.

з тексту надмірність, стиснення сприяє шиф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© log —— ,.

з A p©.

де C (S) є кількість літер у рядку, p© є статична ймовірність.

появи деякою літери З. Якщо оцінки p© використана частота появи.

кожної літери з в рядку P. S, то H© називається самоэнтропией рядки P. S. У цьому.

статті H (P.S) використовуватиметься позначення самоэнтропии рядки, взятій з.

статичного источника.

Розширювані дерева зазвичай описують форми лексикографічної упорядкованості.

деpевьев двоичного пошуку, вони ж, використовувані при стискуванні даних можуть.

мати постійної упорядкованості. Усунення упорядкованості призводить до.

значному спрощення основних операцій розширення. Отримані у результаті.

алгоритми гранично швидкі і компактні. Що стосується застосування кодів Хаффмана,.

pасширение призводить до локально адаптованому алгоритму стискування, котоpый.

чудово простий і швидкий, хоча й дозволяє досягти оптимального стискування.

Коли його до арифметичним кодам, то результат стискування близький до.

оптимальному і близько оптимальний по времени.

КОДИ ПРЕФИКСОВ.

Більшість широко досліджуваних алгоритмів стискування даних засновані на кодах.

Хаффмана. У коді Хаффмана кожна літера вихідного тексту представляється в архіві.

кодом перемінної довжини. Більше часті літери видаються короткими кодами,.

менш часті - довгими. Коди, використовувані стислому тексті мають підкорятися.

властивостями префікса, саме: код, використаний стиснутому тексті може бути.

префіксом іншого кода.

Коди префікса вдасться знайти у вигляді дерева, коли кожен лист.

відповідає однієї букві алфавіту джерела. Hа pисунке 1 показано дерево коду.

префікса для алфавіту з 4 літер. Код префікса для літери то, можливо прочитаний при.

обході деpева від кореня до цієї букві, де 0 відповідає вибору лівої його галузі,.

а 1 — правої. Дерево коду Хаффмана є дерево з выравненным вагою, де кожен.

листок має вагу, рівний частоті народження літери на вихідному тексті, а.

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

частоти літер A, B, З і D будуть 0.125, 0.125, 0.25 і 0.5 соответственно.

Звичайні коди Хаффмана вимагають попередньої інформації про частоті народження.

літер на вихідному тексті, що веде до його подвійного перегляду — один.

щоб одержати значень частот літер, інший щодо самого стискування. У.

наступному, значення цих частот треба об'єднувати із самою стиснутим текстом, щоб.

надалі уможливити його розгортання. Адаптивне стиснення виконується.

за крок, т.к. код, використовуваний кожної літери початкового тексту, грунтується.

на частотах решти кpоме неї літер абетки. Основи для ефективної.

реалізації адаптивного коду Хаффмана було закладено Галлагером, Батіг опублікував.

практичну версію такого алгоритму, а Уиттер його pазвил.

Оптимальний адаптований код Уиттера завжди лежать у межах біта на.

букву джерела стосовно оптимальному статичному коду Хаффмана, які зазвичай.

становить кілька відсотків від H. До того ж, статичні коди Хаффмана завжди.

лежать у межах біта на букву вихідного тексту від H (вони досягають цей.

межа тільки коли всім літер p© = 2). Існують алгоритми стискування.

які можуть опинитися долати ці обмеження. Алгоритм Зива-Лемпелла, наприклад,.

привласнює слова з аpхива фіксованою довжини рядкам вихідного тексту.

пеpеменной довжини, а арифметичне стиснення може використовуватиме кодування.

літер джерела навіть частки бита.

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

Розширювані дерева були вперше описані у 1983 року і більше подpобно.

розглянуті в 1985. Спочатку вони порузумівались як вид самосбалансиpованных.

деpевьев двоичного пошуку, і це також показано, що вказують здійснити.

найшвидшу реалізацію пріоритетних черг. Якщо вузол розширюваного дерева.

доступний, воно є розширеним. Це означає, що доступний вузол стає.

коренем, все вузли ліворуч від нього утворюють нове ліве поддерево, вузли справа ;

нове праве поддерево. Розширення характеризується обході дерева від старої.

кореня до цільовому вузлу і скоєнні пpи цьому локальних змін, тому ціна.

розширення пропорційна довжині пройденого пути.

Тарьян і Слейтон показали, що розширювані дерева статично оптимальні.

Інакше кажучи, якщо коди доступних вузлів взято відповідно до статичному.

розподілу ймовірності, то швидкості доступу до расширяющемуся дереву і.

статично збалансованого, оптимизированному цим розподілом, будуть.

відрізнятися одне від друга на постійний коефіцієнт, помітний за досить.

довгих серіях доступів. Оскільки дерево Хаффмана являє приклад.

статичним збалансованого дерева, то пpи використанні розширення для стискування.

даних, pазмер стиснутого тексту лежатиме не більше деякого коефіцієнта від.

розміру архіву, отриманого під час використання коду Хаффмана.

Як було спочатку описано, розширення застосовується до дерев, хранящим.

дані у внутрішніх вузлах, а чи не в листі. Дерева ж кодів префікса несуть все.

є дані лише у листі. Існує, проте, варіант розширення, званий.

полурасширением, який застосуємо для дерева кодів префікса. За нього цільової.

вузол не переміщається в корінь і модифікація його спадкоємців немає,.

замість шлях від кореня до мети просто зменшується вдвічі. Полурасширение сягає.

тієї ж теоретичних меж, посеред межах постійного коефіцієнта, як і.

расширение.

Що стосується зигзагоподібного обходу лексикографічного дерева, проведення як.

розширення, і полурасширения ускладнюється, на відміну прямого маршруту по.

лівому чи правому краю дерева до цільовому вузлу. Цей простий випадок показаний на.

малюнку 2. Вплив полурасширения на маршруті від кореня (вузол w) до аркуша.

вузла A залежить від зміні місцями кожної пари внутрішніх наступних друг за.

іншому вузлів, у результаті довжина шляху від кореня до узла-листа скорочується в.

2 разу. У процесі полурасширения вузли кожної пари, більш далекі від кореня,.

входять у новий шлях (вузли x і z), причому більше близькі з него.

виключаються (вузли w і y).

Збереження операцією полурасширения лексикографічного ладу у деревах коду.

префікса перестав бути обов’язковим. Єдине важливим у бойових операціях з кодом.

префікса є точне відповідність дерева, використовуваного процедурою стискування.

дереву, використовуваному процедурою розгортання. Будь-яке його зміна, допущене.

між послідовно що йдуть літерами, роблять лише у разі, якщо.

обидві процедури здійснюють однакові зміни у однаковому порядке.

Hенужность підтримки лексикографічного порядку значно спрощує проведення.

операції полурасширения з допомогою винятку випадку зигзагу. Це то, можливо.

зроблено перевіркою вузлів по дорозі від кореня до цільовому аркушу і зміною місцями.

правих спадкоємців зі своїми братами. Назвемо це ПОВОРОТОМ дерева. Тепеpь новий код.

префікса для цільового аркуша складатиметься з одних нулів, оскільки вона став.

самим лівим листом. На малюнку 3 дерево було повернутим навколо аркуша З. Ця.

операція не порушує ніяких обмежень уявлення полурасширения.

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

між собою як спадкоємців одного вузла, але й внутрішні вузли дерева.

кодів префіксів, оскільки вони анонімні і несуть інформації. Це дозволяє.

замінити яка у полурасширении операцію обоpота на операцію, що вимагає.

обміну лише двома ланками у ланцюзі, яку називатимемо ПІВОБЕРТОМ.

Вона показано малюнку 4. Ця операція впливає так ж впливом геть довжину шляху.

від кожної аркуша до кореня, як і під повний обоpот, але знищує лексикографический.

порядок, виконуючи у нашій прикладі відсікання і пересадку лише двох гілок на.

дереві, тоді як повний обоpот здійснює відсікання і пересадку 4.

ветвей.

Справжньою необхідності повертати дерево перед операцією полурасширения немає.

Натомість полурасширение може бути застосована до маршруту від кореня до цільової.

вершині як до самого лівому шляху. Наприклад, дерево малюнку 3 то, можливо.

розширене безпосередньо як показано малюнку 5. У цьому вся прикладі дерево.

полурасширяется навколо аркуша З, використовуючи полуобоpот кожної пари внутрішніх.

вузлів по дорозі від З до корені. Потрібно звернути увагу, у результаті цієї.

зміни кожен лист розташований рівній відстані від кореня, що коли.

б деpево було спочатку повернутим отже З був лівим листом, та був.

полурасширено звичайним шляхом. Підсумкове дерево відрізняється лише знаками.

внутрішніх вузлів і зміною місцями спадкоємців деяких із них.

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

різняться між собою четной чи нечетной довжиною шляху від кореня до аркушу. У.

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

і: downindex;

j: upindex;

begin.

for і := 2 to twicemax do.

up[i] := і divx 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.

з, d: upindex { пари вузлів для полуобоpота };

a, b: downindex { вpащаемые спадкоємці вузлів };

begin.

a := plain + succmax;

repeat { обхід знизу вгору получередуемого дерева }.

з := up[a];

if з # root then begin { оставляемая пара }.

d := up[c];

{ зміна місцями спадкоємців пари }.

b := left[d];

if з = 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 := з { управління кінці непарною вузлом };

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 = 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 і звичайно становить дві% від H. Результат роботи алгоритму розширюваного.

префікса будь-коли перевищує H більше, ніж 20%, інколи ж багато менше.

H .

Тестові дані включають програму на Сі (файл 1), дві програми на Паскале.

(файли 2 і трьох) і довільний текстовий файл (файл 4). Усі текстові файли.

використовують безліч символів коду ASCII з табуляцією, замінної групи з 8.

прогалин на початку, і всі прогалини у кінці рядків. Всім цих файлів Лалгоритм.

сягає результатів, складових приблизно 60% від розмірів вихідного тексту, а.

алгоритм розширення — 70%. Це найбільш гірший випадок стискування, спостережуваний при.

порівнянні алгоритмов.

Два объектых файла М68 000 були стислі (файли 5 і шість) також можуть добре, як і файли.

виведення TEX в форматі .DVI (файл 7). Вона має меншу надмірність, ніж.

текстові файли, і тому один метод стискування неспроможна скоротити їх розмір

досить ефективно. Проте, обом алгоритмам вдається успішно стиснути.

дані, причому алгоритм розширення дає деякі результати, великі результатів роботи.

Л-алгоритма приблизно на 10%.

Були стиснуті три графічних файла, містять зображення людських осіб (.

файли 8, 9 і десяти). Вони містять різне число крапок і реалізовані через 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 станами, аби домогтися.

результату, кращого ніж в команди стискування, заснованої на методі Зива-Лемпела, а.

модель із чотирьох станами вже перекриває H. Для текстового файла модель з 64.

станами вже близька за результатом до команди стискування, а модель з 8 станами.

достатня задля подолання бар'єра H. Для графічних даних (файл 8) моделі.

із 16-го станами досить, щоб поліпшити результат команди стискування, у своїй.

все моделі за своїми наслідками чудово перекривають H. Моделі Маркова більш.

ніж із 8 станами були б менш ефективні, ніж простий статична модель,.

застосовуваний до графічним даним, а найгірший результат спостерігався для моделі.

з 3 станами. Це вийшло через ту причину, що використання моделі Маркова.

служить перешкодою локально адаптованому поведінці алгоритму расширяемого.

префикса.

Обидва алгоритму, Лі расширяемого префікса, виконуються за часом прямо.

пропорційно розміру вихідного файла, в обох випадках, вихід найгіршому.

варіанті має довжину O (H), т.а. обидва їх необхідно виконувати у разі під час.

O (H). Постійні коефіцієнти відрізняються, оскільки алгоритм расширяемого.

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

виході більше бітов. Для 13 файлів, поданих у таблиці I, Лалгоритм.

виводить загалом 2К бітов в секунду, як алгоритм расширяемого префікса ;

більш 4К бітов в секунду, т.а. другий алгоритм завжди значно швидше. Ці.

показники отримано на робочої станції М68 000, серії 200 9836CU Хьюлет.

Паккард, має OC HP-UX. Обидва алгоритму були реалізовані на Паскале, подібним по.

опису з представленим тут языком.

АРИФМЕТИЧНІ КОДЫ.

Tекст, отриманий при стисканні арифметичних даних, розглядається як.

дробу, де кожна літера в алфавіті пов’язують із деяким подинтервалом.

відкритого справа інтервалу [0,1). Текст джерела можна як.

буквальне уявлення дробу, використовує систему обчислення, де кожна.

літера в алфавіті використовують у ролі числа, а інтервал значень, що з.

ній залежить від частоти народження цієї літери. Перша літера стиснутого тексту.

(сама «варта «цифра) то, можливо декодирована перебуванням літери, полуинтеpвал.

якої включає значення пpедставляющей текст дробу. Після визначення.

черговий літери початкового тексту, дріб перераховується перебування.

наступній. Це здійснюється відніманням з дробу основи що з знайденою.

буквою подобласти, і розподілом результату на ширину її полуинтервала. Після.

завершення цієї операції можна декодировать таку букву.

Як приклад арифметичного кодування розглянемо алфавіт з 4-х літер

(A, B, З, D) з імовірностями (0.125, 0.125, 0.25, 0.5). Інтервал [ 0,1) може.

бути розділений наступним образом:

A = [ 0, 0.125), B = [ 0.125, 0.25), З = [ 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© збільшує частоту літери з. Функції findletter і findrange.

обратны одна одній, і update може виконувати будь-яка зміна порядку алфавіту,.

поки зберігається ця зворотний. Першої-ліпшої хвилини часу findletter (f, з,.

min, max) повертатиме букву з і пов’язані з нею нагромаджувальний частотний.

інтервал [ min, max), де f [ min, max). Зворотний функція findrange (з, min,.

max) повертатиме значення min і max для даної літери c.

Функція maxrange повертає суму всіх частот всіх літер абетки, вона нужна.

для перерахування накопичених частот в інтервалі [ 0, 1).

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

Ключем до реалізації СД, накапливающей значення частот й у гіршому випадку.

що вимагає кожної літери менш, ніж O (n) операцій для n-буквенного алфавіту,.

є уявлення літер абетки як листя дерева. Кожен листок.

дерева має вагу, рівний частоті встречаемой літери, вагу кожного вузла.

є сумою терезів його спадкоємців. Малюнок 7 демонструє таке.

дерево для 4-х-буквенного алфавіту (A, B, З, 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ева і пов’язаний.

з інтервалом [a, b), де a — b = freq[i], то інтервалами, пов’язані з двома.

поддеревьями будуть інтервали [a, a+freq[left[i]]) і [a+freq[left[i]], b). Вони.

не перетинаються, тому шлях вниз з дерева буде так, що f міститься у.

подинтервале, що з кожним вузлом цьому шляху. Це показано в.

наступній процедуре:

procedure findsymbol (f: integer; var з: codetype; var a, b: integer);

var.

і: downindex;

t: integer;

begin.

a := 0;

і := root;

b := freq[root];

repeat.

t := a + freq[left[i]];

if f < t then begin { повоpот наліво }>

і := left[i];

b := t;

end else begin { повоpот напpаво }.

і := right[i];

a := t;

end;

until і > maxchar;

з := і - succmax;

end { findsymbol };

Щоб знайти пов’язані з буквою частотний інтервал, процес, описаний в.

findsymbol має відбуватися у напрямі. Спочатку єдиною.

інформацією, відомої про букві вузла дерева і, є частота цієї літери freq[i].

Це означає, що інтервал [0, freq[i]) відповідатиме якийсь букві,.

якщо весь алфавіт складається з неї однієї. Дано: інтервал [a, b) пов’язані з деяким.

листом поддерева з коренем в вузлі і, тоді то, можливо вирахувано інтервал,.

пов’язаний із цією листом в поддереве up[i]. Якщо і - лівий спадкоємець, це.

просто інтервал [ a, b), якщо правий, то — [ a + d, b + d), где.

d = freq[up[i]] - freq[i], чи, що одне те: d = freq[left[up[i]]].

procedure findrange (з: codetype; var a, b: integer);

var.

і: downindex;

d: integer;

begin.

a := 0;

і := з + succmax;

b := freq[i];

repeat.

if right[up[i]] = і then begin { і is right child }.

d := freq[left[up[i]]];

a := a + d;

b := b + d;

end;

і := up[i];

until і = root;

end { findrange };

Якщо проблему збереження збалансованості в дереві накопичуваних частот не.

стоїть, то функція update буде тривіальної, що з обходу дерева від.

змінюваного аркуша до кореня, супроводжуваного збільшенням значення кожного.

зустрінутого вузла на одиницю. Інакше час, витрачене для операцій.

findletter, findrange і update при спочатку збалансованому дереві буде зацікавлений у.

сpеднем O (log n) однією букву для n-буквенного алфавіту. Це краще, ніж гірший.

варіант O (n), який досягається з застосування лінійної СД (улаштуванням.

move-to-front чи ні неї), але, можливо поліпшено еще.

Зауважте, кожна літера, стиснута арифметичним методом вимагає звернення до.

процедурі findrange, котрого супроводжує виклик update. Т.а. шлях від кореня до літери.

в дереві накопичуваних частот буде виконано двічі під час стискування і двічі у.

час розгортання. Мінімізація загального часу стискування чи розгортання.

повідомлення вимагає мінімізації загальної довжини всіх шляхів, пройдених в дереві. Якщо.

частоти літер відомі наперед, то статичне дерево Хаффмана буде мінімізувати.

довжину цього маршруту! Довжина шляхи до повідомлення P. S буде обмежена значенням.

2(Hs (S) + C (S)), де C (S) — кількість літер у рядку, а множник 2 відбиває той.

факт, кожен маршрут минається дважды.

Немає сенсу використання дерева накопичуваних частот, коли всі ймовірності.

відомі наперед, що дозволяє застосовувати просту пошукову таблицю для.

перебування ймовірностей. Якщо вони самі невідомі, то оптимальний Л-алгоритм Уиттера.

то, можливо легко модифікований керувати деревом накопичуваних частот,.

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

нічого очікувати перевищувати значення 2(H (P.S) + C (S)). Аналогічно можна використовувати.

алгоритм розширюваного префікса, що дає обмеження O (H (P.S)) для довжини шляху,.

але за більшому постійному множителе. Раніше пpиведенные досвідчені результати.

показують, що це постійні множники більш як компенсуються простотой.

алгоритму розширюваного префикса.

Відповідно до цим алгоритмом операції розширення непотрібно торкатися.

інформації внутрішніх вузлів дерева. Коли розширення виконується, як частина.

операції update, кожна операція полувpащения повинна предохранять инвариацию.

регулювання терезів вузлів дерева. На малюнку 8 дерево полувpащается навколо А,.

маючи результатом те, що вагу Х скорочується вагою Проте й нарощується вагою З. У той.

водночас, оскільки це є частка повторного шляху від, А до корені, вагу А.

збільшується. Підсумковий код будет:

procedure update (з: codetype);

var.

з, d: upindex { пара полувpащаемых вузлів };

a, b: downindex { спадкоємці полувpащемых вузлів };

begin.

a := з + succmax;

repeat { вгору з дерева, чергуючи і нарощуючи }.

з := up[a];

if з # root then begin { що залишилося пара }.

d := up[c];

{ обмін між спадкоємцями пари }.

b := left[d];

if з = 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;

freq[c] := (freq[c] - freq[a]) + freq[b];

freq[a] := freq[a] + 1;

a := d;

end else begin { приміщення непарного (непарного) вузла насамкінець шляху }.

freq[a] := freq[a] + 1;

a := up[a];

end;

until a = root;

freq[root] := freq[root] + 1;

end { update };

Програма ігнорує проблему переповнення лічильників частот. Арифметичне.

стиснення даних постійно виробляє обчислення за такою формулою a * b / з, і межа.

точності результату обчислення визначається розміром пам’яті, виділеної.

проміжним творам і діленим, а чи не самим целочисленным змін ным.

Багато 32-битные машини накладають 32-битовое обмеження на твори.

ділені, і т.а. насправді встановлюють 16-битовый межа подання.

цілих чисел a, b і з в вищевказаному вираженні. Коли це обмеження передається.

коду найбільш витратну програму архиватора, то чистий результат має обмеження в 16 383.

для максимального значення, возвращаемого функцією maxrange чи значення.

freq[root]. Тому, якщо стиснений файл має довжину більш 16 383 байтів, необхідно.

періодично перераховувати все частоти в СД, щоб втиснути в цей інтервал.

Простий шлях до цього — розділити значення всіх частот на маленьку константу,.

наприклад 2, і округленням вгору уберегти частоти від обнуления.

Значення листя в дереві накопичуваних частот легко може бути перераховані.

розподілом на 2, але значення внутрішніх вузлів перелічити по таким легким шляхом за.

труднощі поширення округляемых результатів вгору з дерева. Найпростіший.

спосіб перебудови дерева показаний у наступному процедуре:

procedure rescale;

var.

u: upindex;

d: downindex;

begin.

for d := succmax to twicemax do.

freq[d] := (freq[d] + 1) divx 2;

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 { rescale };

Характеристика арифметичних кодов.

Hа основі алгоpитма Виттена, Нейла і Клірі вышепредставленные процедури були.

обьединены серед мови Паскаль. Як і передбачалося, значної різниці між.

стиснутими текстами, одержаними у результаті робіт початкового і.

модифікованого алгоритмів арифметичного стискування немає. Зазвичай це.

тексти мають однакову длину.

Малюнок 9 показує швидкість цих двох алгоритмів як функцію від H. Час.

представлено в милисекундах на байт вихідного тексту, а ентропія — в бітах на.

байт джерела. Файли з 2 битами/байт і побачили 8-го битами/байт створені штучно, а.

інші представляють собой:

цифровий графічний файл, використовує 16 відтінків сірого кольору (3.49.

бит/байт);

текстовій файл (4.91 бит/байт вихідного тексту);

M68000 об'єктний файл (6.02 бит/байт).

Час вимірювалося на робочої станції HP9836 серед HP-UX.

Як зазначено малюнку 9, застосування розширення до дерева накопичуваних частот.

покращує алгоритм move-to-front, використовуваний Виттеном, Нейлом і Клірі [12],.

тільки коли сжимаемые дані мають ентропію більше, ніж 6.5 бит/байт. Нижче.

цього значення метод move-to-front працює трохи краще розширення.

Т.а. розширення й інші підходи до балансування дерева накопичуваних частот.

мабуть не виправдовуються пpи стисканні даних, використовують 256-буквенный алфавіт.

Проте, досліди показують, що з більшого алфавіту pасширение може бути кращим.

подходом.

Заключение

.

Поданий тут алгоритм расширяемого префікса є мабуть самим.

простою й швидким адаптивним алгоритмом стискування, заснованому на використанні коду.

префікса. Його характерні риси — невелика кількість необхідної ВП і.

локально адаптивне поведінка. Коли доступні більше об'ємів пам’яті,.

використання цього алгоритму разом із моделлю Маркова часто дозволяє стиснути.

дані краще, чому це роблять конкуруючі алгоритми цьому ж обсязі памяти.

Переваги алгоритму розширюваного префікса найнаочніше видно при стисканні.

графічних даних. Локально адаптований характер алгоритму дозволяє стискати.

зображення до меншій кількості біт, ніж самоэнтропия, вимірювана у статичного.

джерела. У результаті, проста модель Маркова, застосована алгоритмі.

розширюваного префікса, часто дозволяє здійснити краще стиснення, ніж широко.

використовуваний алгоритм Зива-Лемпела на порівнянному обсязі памяти.

Алгоритми арифметичного стискування даних можуть виконуватися під час O (H) при.

використанні дерева накопичуваних частот, балансируемого эвристическим.

розширенням для необхідної алгоритмом статистичної моделі. Це створює нове.

обмеження, тому простий евристичний метод приміщення на початок (move.

— to-front) ефективніша для маленьких типових алфавитов.

І алгоритм розширюваного префікса, і розширення керувати.

деревом накопичуваних частот служать корисними ілюстраціями застосування.

розширення керувати лексикогpафически неупорядоченными деревами. Ідея.

повороту, предваряющего розширення дерева, може застосовуватись і в.

нелексикографических деревах, як і поняття полуобоpота балансування.

таких дерев. Наприклад, їх можна застосовувати щодо злиття, пpи використанні.

двоичного дерева з 2-га шляхами злиття для побудови n-путевого слияния.

Цікаво зазначити, що, порівняно коїться з іншими адаптивними схемами стискування,.

втрата тут 1 біта з потоку стиснутих даних є катастрофою! Тому.

pешение проблеми відновлення цієї втрати представляє безсумнівний інтерес,.

що, крім того припускає можливість використання таких схем стискування в.

криптографії. Відомо, що стиснення повідомлення перед його шифровкою.

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

надмірності інформацією зашифрованому тексті, а стиснення скорочує це.

надмірність. Нова можливість, подана у описаних тут алгоритми.

стискування, полягає у використанні початкового стану дерева префікса кодів чи.

початкового стану дерева накопичуваних частот як ключа для прямого.

шифрування у процесі стискування. Алгоритм арифметичного стискування може ще.

ускладнити зломщика кодів тим, що кордони літер необов’язково перебувають.

ще й між битами.

Ключове простір для такого алгоритму шифрування величезна. Для n літер

алфавіту існує n! перестановок на листі кожного з З дерев, містять.

n — 1 внутрішніх вузлів, де З = (2i)! / і! (i+1)! є i-ое число Каталана.

Це — твір спрощується до (2(n-1))! / (n-1)!. Для n = 257 (256 літер із.

символом end-of-file кінця файла) це завжди буде 512!/256! або щось менше 2 .

Щільна спектакль ключа від цього простору займатиме 675.

байт, тому безсумнівно такі великі ключі можуть експортувати глухий кут. На.

практиці одна з рішення полягатиме на початку роботи з роботи вже.

збалансованим деревом, як й у розглянутий тут алгоритми стискування, та був.

розширенні цього дерева навколо кожного символу з ключовою рядки,.

наданої користувачем. Вpяд вони буде вводити ключі довжиною 675 байт,.

хоча, аби дозволити розширенню встановити дерево в усі можливі стану,.

потрібні ключі ще довші аніж цей, і навіть короткий ключ можуть дозволити.

здійснити шифрування на прийнятному уровне.