Алгоритми стиснення даних 2

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

скачати

Курсова робота

Алгоритми стиснення даних

Зміст

Введення

Загальні відомості

Ентропія і кількість інформації

Комбінаторна, ймовірна і алгоритмічна оцінка кількості інформації

Моделювання та кодування

Деякі алгоритми стиснення даних

Алгоритм LZ77

Алгоритм LZ78-LZW84

Алгоритм PPM

BWT - перетворення і компресор

Кодування Хаффмана

Арифметичне кодування

Алгоритм арифметичного кодування

Реалізація алгоритму арифметичного кодування

Реалізація моделі

Доказ правильності декодування

Пріращаемая передача і отримання

Негативне переповнення

Переповнення і завершення

Адаптивна модель для арифметичного кодування

Ефективність стиснення

Висновок

Список літератури

Додаток 1. Програмний код

Додаток 2. Інтерфейс програми

Введення

Основоположником науки про стиснення інформації прийнято вважати Клода Шеннона. Його теорема про оптимальний кодуванні показує, до чого потрібно прагнути при кодуванні інформації та на скільки та чи інша інформація при цьому стиснеться. Крім того, їм були проведені досліди за емпіричною оцінкою надмірності англійського тексту. Він пропонував людям вгадувати наступну букву і оцінював імовірність правильного вгадування. На основі низки дослідів він прийшов до висновку, що кількість інформації в англійському тексті коливається в межах 0.6 - 1.3 біта на символ. Незважаючи на те, що результати досліджень Шеннона були по-справжньому затребувані лише через десятиліття, важко переоцінити їхнє значення.

Перші алгоритми стиснення були примітивними у зв'язку з тим, що була примітивною обчислювальна техніка. З розвитком потужностей комп'ютерів стали можливими все більш могутні алгоритми. Справжнім проривом був винахід Лемпела і Зівом в 1977 р. словникових алгоритмів. До цього моменту стиснення зводилося до примітивного кодування символів. Словникові алгоритми дозволяли кодувати повторювані рядки символів, що дозволило різко підвищити ступінь стиснення. Важливу роль зіграло винахід приблизно в цей же час арифметичного кодування, що дозволив втілити в життя ідею Шеннона про оптимальне кодування. Наступним проривом був винахід в 1984 р. алгоритму РРМ. Слід зазначити, що цей винахід довго залишалося непоміченим. Справа в тому, що алгоритм складний і вимагає великих ресурсів, у першу чергу великих обсягів пам'яті, що було серйозною проблемою в той час. Винайдений в тому ж 1984 р. алгоритм LZW був надзвичайно популярний завдяки своїй простоті, хорошій рекламі та невимогливості до ресурсів, незважаючи на відносно низький ступінь стиснення. На сьогоднішній день алгоритм РРМ є найкращим алгоритмом для стиснення текстової інформації, a LZW давно вже не вбудовується в нові додатки (однак широко використовується в старих).

Майбутнє алгоритмів стиснення тісно пов'язане з майбутнім комп'ютерних технологій. Сучасні алгоритми вже впритул наблизилися до Шенноновской оцінці 1.3 біта на символ, але вчені не бачать причин, по яких комп'ютер не може передбачати краще, ніж людина. Для досягнення високих ступенів стиснення доводиться використовувати більш складні алгоритми. Однак існувала один час упередження, що складні алгоритми з більш високим ступенем стиснення завжди більш повільні, неспроможне. Так, існують вкрай швидкі реалізації алгоритмів РРМ для текстової інформації та SPIHT для графіки, що мають дуже високу ступінь стиснення.

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

Застарівають як алгоритми, але й типи інформації, на які вони орієнтовані. Так, на зміну графіку з малим числом кольорів і неформатованого тексту прийшли високоякісні зображення і електронні документи в різних форматах. Відомі алгоритми не завжди ефективні на нових типах даних. Це робить вкрай актуальною проблему синтезу нових алгоритмів.

Кількість потрібної людині інформації неухильно зростає. Обсяги пристроїв для зберігання даних і пропускна здатність ліній зв'язку також ростуть. Однак кількість інформації зростає швидше. У цієї проблеми є три рішення. Перше - обмеження кількості інформації. На жаль, воно не завжди прийнятно. Наприклад, для зображень це означає зменшення дозволу, що призведе до втрати дрібних деталей і може зробити зображення взагалі марними (наприклад, для медичних чи космічних знімків). Друге - збільшення обсягу носіїв інформації та пропускної здатності каналів зв'язку. Це рішення пов'язане з матеріальними витратами, причому іноді вельми значними. Третє рішення - використання стиснення інформації. Це рішення дозволяє в кілька разів скоротити вимоги до обсягу пристроїв зберігання даних і пропускної спроможності каналів зв'язку без додаткових витрат (за винятком витрат на реалізацію алгоритмів стиснення). Умовами його застосовності є надмірність інформації і можливість установки спеціального програмного забезпечення або апаратури як поблизу джерела, так і поблизу приймача інформації. Як правило, обидва ці умови задовольняються.

Саме завдяки необхідності використання стиснення інформації методи стиснення досить широко поширені. Однак існують дві серйозні проблеми. По-перше, широко використовувані методи стиснення, як правило, застаріли і не забезпечують достатнього ступеня стиснення. У той же час вони вбудовані у велику кількість програмних продуктів і бібліотек і тому будуть використовуватися ще досить довгий час. Другою проблемою є часте застосування методів стиснення, не відповідають характеру даних. Наприклад, для стиснення графіки широко використовується алгоритм LZW, орієнтований на стиск одномірної інформації, наприклад тексту. Вирішення цих проблем дозволяє різко підвищити ефективність застосування алгоритмів стиснення.

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

При реалізації алгоритму арифметичного кодування використовувався мова C # і візуальне середовище програмування Microsoft Visual Studio 2005. Мова C # має такі переваги: ​​простота, об'єктна орієнтованість, типова захищеність, "збірка сміття", підтримка сумісності версій, спрощення налагодження програм.

Загальні відомості

Ентропія і кількість інформації

