Стиснення

Стиснення скорочує обсяг простору, т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 залежить від зміні місцями кожної пари внутрішніх следую;

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

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

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

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

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

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

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

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

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

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

порядке.

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

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

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

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

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

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

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

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

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

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

зволяет замінити яка у полурасширении операцію обо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 і find;

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

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

(f, з, min, max) повертатиме букву з і пов’язані з нею накапливаемый.

частотний інтервал [ min, max), де f [ min, max). Зворотний функція find;

range (з, 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 байт, хо;

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

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

ществить шифрування на прийнятному уровне.