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

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

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

Другий підхід – використовувати  так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати  схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане  кодування в явному вигляді. Замість  цього декодер, зчитуючи кодований  потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування  забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни  частот. Прикладом є динамічне  кодування Хаффмена.

 

1.3. Кодування Хаффмена

При використанні адаптивного  кодування Хаффмена необхідно постійно коректувати дерево у відповідності  до статистики вхідного потоку, яка  весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати  на балансування кодового дерева відповідно до нових частот символів на кожному  кроці. 
Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).

Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком  в алфавіті {0,1}.

Недоліком кодування Хаффмена є залежність коефіцієнту стискання  від близькості ймовірностей символів до від’ємних ступенів 2; це пов’язано  з тим, що кожен символ кодується  цілою кількістю біт. Найбільш помітно  це під час кодування двосимвольного алфавіту: в цьому випадку стискання  неможливе, незважаючи на відмінності  ймовірностей символів; алгоритм фактично “округляє” їх до 1/2!

1.4. Дворівневе кодування. Алгоритм Лемпеля-Зіва

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

В найпростішому випадку  можна використовувати в якості вхідного алфавіту саме ці символи (байти) вхідного потоку. Саме так працює метод squashing програми РКРАК (використане статичне кодування Хаффмена, двопрохідний алгоритм). Ступінь стискання при цьому  відносно невеликий – близько 50% для текстових файлів.

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

Цей метод належить Лемпелю  та Зіву і називається LZ77-compression (за роком публікації). Він полягає  в наступному: компресор постійно зберігає певну кількість останніх оброблених символів у деякому буфері (який також називається ковзаючим  словником – sliding dictionary). Назва “ковзаючий”  зумовлена тим, що його довжина постійна: кожного разу, коли компресор кодує  наступний ланцюжок, він дописує  її в кінець словника та “відрізає” відповідну кількість символів на початку  буфера. Під час обробки вхідного потоку символи, що надійшли, потрапляють у кінець буфера, зсуваючи попередні символи та витісняючи найстаріші.

Розміри цього буфера є  різними в різних реалізаціях. Очевидно, що використання буфера більших розмірів дозволяє отримати якісніший результат. Алгоритм виділяє (шляхом пошуку в словнику) найдовший початковий підрядок вхідного потоку, що співпадає з одним із підрядків у словнику, і подає  на вихід пару (length, distance), де length –  довжина знайденого у словнику підрядка, а distance – відстань від нього до вхідного підрядка (тобто фактично індекс підрядка в буфері, віднятий від його розміру). В разі, коли такого підрядка не знайдено, до вихідного  потоку просто копіюється черговий символ вхідного потоку.

1.5. Сімейство алгоритмів LZ78 (LZW, MW, AP, Y)

Не можна не відзначити широко відмий алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch compression, LZW, LZ78). Алгоритм відрізняється  високою швидкістю роботи при  кодуванні та декодуванні, невибагливістю до пам’яті та проста апаратна реалізація. Недолік – менший коефіцієнт компресії  порівняно зі схемою двоступеневого кодування. Наведемо принципи роботи цього  алгоритму. 
Створимо словник, що зберігає рядки тексту і містить близько 2-3-8 тисяч пронумерованих комірок. Запишемо до перших 256 комірок рядки, що складаються з одного символу, номер якого дорівнює номеру комірки. Алгоритм проглядає вхідний потік, розбиваючи його на підрядки і додаючи нові комірки в кінець словника. Будемо зчитувати із вхідного потоку по одному символу, кожного разу перевіряючи, чи є вже зчитаний ланцюжок у словнику. Таким чином ми отримаємо рядок S – найдовший префікс вхідного тексту (якщо його розглядати як рядок In), який вже є у словнику. Нехай його знайдено в комірці з номером n. Виведемо число n у вихідний потік, змістимо вказівник вхідного потоку на length(S) символів наперед та додамо до словника нову комірку, що містить рядок Sc, де с – черговий символ на вході (відразу після S). За побудовою ланцюжка S ланцюжка Sc у словнику немає. Алгоритм перетворює потік символів на вході на потік індексів комірок словника на виході. При розмірі словника в 4096 комірок можна передавати 12 біт на індекс кожного ланцюжка, що знайдено.

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

Далі, кодер використовує дві операції зі словником: пошук  рядка Sc, за умови, що рядок S є в словнику (та відома його позиція в ньому), а с – це наступний прочитаний символ, та додавання нової комірки, що містить цей рядок. Внаслідок  цього можна обійтися структурою даних, що називається trie – деревом  послідовного політерного пошуку.

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

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

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

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

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

При арифметичному стисненні повідомлень  алфавіту джерела ставиться у  відповідність числовий, відкритий  справа, інтервал [0,1), а кожен символ алфавіту зіставляється з різними  ділянками цієї числової осі. Ширина інтервалу (діапазон) кожної ділянки залежить від імовірності (частоти) появи символу в повідомленні.

Розглянемо, як приклад, алфавіт, що складається  із шести символів A, B, С, D, E, ! з імовірностями  появи відповідно 0,1; 0,1; 0,3; 0,2; 0,2 та 0,1. Тоді інтервал [0,1) може бути розділений на ділянки таким чином:

A: [0, 0,1), B: [0,1, 0,2), С: [0,2, 0,5),

D: [0,5, 0,7), E: [0,7, 0,9), !: [0,9, 1,0).

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

Рис. 1.1 Розподіл відрізків числової осі між символами при арифметичному кодуванні

 

2. Аналіз завдання та способи його вирішення
1. Аналіз завдання

Метою даної курсової роботи є написання програми, яка  виконує кодування інформації методом  «Арифметичне кодування». Для її успішного  написання потрібно, щоб виконувались ряд вимог:

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

Також, необхідно  реалізувати такі функції:

1. визначення розміру вхідного та вихідного файлу;
2. аналіз вхідного файлу;
3. побітове кодування/декодування вхідних файлів;
4. створення вихідного файлу та запис у нього кодованої/декодованої інформації.
2. Блок-схема алгоритму кодування

Блок-схему алгоритму стискання файлів за допомогою алгоритму «Арифметичне кодування» приведено на Рис. 2.1

 

 

Рис. 2.1 Блок-схема алгоритму стискання інформації

 

 

 

 

 

 

 

 

 

 

 

 

 

Ні

 

 

Так

Так

 

 

 

 

 

 

 

 

 

 

Рис. 2.1 «продовження»

 

Опис блок-схеми алгоритму

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

3. Блок-схема алгоритму декодування

Блок-схема алгоритму декодування файлів за алгоритмом «Арифметичне кодування» наведена на Рис. 2.2

 

 

 

 

 

 

 

 

 

Рис. 2.2 Блок-схема алгоритму  декодування стиснутого файлу

 

 

 

 

 

 

 

 

 

Ні

 

Так

 

 

 

 

 

 

 

 

 

Рис. 2.2 «продовження»

 

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

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