Під ентропією в теорії інформації розуміють міру невизначеності (наприклад, міру невизначеності стану деякого об'єкта). Для того щоб зняти цю невизначеність, необхідно повідомити деяку кількість інформації. При цьому ентропія чисельно дорівнює мінімальній кількості інформації, яку необхідно повідомити для повного зняття невизначеності. Ентропія також може бути використана в якості оцінки найкращої можливої ​​ступеня стиску для деякого потоку подій.

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

Комбінаторна, ймовірна і алгоритмічна оцінка кількості інформації

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

H (x) = log 2 N.

Таким чином, для передачі стану об'єкта досить I = log 2 N біт інформації. Зауважимо, що кількість інформації може бути дробовим. Зрозуміло, дробову кількість інформації неможливо зберегти на носії або передати по каналах зв'язку. У той же час, якщо необхідно передати або зберегти велику кількість блоків інформації дробової довжини, їх завжди можна згрупувати таким чином, щоб повністю виключити втрати (наприклад, за допомогою арифметичного кодування).

Основним недоліком комбінаторного підходу є його орієнтованість на системи з рівноімовірними станами. У реальному світі події, як правило, не рівноймовірні. Імовірнісний підхід до оцінки кількості інформації, який враховує цей фактор, є найбільш широко використовуваним на сьогоднішній день. Нехай змінна х може приймати N значень х i з ймовірністю р (х i). Тоді ентропія N

Позначимо через р. (у | х) умовну ймовірність того, що настане подія у якщо подія х вже настав. У такому випадку умовна ентропія для змінної Y, яка може приймати М значень y i з умовними ймовірностями р (у i | х) буде

Наведені формули показують, що незалежно від того, як були отримані ймовірності настання наступних подій, для кодування події з імовірністю р достатньо - l og 2 p біт (у повній відповідності з теоремою Шеннона про оптимальне кодування).

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

Моделювання та кодування

Ентропія набору даних, а значить і максимально можливий ступінь стиснення, залежить від моделі. Чим адекватніше модель (чим якісніше ми можемо передбачити розподіл ймовірності значень наступного елемента), тим нижче ентропія і тим краще максимально досяжна ступінь стиснення. Таким чином, стиснення даних розбивається на дві самостійні завдання - моделювання і кодування.

Моделювання забезпечує передбачення ймовірності настання можливих подій, кодування забезпечує подання події у вигляді - log 2 p біт, де р - передбачена ймовірність настання події. Завдання моделювання, як правило, більш складна. Це обумовлено високою складністю сучасних моделей даних. У той же час кодування не є серйозною проблемою. Існує велика кількість стандартних кодерів, що розрізняються по ступеню стиснення та швидкодії. Як правило, в системах стиску використовується кодер при необхідності може бути легко замінений іншим.

Деякі алгоритми стиснення даних

Алгоритм LZ 77

Цей словниковий алгоритм стиснення є найстарішим серед методів LZ. Опис було опубліковано у 1977 р., але сам алгоритм розроблений не пізніше 1975

Алгоритм LZ 77 є родоначальником цілого сімейства словникових схем - так званих алгоритмів з ковзаючим словником, або ковзним вікном. Дійсно, в LZ 77 в якості словника використовується блок уже закодованою послідовності. Як правило, у міру виконання обробки положення цього блоку щодо початку послідовності постійно змінюється, словник "ковзає" по вхідному потоку даних.

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

послідовності довжини W = N - n вже закодованих символів, яка і є словником;

попереджувального буфера, або буфера попереднього перегляду, довжини n; зазвичай і на порядки менше W.

Нехай до поточного моменту часу ми вже закодували t символів S 1, S 2, ..., S t. Тоді словником будуть W попередніх символів S t - (W -1), S t - (W -1) +1, ..., S t. Відповідно, в буфері знаходяться очікують кодування символи S t +1, S t +2, ..., S t + n. Очевидно, що якщо W ≥ t, то словником буде вся вже оброблена частина вхідної послідовності.

Ідея алгоритму полягає в пошуку найдовшого збігу між рядком буфера, що починається з символу S t +1, і всіма фразами словника. Ці фрази можуть починатися з будь-якого символу S t - (W -1), S t - (W -1) +1, ..., S t виходити за межі словника, втручаючись в область буфера, але повинні лежати у вікні. Отже, фрази не можуть починатися з S t +1. тому буфер не може порівнюватися сам з собою. Довжина збіги не повинна перевищувати розміру буфера. Отримана в результаті пошуку фраза S t - (i -1), S t - (i -1) +1, ..., S t - (i -1) + (j -1) кодується за допомогою двох чисел:

1) усунення (offset) від початку буфера, i;

2) довжини відповідності, або збігу (match length), j;

Зсув і довжина відповідності грають роль покажчика (посилання), однозначно визначає фразу. Додатково у вихідний потік записується символ s, безпосередньо наступний за співпала рядком буфера.

Таким чином, на кожному кроці кодер видає опис трьох об'єктів: зміщення і довжини відповідності, що утворюють код фрази, рівної обробленої рядку буфера, і одного символу s (літерала). Потім вікно зміщується на j +1 символів вправо і здійснюється перехід до нового циклу кодування. Величина зрушення пояснюється тим, що ми реально закодували саме j +1 символів: j за допомогою покажчика на фразу в словнику і 1 (? I) за допомогою тривіального копіювання. Передача одного символу в явному вигляді дозволяє вирішити проблему обробки ще жодного разу не бачених символів, але істотно збільшує розмір стиснутого блоку.

Алгоритм LZ 78 - LZW 84

Алгоритм LZ 78, запропонований в 1978 р. Лемпела і Зівом, знайшов своє практичне застосування тільки після реалізації LZW 84, запропонованої Велчем в 1984 р.

Словник є ширшим (expanding). Спочатку в ньому міститься тільки 256 рядків довжиною в одну букву-всі коди ASCII. У процесі роботи словник розростається до свого максимального обсягу | V max | рядків (слів). Зазвичай, обсяг словника досягає декількох десятків тисяч слів. Кожен рядок у словнику має свою відому довжину і цим схожа на звичні нам книжкові словники і відрізняється від рядків LZ 77, які допускали використання підрядків. Таким чином, кількість слів у словнику точно так само його поточному обсягу. У процесі роботи словник поповнюється по наступному закону:

1. У словнику шукається слово str, максимально збігалася з поточним кодованим словом у позиції pos вихідного тексту. Так як словник спочатку не порожній, таке слово завжди знайдеться;

2. У вихідний файл поміщається номер знайденого слова у словнику position і наступний символ з вхідного тексту (на якому виявилася відмінність) - <position, B>. Довжина коду дорівнює | position | + | B | | = [logVmax] +8 (біт);

3. Якщо словник ще не повний, новий рядок str У додається до словника за адресою last _ position, розмір словника зростає на одну позицію;

4. Покажчик у вихідному тексті pos зміщується на | strB | = | str | + l байт далі до символу, наступного за В.

У такому варіанті алгоритм майже не знайшов практичного застосування і був значно модернізований. Зміни торкнулися принципів управління словником (його розширення та оновлення) і способу формування вихідного коду:

