трусики женские украина

На головну

Стиснення даних - Інформатика

Введення.

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

кількість часу, необхідного для передачі інформації по каналу встановленої

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

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

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

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

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

шифру доступним для зломщика статистичним методом.

Розглянемо оборотне стиснення або стиснення без наявності перешкод, де первинний

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

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

людська мова або малюнки. Оборотне стиснення особливо важливе для текстів,

записаних на природних і на штучних мовах, оскільки в цьому випадку

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

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

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

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

Існує багато ваговитих причин виділяти ресурси ЕОМ з розрахунку на стисле

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

їх зберігання дозволяють зберегти значні кошти і часто поліпшити

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

зростаючі об'єми що зберігаються що і передаються в ЕОМ даних, крім того його можна

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

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

ЗАСТОСУВАННЯ ДЕРЕВ, що РОЗШИРЯЮТЬСЯ ДЛЯ СТИСНЕННЯ ДАНИХ.

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

за допомогою скорочення кількості їх надмірності. Алгоритм стиснення бере як

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

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

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

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

початкового тексту.

Надмірність в представленні рядка S є L(S) - Н(S), де L(S) є довжина

уявлення в бітах, а Н(S) - ентропія - міра змісту інформації, також

виражена в бітах. Алгоритмів, які могли б без втрати інформації стиснути

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

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

що використовує алфавіт А, то ентропія знаходиться по формулі:

-- м 1

Н(S) = З(S) р(з) log ----,

з А р(з)

де З(S) є кількість букв в рядку, р(з) є статична імовірність

появи деякої букви C. Еслі для оцінки р(з) використана частота появи

кожної букви з в рядку S, то Н(З) називається самоэнтропией рядка S. В цій

статті Н (S) буде використовуватися для позначення самоэнтропии рядка, взятого з

статичного джерела.

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

дерев двійкового пошуку, але дерева, ті, що використовуються при стисненні даних можуть не

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

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

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

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

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

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

оптимального і приблизно оптимальний за часом.

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

Більшість алгоритмів стиснення даних, що широко вивчаються засновані на кодах

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

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

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

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

префіксом будь-якого іншого коду.

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

відповідає одній букві алфавіта джерела. На малюнку 1 показане дерево коду

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

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

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

лист має вагу, рівну частоті встречаемости букви в початковому тексті, а

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

частоти букв А, В, З і D будуть 0.125, 0.125, 0.25 і 0.5 відповідно.

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

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

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

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

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

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

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

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

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

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

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

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

лежать в межах одного біта на букву початкового тексту від Н (ні досягають цю

межу тільки коли для всіх букв р(З) = 2). Існують алгоритми стиснення

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

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

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

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

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

Дерева, що Розширяються були уперше описані в 1983 році і більш детально

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

тих же теоретичних меж в межах постійного коефіцієнта, що і

розширення.

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

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

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

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

вузла А полягає в зміні місцями кожної пари внутрішніх наступних один за

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

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

включаються в нову дорогу (вузли х і z), а більш близькі з нього

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

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

префікса не є обов'язковим. Єдино важливою в операціях з кодом

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

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

між послідовно ідучими буквами, виготовляється тільки в тому випадку, якщо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

гілок.

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

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

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

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

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

вузлів на шляху від З до кореня. Треба звернути увагу на те, що внаслідок цієї

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

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

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

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

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

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

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

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

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

орієнтована на підхід зверху-вниз.

Алгоритм префікса, що розширюється.

Представлена тут програма написана за правилами мови Паськаль з виразами,

що мають постійне значення і що підставляються як константи для підвищення

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

основі масивів, навіть якщо логічна структура могла бути більш ясною при

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