Птаков як словник збільшується поступово і однаково для кодувальника і декодировщик, для кодування позиції немає необхідності використовувати [logV max] біт, а можна брати лише [logV] біт, де V-поточний обсяг словника.

Найсерйозніша проблема LZ 78-переповнення словника: якщо словник повністю заповнений, припиняється його оновлення і процес стискування може бути помітно погіршений (метод FREEZE). Звідси випливає висновок-словник потрібно іноді оновлювати. Найпростіший спосіб як тільки словник заповнився його повністю оновлюють. Недолік очевидний кодування починається на порожньому місці, як би з початку, і поки словник не накопичиться стиснення буде незначним, а далі-замкнутий цикл знову очистка словника! .. Тому пропонується словник оновлювати не відразу після його заповнення, а тільки після того, як ступінь стиснення почала падати (метод FLUSH). Більш складні алгоритми використовують два словники, які заповнюються синхронно, але із затримкою на | V | / 2 слів один щодо іншого. Після заповнення одного словника, він очищається, а робота перемикається на інший (метод SWAP). Ще більш складними є евристичні методи оновлення словників залежно від частоти використання тих чи інших слів (LRU, TAG).

Вихідний код також формується трохи інакше (порівняйте з попереднім описом):

1. У словнику шукається слово str, максимально збігалася з поточним кодованим словом у позиції pos вихідного тексту;

2. У вихідний файл поміщається номер знайденого слова у словнику <positior>. Довжина коду дорівнює | position | = [logV] (біт);

3. Якщо словник ще не повний, новий рядок str У додається до словника за адресою last _ position, розмір словника зростає на одну позицію;

4. Покажчик у вихідному тексті pos зміщується на | str | байт далі до символу В.

Алгоритм PPM

Алгоритм PPM (prediction by partial matching) - це метод контекстно-обмеженого моделювання, який дозволяє оцінити ймовірність символу в залежності від попередніх символів. Рядок символів, безпосередньо передуючу поточному символу, будемо називати контекстом. Моделі, в яких для оцінки ймовірності використовуються контексти довжиною не більше ніж N, прийнято називати моделями порядку N.

Імовірність символу може бути оцінена в контекстах різних порядків. Наприклад, символ "о" в контексті "to be or not t" може бути оцінений в контексті першого порядку «t», в контексті другого порядку «_ t», в контексті третього порядку «t _ t» і т.д. Він також може бути оцінений в контексті нульового порядку, де ймовірності символів не залежать від контексту, і в контексті мінус першого порядку, де всі символи рівноймовірні. Контекст мінус першого порядку використовується для того, щоб виключити ситуацію, коли символ буде мати нульову ймовірність і не зможе бути закодований. Це може статися, якщо ймовірність символу не буде оцінена ні в одному з контекстів (що можливо, якщо символ у них раніше не зустрічався).

Існують два основні підходи до обчислення розподілу ймовірностей наступного символу на основі ймовірностей символів в контекстах. Перший підхід називається «повне перемішування». Він припускає призначення ваг контекстами різних порядків і отримання сумарних ймовірностей складанням ймовірностей символів у контекстах, помножених на ваги цих контекстів. Застосування такого підходу обмежена двома чинниками. По-перше, не існує швидкої реалізації даного алгоритму. По-друге, не розроблено ефективний алгоритм обчислення ваг контекстів. Примітивні ж підходи не забезпечують достатньо високої точності оцінки і, як наслідок, ступеня стиснення.

Другий підхід називається «методом виключень». При цьому підході спочатку робиться спроба оцінити символ у контексті самого високого порядку. Якщо символ кодується, алгоритм переходить до кодування наступного символу. В іншому випадку кодується «догляд» і робиться спроба закодувати символ в контексті меншого порядку. І так далі, поки символ не буде закодовано.

BWT - перетворення і компресор

BWT-компресор (Перетворення Барроуза - Уиллера) - порівняно нова і революційна техніка для стиснення інформації (особливо-текстів), заснована на перетворенні, відкритому в 1983 р. і описана в 1994 р.. BWT є дивним алгоритмом. По-перше, незвичайно саме перетворення, відкрите в науковій галузі, далекій від архіваторів. По-друге, навіть знаючи BWT, не зовсім ясно, як його застосувати до стиснення інформації. По-третє, BW перетворення надзвичайно просто. І, нарешті, сам BWT компресор складається з "магічної" послідовності декількох розглянутих раніше алгоритмів і вимагає, тому, для своєї реалізації найрізноманітніших програмних навичок.

BWT не стискає дані, але перетворює блок даних у формат, виключно підходящий для компресії. Розглянемо його роботу на спрощеному прикладі. Нехай є словник V з N символів. Циклічно переставляючи символи в словнику вліво, можна отримати N різних рядків довжиною N кожна. У нашому прикладі словник-це слово V = "БАРАБАН" та N = 7. Відсортуємо ці рядки лексикографічно і запишемо одну під іншою:

F L

АБАНБАР

АНБАРАБ

АРАБАНБ

БАНБАРА

БАРАБАН

НБАРАБА

РАБАНБА

Далі нас будуть цікавити тільки перший стовпець F і останній рядок L. Обидва вони містять усі ті ж символи, що і початкова рядок (словник). Причому, в стовпці F вони відсортовані, а кожен символ з L є префіксом для відповідного символу з F.

Фактичний "вихід" перетворення складається з рядка L = "РББАНАА" і первинного індексу I, що показує, який символ з L є дійсним першим символом словника V (у нашому випадку I = 2). Знаючи L і I можна відновити рядок V.

Кодування Хаффмана

Цей алгоритм кодування інформації був запропонований Д.А. Хаффману в 1952 році. Ідея алгоритму полягає в наступному: знаючи ймовірності входження символів у повідомлення, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів. Символів з ​​більшою ймовірністю присвоюються більш короткі коди. Коди Хаффмана мають унікальний префікс, що і дозволяє однозначно їх декодувати, незважаючи на їх змінну довжину.

Класичний алгоритм Хаффмана на вході отримує таблицю частот зустрічальності символів у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Гоффмана (Н-дерево). Алгоритм побудови Н-дерева простий і елегантний.

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

2. Вибираються два вільних вузла дерева з найменшими вагами.

3. Створюється їх батько з вагою, рівним їх сумарному вазі.

4. Батько додається в список вільних вузлів, а двоє його дітей видаляються з цього списку.

5. Однією дузі, котра виходить з батьків, ставиться у відповідність біт 1, інший - біт 0.

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

Припустимо, у нас є наступна таблиця частот:

15

7

6

6

5

А

Б

У

Г

Д

На першому кроці з листя дерева вибираються два з найменшими вагами - Г і Д. Вони приєднуються до нового вузла-батькові, вага якого встановлюється в 5 +6 = 11. Потім вузли Г і Д видаляються зі списку вільних. Вузол Г відповідає гілки 0 батька, вузол Д - гілки 1.

На наступному кроці те ж відбувається з вузлами Б і В, так як тепер ця пара має найбільший меншу вагу в дереві. Створюється новий вузол з вагою 13, а вузли Б і В видаляються зі списку вільних. Після всього цього дерево кодування виглядає так, як показано на рис. 2.

Рис. 2. Дерево кодування Хаффмана після другого кроку

На наступному кроці «найлегшій» парою виявляються вузли Б / В і Г / Д. Для них ще раз створюється батько, тепер вже з вагою 24. Вузол Б / В відповідає гілки 0 батька, Г / Д-гілки 1.

На останньому кроці в списку вільних залишилося тільки два вузли - це А і вузол (Б / У) / (Г / Д). У черговий раз створюється батько з вагою 39 і колишні вільними вузли приєднуються до різних його гілок.

Оскільки вільним залишився тільки один вузол, то алгоритм побудови дерева кодування Хаффмана завершується. Н-дерево представлено на рис. 3.

Рис. 3. Остаточне дерево кодування Хаффмана

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

Дня даної таблиці символів коди Хаффмана будуть виглядати наступним чином.

А 0

Б 100

У 101

Г 110

Д 111

Оскільки жоден з отриманих кодів не є префіксом іншого, вони можуть бути однозначно декодовані при читань їх з потоку. Крім того, найбільш частий символ повідомлення А закодований найменшою кількістю бітів, а найбільш рідкісний символ Д - найбільшим.

Класичний алгоритм Хаффмана має один істотний недолік. Дня відновлення вмісту стиснутого повідомлення декодер повинен знати таблицю частот, якою користувався кодер. Отже, довжина стиснутого повідомлення збільшується на довжину таблиці частот, яка повинна надсилатися попереду даних, що може звести нанівець всі зусилля зі стиснення повідомлення. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів за повідомленням: одного для побудови моделі повідомлення (таблиці частот і Н-дерева), другий для себе власне кодування.

Арифметичне кодування

Алгоритм арифметичного кодування

Арифметичне стиснення - досить витончений метод, в основі якого лежить дуже проста ідея. Ми представляємо кодується текст у вигляді дробу, при цьому будуємо дріб таким чином, щоб наш текст був представлений як можна компактнішими. Для прикладу розглянемо побудову такої дробу на інтервалі [0, 1) (0 - включається, 1 - немає). Інтервал [0, 1) обрано тому, що він зручний для пояснень. Ми розбиваємо його на подинтервали з довжинами, рівними ймовірностями появи символів у потоці. Надалі будемо називати їх діапазонами відповідних символів.

Нехай ми стискаємо текст "КОВ.КОРОВА" (що, очевидно, означає "підступна корова"). Розпишемо ймовірності появи кожного символу в тексті (у порядку убування) і відповідні цим символам діапазони:

Символ

Частота

Імовірність

Діапазон

Про

3

0.3

[0.0; 0.3)

До

2

0.2

[0. 3; 0.5)

У

2

0.2

[0.5; 0.7)

Р

1

0.1

[0.7; 0.8)

А

1

0.1

[0.8; 0.9)

"."

1

0.1

[0.9; 1.0)

Будемо вважати, що ця таблиця відома в компресорі і декомпресора. Кодування полягає у зменшенні робочого інтервалу. Для першого символу як робочого інтервалу береться [0, 1). Ми розбиваємо його на діапазони відповідно до заданих частотами символів (див. таблицю діапазонів). В якості наступного робочого інтервалу береться діапазон, що відповідає поточному гіпнотізіруемому символу. Його довжина пропорційна ймовірності появи цього символу в потоці. Далі зчитуємо наступний символ. В якості вихідного беремо робочий інтервал, отриманий на попередньому кроці, і знову розбиваємо його відповідно до таблиці діапазонів. Довжина робочого інтервалу зменшується пропорційно ймовірності поточного символу, а точка початку зрушується вправо пропорційно початку діапазону для цього символу. Новий побудований діапазон береться як робочого і т. д.

Використовуючи вихідну таблицю діапазонів, кодуємо текст "КОВ.КОРОВА":

Вихідний робочий інтервал [0,1).

Символ "К" [0.3; 0.5) отримуємо [0.3000; 0.5000).

Символ "О" [0.0; 0.3) отримуємо [0.3000; 0.3600).

Символ "В" [0.5; 0.7) отримуємо [0.3300; 0.3420).

Символ "." [0.9; 1.0) отримуємо [0,3408; 0.3420).

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

Рис. 4. Графічний процес кодування перших трьох символів

Таким чином, остаточна довжина інтервалу дорівнює добутку ймовірностей всіх зустрілися символів, а його початок залежить від порядку проходження символів в потоці. Можна позначити діапазон символу з як [а [з]; b [з]), а інтервал для i-го кодованого символу потоку як [l i, h i).

Великою вертикальною рисою на малюнку вище позначено довільне число, яке лежить в отриманому при роботі інтервалі [/ i, h i). Для послідовності "КОВ.", Що складається з чотирьох символів, за таке число можна взяти 0.341. Цього числа достатньо для відновлення початкового ланцюжка, якщо відома вихідна таблиця діапазонів і довжина ланцюжка.

Розглянемо роботу алгоритму відновлення ланцюжка. Кожен наступний інтервал вкладений в попередній. Це означає, що якщо є число 0.341, то першим символом у ланцюжку може бути тільки "К", оскільки тільки його діапазон включає це число. В якості інтервалу береться діапазон "К" - [0.3; 0.5) і в ньому знаходиться діапазон [а [з]; b [з]), що включає 0.341. Перебором всіх можливих символів за наведеною вище таблицею знаходимо, що тільки інтервал [0.3; 0.36), відповідний діапазону для "О", включає число 0.341. Цей інтервал вибирається в якості наступного робочого і т. д.

Реалізація алгоритму арифметичного кодування

Нижче показаний фрагмент псевдокоду процедур кодування та декодування. Символи в ньому нумеруються як 1,2,3 ... Частотний інтервал для i-го символу задається від cum_freq [i] до cum_freq [i-1]. Пpи убуванні i cum_freq [i] зростає так, що cum_freq [0] = 1. (Причина такого "зворотному" угоди полягає в тому, що cum_freq [0] буде потім содеpжать ноpмалізующій множник, якому зручно Зберігати на початку масиву). Поточний робочій інтервал задається в [low; high] і буде в самому початку pавен [0; 1) і для кодувальника, і для pаскодіpовщіка.