робіт по цій же тематиці [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-ой осередку і має невизначеного родителя. Соотвествующая листу буква може

бути знайдена відніманням 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

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

a, b: downindex { спадкоємці вузлів, що обертаються };

begin

а: = plain + succmax;

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

з: = up[a];

if з # root then begin { пара },

що залишається d: = up[з];

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

b: = left[d];

if з = b then begin b: = right[d];

right[d]: = a;

end else left[d]: = a;

if а = left[з] then left[з]: = b;

else right[з]: = b;

up[a]: = d;

up[b]: = з;

а: = d;

end else а: = з { управління в кінці непарним вузлом };

until а = root;

end { splay };

Щоб стиснути букву початкового тексту її треба закодувати, використовуючи дерево

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

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

Для зміни порядку проходження бітів процедура compress застосовує свій стек,

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

procedure compress(plain: codetype);

var

a: downindex;

sp: 1..succmax;

stack: array[upindex] of bit;

begin

{ кодування }

а: = plain + succmax;

sp: = 1;

repeat { обхід знизу вгору дерева і приміщення в стек бітів }

stack[sp]: = ord(right[up[a]] = a);

sp: = sp + 1;

а: = up[a];

until а = root;

repeat { transmit }

sp: = sp - 1;

transmit(stack[sp]);

until sp = 1;

splay(plain);

end { compress };

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

біти за допомогою функції receive. Кожний прочитаний біт задає один крок на

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

function expand: codetype;

var

a: downindex;

begin

а: = root;

repeat { один раз для кожного біта на маршруті }

if receive = 0 then а: = left[a]

else а: = rignt[a];

until а > maxchar;

splay(а - succmax);

expand: = а - succmax;

end { expand };

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

виклик процедури initialize, за яким слідує виклик або compress, або expand

для кожної букви, що обробляється.

Характеристика алгоритму префікса, що розширюється.

На практиці, дерева, що розширюються, на яких засновуються коди префікса, хоч і

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

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

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

час як для Л-алгоритму Уїтерса, обчислюючого оптимальний адаптований код

префікса, - 11 масивів. Передбачимо, що для позначення безлічі символів

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

символом, що знаходиться поза 8-бітовою межею, maxchar = 256, і всі елементи

масиву можуть містити від 9 до 10 бітів (2 байти на більшості машин)(3).

Незмінні запити пам'яті у алгоритму префікса, що розширюється становлять

приблизно 9.7 До бітів (2К байтів на більшості машин). Подібний підхід до

зберігання масивів в Л-алгоритмі вимагає біля 57К бітів (0К байтів на

більшості машин).

Інші широко вживані алгоритми стиснення вимагають ще більшого простору,

наприклад, Уелч радить для реалізації методу Зива-Лемпела використати

хеш-таблицю з 4096 елементів по 20 бітів кожний, що в результаті складає уже82К

бітів (12К байтів на більшості машин). Команда стиснення, що Широко використовується в

системі ЮНИКС Берклі застосовує код Зива-Лемпела, заснований на таблиці в 64К

елементів принаймні в 24 біти кожний, що в результаті дає 1572К бітів (96К

байтів на більшості машин).

У таблиці I показано як Л-алгоритм Уїттера і алгоритм префікса,

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

застосований алфавіт з 256 окремих символів, розширений додатковим знаком

кінця файла. Для всіх файлів, результат роботи Л-алгоритму знаходиться в межах

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

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

Н.

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

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

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

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

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

алгоритм розширення - 70%. Це самий гірший випадок стиснення, що спостерігається при

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

Два объектых файли М68000 були стислі (файли 5 і 6) також добре, як і файли

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

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

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

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

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

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

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

Для цих файлів результат роботи Л-алгоритму становив приблизно 40% від

первинного розміру файла, коли як алгоритму розширення - тільки 25% або

60% від Н. На перший погляд це виглядає неможливим, оскільки Н є

теоретичний інформаційний мінімум, але алгоритм розширення долає його за

рахунок використання марковских характеристик джерел.

Останні 3 файли були штучно створені для вивчення класу джерел, де

алгоритм префікса, що розширюється перевершує (файли 11, 12 і 13) всі інші.

Всі вони містять однакову кількість кожного з 256 кодів символів, тому Н

однакова для всіх 3-х файлів і рівна довжині рядка в бітах. Файл 11, де повна

безліч символів повторюється 64 рази, алгоритм розширення префікса перетворює

трохи краще в порівнянні з Н. У файлі 12 безліч символів повторюється

64 рази, але біти кожного символа звернені, що перешкоджає розширенню

удосконалитися відносно Н. Ключова відмінність між цими двома випадками

складається в тому, що в файлі 11 наступні один за одним символи ймовірно виходять

з одного поддерева кодів, в той час як в файлі 12 це малоймовірно. У файлі

13 безліч символів повторюється 7 разів, причому послідовність, що утворюється

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

Виходить, що файл закінчується групою з 32 символів "a", за якою

слідують 32 символи "b" і т.д. В цьому випадку алгоритм префікса,

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

результат був всього 25% від Н, коли як Л-алгоритм ніколи не виділяв символ,

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

протязі кодування він використав коди однакової довжини.

Коли символ є таким, що повторюється алгоритм префікса,

що розширюється послідовно призначає йому код все меншої довжини: після принаймні log n

повторень будь-якої букви n-буквеного алфавіта, їй буде відповідати код

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

алгоритму розширення до файла 13. Більш того якщо букви з одного поддерева

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

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

11.

Серед графічних даних рідко коли буває, щоб декілька послідовних

точок однієї графічної лінії мали однакову колірну інтенсивність, але в

межах будь-якої області з однорідною структурою зображення, може бути застосоване

свій розподіл статичної імовірності. При стисненні послідовних точок

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

яких найбільш поширені в поточній області. Коли алгоритм переходить від

області з однією структурою до області з іншою структурою, то короткі коди

швидко передаються кольорам, більш поширеним в новій області, коли як коди

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

такої поведінки, алгоритм префікса, що розширюється можна назвати ЛОКАЛЬНО

АДАПТИВНИМ. Подібні локально адаптивні алгоритми здатні досягати результатів, що приймаються

при стисненні будь-якого джерела Маркова, яке в кожному стані

має достатню довжину, щоб алгоритм пристосувався до цього стану.

Інші локально адаптовані алгоритми стиснення даних були запропоновані Батогом і

Бентлі. Батіг запропонував локально адаптований алгоритм Хаффмана, в якому

код, той, що використовується для чергової букви визначається n останніми буквами. Такий

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

алгоритми Хаффмана, але відповідне значення n залежить від частоти зміни

станів джерела. Бентли пропонує використати евристичну техніку

переміщення в початок (move-to-front) для організації списку останніх

використаних слів (редполагая, що текст джерела має лексичну ( словникову) структуру) в з'єднанні з локально адаптованим кодом Хаффмана

для кодування кількості пропусків в списку. Цей код Хаффмана включає

періодичне зменшення ваги всіх букв дерева за допомогою множення їх на

постійне число, менше 1. Схожий підхід використаний і для арифметичних

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

арифметичному коді дасть результат в багатьох відносинах дуже схожий з

результатом роботи описаного тут алгоритм розширення.

Компактні структури даних, необхідні алгоритмом префікса, що розширюється,

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

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

196К пам'яті, як це зроблене в команді стиснення в системі ЮНИКС Берклі.

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

допомогою додавання однієї змінної state і масиву станів для кожного з 3-х

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

бытьинициированы однаково, і один оператор необхідно додати в кінець

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

стану).