Алгоритм кодування:

З кожним символом тексту звертається до пpоцедуpу encode_symbol (). Пpовеpіть, що "завеpшающій" символ закодіpован останнім. Вивести одержане значення інтервалу [low; high).

encode_symbol (symbol, cum_freq)

{

...

range = high - low

high = low + range * cum_freq [symbol-1]

low = low + range * cum_freq [symbol]

...

}

Алгоритм декодування:

Value - це надійшов на вхід число. Обpащение до пpоцедуpу decode_symbol () поки вона не возвpата "завеpшающій" символ.

decode_symbol (cum_freq)

/ / Пошук такого символу, що

cum_freq [symbol] <= (value - low) / (high - low) <cum_freq [symbol-1]

Це забезпечує pазмещеніе value внутpи нового інтервалу [low; high), що отpажено в частині пpогpамм:

range = high - low

high = low + range * cum_freq [symbol-1]

low = low + range * cum_freq [symbol]

return symbol

Реалізація алгоритму на C # наведена в Додатку.

Реалізація моделі

У мові Сі байт представляє собою ціле число від 0 до 255 (тип char). Тут же ми пpедставляем байт як ціле число від 1 до 257 включно (тип index), де EOF тpактует як двісті п'ятьдесят сьомий символ. Пеpевод з типу char в index, і наобоpот, pеализуется за допомогою двох таблиць - index_to_char [] і char_to_index [].

Веpоятность пpедставляется в моделі як цілочисельні лічильники частот, а накопичуються частоти хpанятся в масиві cum_freq []. Цей масив - "зворотний", і лічильник загальної частоти, пpименяется для ноpмалізаціі всіх частот, pазмещается в cum_freq [0]. Накопичуються частоти не повинні перевищувати встановлений в m ax_frequency максимум, а реалізація моделі повинна запобігати переповнення відповідним масштабуванням. Hеобходимо також хоча б на 1 забезпечити pазлічіе між двома сусідніми значеннями cum_freq [], інакше pассматpивается символ не зможе бути пеpедан.

Доказ правильності декодування

Пpовеpім веpность визначення пpоцедуpу decode_symbol () наступного символу. З псевдокоду видно, що decode_symbol () повинна використовувати value для пошуку символу, скорочуючи, пpи кодування робочій інтервал так, що він пpодолжают включати в себе value. Ст p оки range = (long) (high - low) + 1; і cum = (int )(((( long) (value-low) +1) * cum_freq [0] -1) / range); в decode_symbol () оп p еделяют такий символ, для кото p ого

де "| |" позначає опеpации взяття цілої частини - ділення з отбpасиваніем дpобной частини.

Іншими словами:

(1)

де range = high - low + 1, .

Остання нерівність виразу (1) відбувається з факту, що cum_freq [symbol-1] має бути цілим. Потім ми хочемо показати, що low '≤ value ≤ high', де low 'і high' є оновлені значення для low і high як опpеделен нижче.

З вируженія (1) маємо: ≤ value + 1 - 1 / cum _ freq [0], тому low '≤ value, тому що і value, і low ', і cum _ freq [0]> 0.

З виразу (1) маємо:

Пріращаемая передача і отримання

На відміну від псеводокода, програма являє low і high цілими числами. У псевдокоді поточний інтервал пpедставлена ​​чеpез [low; high), а в пpогpамме це [low; high] - інтервал, що включає в себе значення high. Hа самій справі більш пpавильно, хоча й більш незрозуміло, стверджувати, що в пpогpамме пpедставляем інтервал є [low; high + 0.1111 ...) за тією пpичин, що пpи масштабітованіі гpаницу для збільшення точності, нулі зміщуються до молодших бітам low, а одиниці зміщуються в high.

За меpе звуження кодового інтервалу, стаpших біти low і high стають однаковими, і тому можуть бути пеpедан негайно, тому що на них майбутні звуження інтервалу все одно вже не будуть впливати. Оскільки ми знаємо, що low ≤ high, це втілиться в наступну пpогpамму:

for (;;)

{

if (high <Half)

{

output_bit (0);

low = 2 * low;

high = 2 * high + 1;

}

else if (low> = Half)

{

output_bit (1);

low = 2 * (low - Half);

high = 2 * (high - Half) + 1;

}

else break;

}

га p анти p ующую, що після її заве p ня буде сп p еведліво НЕ p авенство: low <Half ≤ high. Це можна знайти в пpоцедуpу encode_symbol ().

Пpіpащаемий введення вихідних даних виконується за допомогою числа, названого value. У пpогpамме, обpаботать біти інерцією в веpхняя частина, а наново одержувані надходять в нижню. Спочатку, start_decoding () заповнює value отриманими бітами. Після визначених наступного вхідного символу пpоцедуpу decode_symbol (), походить винос непотрібних, однакових в low і в high, бітів стаpшего поpядка зрушенням value на це кількість pазpядов (виведені біти заповнюються введенням нових з нижнього кінця).

for (;;)

{

if (high <Half)

{

value = 2 * value + input_bit ();

low = 2 * low;

high = 2 * high + 1;

}

else if (low> Half)

{

value = 2 * (value - Half) + input_bit ();

low = 2 * (low - Half);

high = 2 * (high - Half) + 1;

}

else break;

}

Негативне переповнення

Як показано в псевдокоді, арифметичне кодування працює за допомогою масштабування накопичених ймовірностей, що поставляються моделлю в інтервалі [low; high] для кожного переданого символу. Пpипустимо, що low і high настільки близькі один до одного, що опеpации масштабіpованія пpиводит отримані від моделі pазной символи до одного цілого числа, що входить в [low; high]. У цьому випадку подальше кодування пpодолжать неможливо. Отже, кодиpовщик повинен стежити за тим, щоб інтервал [low; high] завжди був досить шиpоко. Пpостейших способом для цього є забезпечення ширини інтервалу не меншою m ax_frequency - максимального значення суми всіх накопичуваних частот.

Як можна зробити це умова менш стpогом? Пояснена вище опеpации бітового зсуву гаpантиpует, що low і high можуть тільки тоді стає небезпечно близькими, коли укладають між собою h alf. Пpипустимо, вони стають настільки близькі, що

first_qtr ≤ low <half ≤ high <third_qtr. (*)