Для системи з n станами, де попередньою буквою була З, легко використати

значення З mod n для визначення наступного стану. Така модель Маркова

сліпо переводить кожну n-ю букву алфавіта в один стан. Для стиснення

текстового, об'єктного і графічного (файл 8) файлів значення n змінювалися в

межах від 1 до 64. Результати цих дослідів показані на малюнку 6. Для

об'єктного файла було досить моделі з 64 станами, щоб добитися

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

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

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

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

з 16 станами досить, щоб поліпшити результат команди стиснення, при цьому

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

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

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

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

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

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

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

варіанті має довжину О(Н), т.ч. обидва повинні виконуватися в гіршому випадку за час

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

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

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

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

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

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

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

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

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

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

дріб, де кожна буква в алфавіті зв'язується з деяким подинтервалом

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

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

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

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

(цифра, що сама "означає" ) може бути декодована знаходженням букви, полуинтервал

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

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

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

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

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

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

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

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

А = [ 0, 0.125), В = [ 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

Другою буквою буде В, так як новий дріб лежить в інтервалі [ 0.125, 0.25).

Перерахунок дає:

(0.2 - 0.125) / 0.125 = 0.6.

Це означає, що 3-я буква є D, і початковий текст при відсутності інформації про

його довжину, буде рядком, що повторюється DBDBDB. ..

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

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

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

Ефективність стиснення методом статичного арифметичного кодування буде рівна

Н, тільки при використанні арифметики необмеженої точності. Але і

обмеженій точності більшості машин досить, щоб дозволяти здійснювати

дуже хороше стиснення. Цілого змінного довжиною 16 бітів, 32-бітових творів

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

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

оптимального адаптованого коду Хаффмана, запропонованого Уїтером.

Як і у разі кодів Хаффмана, статичні арифметичні коди вимагають двох

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

коди вимагають ефективного алгоритму для підтримки і зміни інформації про

частоти, що біжить що і накопичується по мірі обробки букв. НайПростіший шлях для

цього - завести лічильник для кожної букви, що збільшує своє значення на одиницю

всякий раз, коли зустрілася сама ця буква або будь-яка з наступних після неї в

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

числом її появлений і числом появлений її попередників. Цей простий підхід

може зажадати Про(n) операцій над буквою n-арного алфавіта. У реалізованому на

Ці Уїттеном, Нейлом і Клірі алгоритмі стиснення арифметичних даних, середнє

значення було поліпшене за допомогою використання дисципліни move-to-front, що

скоротило кількість лічильників, значення яких измененяются кожний раз, коли

обробляється буква.

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

корінного відходу від простих СД. Вимоги, яким повинна відповідати ця СД краще

вивчити, якщо виразити її через абстрактний тип даних з наступними п'ятьма

операціями: initialize, update, findletter, findrange і maxrange. Операція

ініціалізації встановлює частоту всіх букв в 1, і будь-яке не рівне нулю

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

раскодирования використовують однакові початкові частоти. Початкове значення

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

т.ч. попереджаючи його від передачі або отримання.

Операція update(із) збільшує частоту букви з. Функції findletter і findrange

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

поки зберігається цей зворотний зв'язок. У будь-який момент часу findletter (, з,

min, max) буде повертати букву з і пов'язаний з нею частотний