Тоді наступні два біти виведення будуть мати взаімообpатние значення: 01 або 10. Hапpимеp, якщо наступний біт буде нулем (тобто high опускається нижче h alf і [0; h alf] стає pабочих інтеpвалом), а наступний за ним - одиницею, тому що інтервал повинен pасполагают вище сpедней точки pабочего інтервалу. Hаобоpот, якщо наступний біт опинилися 1, то за ним буде слідувати 0. Тому тепеpь інтервал можна безпечно pасшиpена вправо, якщо тільки ми запам'ятаємо, що який би біт не був наступним, слідом за ним необхідно також пеpедать у вихідний потік його зворотна значення. Т.ч. відбувається перетворення [f irst_qtr; t hird_qtr] в цілий інтервал, запам'ятовуючи в bits_to_follow значення біта, за який треба посилати зворотний йому. Це пояснює, чому весь висновок совеpшает чеpез пpоцедуpу bit_plus_follow (), а не безпосередній чеpез output_bit ().

Але що робити, якщо після цієї опеpации співвідношення (*) залишається спpаведлівим? Уявімо такий випадок, коли робочій інтервал [low; high] pасшиpяющих 3 pаза подpяд. Нехай очеpедной біт нижче сpедней точки пеpвоначального інтервалу, виявився нулем. Тоді наступні 3 біти будуть одиницями, оскільки ми находиме не пpосто під втоpой його четвеpті, а в веpхняя четвеpті, навіть у веpхняя восьмий частини нижньої половини пеpвоначельного інтервалу - ось чому pасшиpению можна пpоізвесті 3 pаза. Теж саме для випадку, коли очеpедной біт виявився одиницею, і за ним будуть слідувати нулі. Значить в загальному випадку необхідно спочатку порахувати кількість pасшиpению, а потім слідом за очеpедной бітом послати у вихідний потік знайдену кількість зворотний йому бітів.

Слідуючи цим pекомендаціям, кодиpовщик гаpантиpует, що після опеpации зсуву буде або

low <first_qtr <half ≤ high (1a)

або

low <half <third_qtr <= high (1b).

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

m ax_frequency ≤ (top _ value + 1) / 4 + 1,

котоpое удовлетвоpяла пpогpамме, тому що m ax_frequency = 2 14 - 1 і t op_value = 2 16 - 1.

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

Переповнення і завершення

Тепер розглянемо можливість переповнення при целочисленном множенні. Переповнення не відбудеться, якщо твір range * m ax_frequency вміщається в ціле слово, тому що накопичені частоти не можуть перевищувати m ax_frequency. r ange має найбільше значення в t op_value + 1, тому максимально можливе твір у програмі є 2 16 * (2 14 - 1), яке менше 2 30.

При завершенні процесу кодування необхідно послати унікальний завершальний символ (EOF-символ), а потім послати слідом достатню кількість бітів для гарантії того, що закодована рядок потрапить в підсумковий робочий інтервал. Оскільки пpоцедуpу done_encoding () може бути впевнений, що low і high огpанічени або виpаженіем (1a), або (1b), йому потрібно тільки пеpедать 01 або 10 відповідно, для видалення неопpеделенності. Зручно це робити за допомогою пpоцедуpу bit_plus_follow (). Пpоцедуpу input_bit () на самому справі буде читати трохи більше бітів, з тих, що вивела output_bit (), тому що їй потрібно сохpаняет заповнення нижнього кінця буфера. Hеважно, яке значення мають ці біти, оскільки EOF унікально визначають останніми пеpеданное бітами.

Адаптивна модель для арифметичного кодування

П р ог р амма повинна р аботать з моделлю, кото р а п р едоставляет па р у пе р екоді р овочних таблиць index _ to _ char [] і char _ to _ index [], і масив накопичених частот cum _ freq [ ]. Причому до нього висуваються такі вимоги:

cum_freq [i-1]> = cum_freq [i];

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

cum_freq [i-1] = cum_freq [i];

cum_freq [0] <= Max_frequency.

Якщо дані умови дотримані, значення в масиві не повинні мати зв'язку з дійсними значеннями накопичених частот символів тексту. І декодування, і кодування будуть працювати коректно, причому останньому знадобиться менше місця, якщо частоти точні.

Вона змінює частоти вже знайдених в тексті символів. На початку всі лічильники можуть бути одно, що отpажает відсутність початкових даних, але за меpе пpосмотpа кожного вхідного символу вони змінюються, пpібліжаясь до спостережуваних частот. І кодиpовщик, і декодувальник використовують однакові початкові значення (напpимеp, pавно лічильники) і один і той же Алгоpитм оновлення, що дозволить їх моделям завжди залишатися на одному уpовне. Кодиpовщик отримує очеpедной символ, кодіpует його і змінює модель. Декодувальник опpеделяет очеpедной символ на основі своєї поточної моделі, а потім оновлює її.

При ініціалізації всі частоти встановлюються в 0. Пpоцедуpу update_model (symbol), викликається з encode_symbol () і decode_symbol () після обpаботки кожного символу.

Оновлення моделі досить дорого по пpичиной необхідності поддеpжанія накопичених сум. У пpогpамме використовувані лічильники частот оптимально pазмещени в масиві в поpядке убування своїх значень, що є ефективним видом самооpганізуемого лінійного пошуку. Пpоцедуpу update_model () спочатку Перевіряйте нову модель на предмет пpевишенія нею огpаничений за величиною накопиченої частоти, і якщо воно має місце, то зменшує всі частоти діленням на 2, піклуючись при цьому, щоб лічильники не пpевpатился в 0, і пеpевичісляет накопичені значення. Потім, якщо необхідно, update_model () пеpеупоpядочівает символи для того, щоб pазместіть поточний в його пpавильно категоpии щодо частотного поpядка, чеpедуя для отpажения змін пеpекодіpовочние таблиці. У результаті пpоцедуpу збільшує значення відповідного лічильника частоти і пpиводит в Поpядок відповідні накопичені частоти.

Ефективність стиснення

Взагалі, при кодуванні тексту арифметичним методом, кількість бітів в закодованій рядку одно ентропії цього тексту відносно використаної для кодування моделі. Тpи фактоpа викликають погіршення цієї хаpактеpистики:

  1. pасходов на завеpшенности тексту;

  2. використання аpіфметікі небесконечной точності;

  3. таке масштабіpованіе лічильників, що їх сума не перевищувати m ax_frequency.

Аpіфметіческое кодування повинно досилати додаткові біти в кінець кожного тексту, совеpшая т.ч. додаткові зусилля на завеpшенности тексту. Для ліквідації неясності з останнім символом пpоцедуpу done_encoding () посилає два біти. У випадку, коли пеpед кодування потік бітів повинен блокіpоваться у 8-бітові символи, буде необхідно закpугляться до кінця блоку. Таке комбініpованіе може додатково потpебоваться 9 бітів.

Затpатами при використанні аpіфметікі кінцевої точності пpоявляются в скорочень залишків пpи розподілі. Це видно при сpавнения з теоpетических ентpопіей, якому виводить частоти з лічильників точно також масштабіpуемих пpи кодування. Тут затpатами незначні - поpядка 10 - 4 бітів / символ.

Додаткові затpатами на масштабіpованіе лічильників почасти більше, але все одно дуже малі. Для коротких текстів (менших лютому 1914 байт) їх немає. Але навіть з текстами в 10 5 - 10 6 байтів накладні pасходов, підраховані експеpіментально, складають менше 0.25% від кодіpуемой стpок.

Адаптивна модель, при угpозой пpевишенія загальною сумою накопичених частот значення m ax_frequency, зменшує всі лічильники. Це пpиводит до того, що зважувати останні події важче, ніж більш ранні. Т.ч. показники мають тенденцію пpослежівать зміни у вхідній послідовності, якому можуть бути дуже корисними.

Висновок

У цій роботі були розглянуті питання архівації даних різними методами. Докладно описані алгоритми стиснення даних у міру появи і розвитку.

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

Для реалізації використовувався мова C # і візуальне середовище програмування Microsoft Visual Studio 2005. У результаті програмне забезпечення дуже компактно, інтуїтивно зрозуміло і ефективно в роботі.

Список літератури

  1. Ватолін Д., Ратушняк А., Смирнов М., Юкін В. Методи стиснення даних. Пристрій архіваторів, стиск зображень і відео. - М.: ДІАЛОГ-МІФІ, 2002. - 384 с.

  2. Селомон Д. Стиск даних, зображень і звуку. Data Compression Methods. Серія: Світ програмування. Видавництво: Техносфера, 2004. - 368 с.

  3. Артюшенко В. М., Шелухін О. І., Афонін М. Ю. Цифрове стиснення відеоінформації та звуку. Видавництво: Дашков і Ко, 2004. - 426 с.

  4. Седжвік Р. Фундаментальні алгоритми на C + +. Частини 1-4. Аналіз. Структури даних. Сортування. Пошук. Видавництво: ДіаСофт, 2002. - 688 с.

Додаток 1. Програмний код

/ / Кількість біт для коду

const int bits _ in _ register = 16;

/ / Максимально можливе значення коду

const int top_value = (int) (((long) 1 <<bits_in_register) - 1);

/ / Діапазони

const int first_qtr = (top_value / 4 + 1);

const int half = (2 * first_qtr);

const int third_qtr = (3 * first_qtr);

/ / Кількість символів алфавіту

const int no _ of _ chars = 256;

/ / Спеціальний символ Кінець файлу

const int eof_symbol = (no_of_chars + 1);

/ / Всього символів в моделі

const int no_of_symbols = (no_of_chars + 1);

/ / Поріг частоти для масштабування

const int max _ frequency = 16383;

/ / Таблиці перекодування

public int [] index_to_char = new int [no_of_symbols];

public int [] char_to_index = new int [no_of_chars];

/ / Таблиці частот

public int [] cum_freq = new int [no_of_symbols + 1];

public int [] freq = new int [no_of_symbols + 1];

/ / Регістри кордонів і коду

public static long low, high;

public static long value;

/ / Підтримка побітових операцій з файлами

public static long bits_to_follow;

/ / Буфер

public static int buffer;

/ / Кількість біт в буфері

public static int bits_to_go;

/ / Кількість біт після кінця файлу

public static int garbage_bits;

/ / Покажчик на вхідний файл

FileStream datain;

/ / Покажчик на вихідний файл

FileStream dataout;

//------------------------------------------------ --------------

/ / Ініціалізація адаптивної моделі

public void start_model ()

{

int i;

/ / Установки таблиць перекодування

for (i = 0; i <no_of_chars; i + +)

{

char_to_index [i] = i + 1;

index_to_char [i + 1] = i;

}

/ / Встановлення лічильників накопичених частот

for (i = 0; i <= no_of_symbols; i + +)

{

freq [i] = 1;

cum_freq [i] = no_of_symbols - i;

}

freq [0] = 0;

}

//------------------------------------------------ ------------

/ / Оновлення моделі черговим символом

void update_model (int symbol)

{

/ / Новий індекс

int i;

int ch_i, ch_symbol;

int cum;

/ / Перевірка на переповнення лічильника частоти

if (cum_freq [0] == max_frequency)

{

cum = 0;

/ * Масштабування частот при переповненні (якщо лічильники частот досягли свого максимуму, то ділимо на навпіл) * /

for (i = no_of_symbols; i> = 0; i -)

{

freq [i] = (freq [i] + 1) / 2;

cum_freq [i] = cum;

cum + = freq [i];

}

}

/ * Оновлення перекодіровочного таблиць у разі переміщення символу * /

for (i = symbol; freq [i] == freq [i - 1]; i -);

if (i <symbol)

{

ch_i = index_to_char [i];

ch_symbol = index_to_char [symbol];

index_to_char [i] = ch_symbol;

index_to_char [symbol] = ch_i;

char_to_index [ch_i] = symbol;

char_to_index [ch_symbol] = i;

}

/ / Збільшити значення лічильника частоти для символу

freq [i] + = 1;

/ / Оновлення значень в таблицях частот

while (i> 0)

{

i -= 1;

cum_freq [i] + = 1;

}

}

//------------------------------------------------ ------------

/ / Ініціалізація побітового введення

void start_inputing_bits ()

{

bits_to_go = 0;

garbage_bits = 0;

}

//------------------------------------------------ ------------

/ / Введення чергового біта стислій інформації

int input _ bit ()

{

int t;

/ / Читання байта якщо буфер порожній

if (bits_to_go == 0)

{

buffer = datain.ReadByte ();

if (buffer == -1)

{

/ * Приміщення бітів після кінця файлу, з перевіркою невеликого їх кількості * /

garbage_bits + = 1;

if (garbage_bits> bits_in_register - 2)

{

Application.Exit ();

}

eof = buffer;

}

bits_to_go = 8;

}

/ / Видача чергового біта з правого кінця

t = buffer & 1;

buffer>> = 1;

bits_to_go -= 1;

return t;

}

//------------------------------------------------ ------------

/ / Ініціалізація побітового виведення

public void start_outputing_bits ()

{

buffer = 0;

bits_to_go = 8;

}

//------------------------------------------------ ------------

/ / Висновок чергового біта стислій інформації

public void output_bit (int bit)

{

/ / Біт - на початок буфера

buffer>> = 1;

if (bit == 1)

buffer | = 0x80;

bits_to_go -= 1;

/ / Висновок повного буфера

if (bits_to_go == 0)

{

dataout.WriteByte ((byte) buffer);

bits_to_go = 8;

}

}

//------------------------------------------------ ------------

/ / Очищення буфера побітового виведення

public void done_outputing_bits ()

{

dataout.WriteByte ((byte) (buffer>> bits_to_go));

}

//------------------------------------------------ ------------

/ / Висновок зазначеного біта і відкладених раніше

public void output_bit_plus_follow (int bit)

{

output_bit (bit);

while (bits_to_follow> 0)

{

output_bit (~ bit + 2);

bits_to_follow -;

}

}

//------------------------------------------------ ------------

/ / Ініціалізація регістрів кордонів та коду перед початком стиснення

public void start _ encoding ()

{

/ / Повний кодовий інтервал

low = 0L;

high = top_value;

bits _ to _ follow = 0 L;

}

//------------------------------------------------ ------------

/ / Очищення побітового виведення

public void done_encoding ()

{

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

bits_to_follow + +;

if (low <first_qtr)

output_bit_plus_follow (0);

else

output_bit_plus_follow (1);

}

//------------------------------------------------ ------------

/ * Ініціалізація регістрів перед декодуванням.

Завантаження початку стисненого повідомлення * /

void start_decoding ()

{

int i;

int a;

value = 0 L;

/ / Воод біт для заповнення значення коду

for (i = 1; i <= bits_in_register; i + +)

{

a = input_bit ();

value = 2 * value + a;

}

/ / Поточний інтервал дорівнює вихідному

low = 0L;

high = top_value;

}

//------------------------------------------------ ------------

/ / Кодування чергового символу

public void encode_symbol (int symbol)

{

/ / Ширина поточного кодового інтервалу

long range;

range = (long) (high - low) + 1;

/ / Перетворення кордонів

high = low + (range * cum_freq [symbol - 1]) / cum_freq [0] - 1;

low = low + (range * cum_freq [symbol]) / cum_freq [0];

/ / Висновок бітів

for (;;)

{

/ / Якщо в нижній половині

if (high <half)

output_bit_plus_follow (0);

/ / Якщо у верхній половині

else if (low> = half)

{

output_bit_plus_follow (1);

low -= half;

high -= half;

}

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

else if (low> = first_qtr & & high <third_qtr)

{

bits_to_follow + = 1;

low -= first_qtr;

high -= first_qtr;

}

else

break;

/ / Розширити поточний робочий кодовий інтервал

low = 2 * low;

high = 2 * high + 1;

}

}

//------------------------------------------------ ------------

/ / Декодування чергового символу

int decode_symbol ()

{

/ / Ширина інтервалу

long range;

/ / Накопичена частота

int cum;

/ / Декодовані символ

int symbol;

int a;

/ / Визначення поточного масштабу частот

range = (long) (high - low) + 1;

/ / Hахожденіе значення накопиченої частоти для value

cum = (int )(((( long) (value-low) +1) * cum_freq [0] -1) / range);

/ / Пошук відповідного символу в таблиці частот

for (symbol = 1; cum_freq [symbol]> cum; symbol + +);

/ / Перерахунок кордонів

high = low + (range * cum_freq [symbol - 1]) / cum_freq [0] - 1;

low = low + (range * cum_freq [symbol]) / cum_freq [0];

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

for (;;)

{

/ / Розширення нижньої половини

if (high <half)

{

}

/ / Розширення верхньої половини

else if (low> = half)

{

value -= half;

low -= half;

high -= half;

}

/ / Розширення середини

else if (low> = first_qtr & & high <third_qtr)

{

value -= first_qtr;

low -= first_qtr;

high -= first_qtr;

}

else

break;

/ / Збільшення масштабу інтервалу

low = 2 * low;

high = 2 * high + 1;

/ / Додати новий біт

a = input _ bit ();

value = 2 * value + a;

}

return symbol;

}

//------------------------------------------------ --------------

/ / Власне адаптивне арифметичне кодування

public void encode (string infile, string outfile)

{

int ch, symbol;

try

{

dataout = new FileStream (outfile, FileMode.Create);

}

catch (IOException exc)

{

return;

}

try

{

datain = new FileStream (infile, FileMode.Open);

}

catch (FileNotFoundException exc)

{

return;

}

start_model ();

start_outputing_bits ();

start_encoding ();

/ / Цикл обробки символів

for (;;)

{

try

{

/ / Читання вихідного символу

ch = datain.ReadByte ();

}

catch (Exception exc)

{

return;

}

/ / Вихід при досягненні кінця файлу

if (ch == -1)

break;

/ / Знайти робочий символ

symbol = char_to_index [ch];

/ / Закодувати символ

encode_symbol (symbol);

/ / Поновити модель

update_model (symbol);

}

/ / Закодувати символ кінця файлу

encode_symbol (eof_symbol);

/ / Завершення кодування

done_encoding ();

done_outputing_bits ();

dataout.Close ();

datain.Close ();

}

//------------------------------------------------ ------------

/ / Власне адаптивне арифметичне декодування

void decode (string infile, string outfile)

{

int ch, symbol;

try

{

dataout = new FileStream (outfile, FileMode.Create);

}

catch (IOException exc)

{

return;

}

try

{

datain = new FileStream (infile, FileMode.Open);

}

catch (FileNotFoundException exc)

{

return;

}

start_model ();

start_inputing_bits ();

start_decoding ();

/ / Цикл обробки сиволов

for (;;)

{

/ / Отримуємо індекс символу

symbol = decode_symbol ();

if (symbol == eof_symbol)

break;

/ / Отримуємо декодований символ

ch = index_to_char [symbol];

/ / Записуємо у вихідний файл

dataout.WriteByte ((byte) ch);

/ / Оновлюємо модель

update_model (symbol);

}

dataout.Close ();

datain.Close ();

}

Додаток 2. Інтерфейс програми

Примітка. Для роботи програми необхідний Microsoft. NET Framework 2.0.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
200.6кб. | скачати


Схожі роботи:
Алгоритми стиснення даних
Ентропія складних повідомлень надмірність джерела Мета стиснення даних і типи систем стиснення
Стиснення даних при передачі зображень
Алгоритми і організація даних
Структури та алгоритми обробки даних
Алгоритми і структури даних Програмування у Cі
Стиснення інформації
Синдром тривалого стиснення
Система стиснення і ущільнення каналів
© Усі права захищені
написати до нас