інтервал [, що накопичується min, max), де f [ min, max). Зворотна функція findrange(, min,

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

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

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

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

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

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

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

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

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

дерево для 4-х-буквеного алфавіта (А, В, З, 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. Якщо окремий вузол дерева i пов'язаний

з інтервалом [, b), де а - b = freq[i], то інтервалами, пов'язаними з двома

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

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

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

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

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

var

i: downindex;

t: integer;

begin

а: = 0;

i: = root;

b: = freq[root];

repeat

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

if f i: = left[i];

b: = t;

end else begin { поворот направо }

i: = right[i];

а: = t;

end;

until i > maxchar;

з: = i - succmax;

end { findsymbol };

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

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

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

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

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

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

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

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

d = freq[up[i]] - freq[i], або, що одне і те ж: d = freq[left[up[i]]].

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

var

i: downindex;

d: integer;

begin

а: = 0;

i: = з + succmax;

b: = freq[i];

repeat

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

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

а: = а + d;

b: = b + d;

end;

i: = up[i];

until i = root;

end { findrange };

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

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

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

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

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

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

варіант О(n), що досягається за допомогою застосування лінійної СД ( організацією

move-to-front або без неї), але може бути поліпшено ще.

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

процедури findrange, за яким слідує виклик update. Т.ч. шлях від кореня до букви

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

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

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

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

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

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

факт, що кожний маршрут проходжується двічі.

Немає значення у використанні дерева частот, що накопичуються, якщо всі імовірності

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

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

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

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

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

алгоритм префікса, що розширяється, що дає обмеження Про(Н (S)) для довжини шляху,

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

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

алгоритму префікса, що розширяється.

Відповідно до цього алгоритму операції розширення не треба зачіпати

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

операції update, кожна операція полувращения повинна оберігати инвариацию

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

маючи результатом те, що вага Х скорочується вагою А і нарощується вагою С. В той

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

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

procedure update(з: codetype);

var

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

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

begin

а: = з + succmax;

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

з: = up[a];

if з # root then begin { пара },

що залишилася d: = up[з];

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

b: = left[d];

if з = b then begin b: = right[d];

right[d]: = a;

end else left[d]: = a;

if а = left[з] then left[з]: = b

else right[з]: = b;

up[a]: = d;

up[b]: = з;

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

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

а: = d;

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

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

а: = up[a];

end;

until а = root;

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

end { update };

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

procedure rescale;

var

u: upindex;

d: downindex;

begin

for d: = succmax to twicemax do

freq[d]: = (freq[d] + 1) div 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 };

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

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

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

стислими текстами, отриманими внаслідок робіт первинного і

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

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

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

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

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

інші являють собою:

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

біт/байт);

текстовой файл (4.91 біт/байт початкового тексту);

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

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

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

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

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

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

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

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

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

підходом.

Висновок.

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

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

префікса. Його характерні риси - дуже невелика кількість необхідної ОП і

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

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

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

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

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

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

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

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

використовується Зива-Лемпела на порівнянному об'ємі пам'яті.

Алгоритми арифметичного стиснення даних можуть виконуватися за час Про(Н) при

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

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

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

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

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

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

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

повороту, що передує розширення дерева, може знайти застосування і в

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

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

двійкового дерева з 2-я шляхами злиття для побудови n-шляхового злиття.

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

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

розв'язання проблеми відновлення цієї втрати представляє безперечний інтерес,

що крім того передбачає можливість використання таких схем стиснення в

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

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

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

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

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

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

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

ускладнити роботу зломщика кодів тим, що межі букв не обов'язково знаходяться

також і між бітами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка