Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Арифметичне кодування-декодування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2007
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра Програмного забезпечення
Курсова робота
з дисципліни “ Методи та засоби комп’ютерних інформаційних технологій ”
на тему « Арифметичне кодування-декодування »
Львів 2007
АНОТАЦІЯ
В даній курсовій роботі розглянуто один із алгоритмів стиснення інформації, а саме алгоритм «Арифметичне кодування-декодування». Реалізовано програму, яка виконує його дії і показано її основні функції. Приведений огляд інших алгоритмів стиснення інформації і їх порівняння з даним.
ЗМІСТ
Вступ
1. Огляд методів стискання інформації
1.1 Загальні характеристики методів стискання інформації
1.2 Кодування Хаффмена
1.3 Дворівневе кодування. Алгоритм Лемпеля-Зіва
1.4 Сімейство алгоритмів LZ78 (LZW, MW, AP, Y)
1.5 Алгоритм арифметичного кодування
2. Формулювання поставленої задачі
Постановка задачі
Функціональні вимоги
3. Реалізація алгоритму арифметичного кодування - декодування
Загальний опис алгоритму арифметичного кодування – декодування
3.1.1 Фіксована модель
3.1.2 Адаптивна модель
3.1.3 Проблеми переповнення і завершення кодування
Реалізація арифметичного кодування
Попередній аналіз файлу
Кодування файлу
Додаткова обробка закодованого файлу
Реалізація арифметичного декодування
Додаткова обробка закодованого файлу
Декодування файлу
Збереження таблиці
Проектування інтерфейсу користувача
Ефективність стискання арифметичного кодування
Інструкція по використанню розробленої програми
Висновок
Список літератури
ВСТУП
Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом. Іншим прикладом кодування є писемність, яка виникла так давно, що точних даних про конкретний час її появи не існує і, мабуть, ніколи не буде знайдено.
В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціонованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі. Можна навести багато інших застосувань кодування інформації.
Арифметичне кодування є одним з перспективних методів стиску інформації, та, в деякому розумінні, її шифрування. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску, - ентропії вхідного потоку.
1. Огляд методів стискання інформації
1.1. Загальні характеристики методів стискання інформації
Методи стискання інформації мають досить довгу історію. Найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).
Недоліки методу RLE є очевидними: це, передусім, низька пристосованість до багатьох розповсюджених типів файлів, наприклад, текстових: у загальному випадку реально стиснути можна лише ланцюжки проміжків на початку абзаців. Саме тому цей метод можна ефективно використовувати лише у комбінації з вторинним кодуванням.
Вторинне кодування реалізовано в алгоритмі кодування факсів: спочатку зображення розбивається на чорні та білі крапки, що перетворюються алгоритмом RLE на потік довжин серій, а потім ці довжини серій кодуються за методом Хаффмена зі спеціально підібраним деревом.
Надалі будемо розглядати компресор (compressor) як програму, що перетворює масив символів деякого алфавіту в інший, бажано меншого за розміром. Часто роль цього масиву виконує безструктурний двійковий файл (подібний до файла MS-DOS або UNIX), а роль масиву символів вхідного алфавіту – 256 можливих значень байта (але не завжди). Відповідно, декомпресор (decompressor) – програма, що виконує зворотнє перетворення, до того ж виконує його однозначно. Таким чином, ми виключаємо з розгляду методи стискання, що втрачають інформацію (наприклад, метод стискання зображень JPEG, що базується на перетворенні кольорів, які практично неможливо розрізнити людським оком).
Найбільш цікавими є однопрохідні алгоритми, що стискають не просто файл прямого доступу, а потік – файл, що не дозволяє позиціонування та скролінгу (подібно до програмного каналу (pipe) в UNIX). Такі алгоритми мають більш широку сферу застосувань, зокрема вони зручніші для апаратної реалізації в складі інтелектуальних контролерів пристроїв. Наприклад, протокол v42bis, що застосовується в модемах – це реалізація модифікації алгоритму LZW.
Кодування має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потоку на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи.
Перший підхід: продивитися вхідний потік і побудувати кодування на основі зібраної статистики (це потребу двох проходів по файлу, що звужує сферу застосування таких алгоритмів). У вихідний потік в такому випадку має бути записано схему кодування, що застосовувалося. Цією схемою потім скористається декодер. Приклад – статистичне кодування Хаффмена.
Другий підхід – використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена.
1.2. Кодування Хаффмена
При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці. Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).
Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.
Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості ймовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності ймовірностей символів; алгоритм фактично “округляє” їх до 1/2!
1.3. Дворівневе кодування. Алгоритм Лемпеля-Зіва
Усі методи та моделі кодування, розглянуті вище, розглядали в якості вхідних даних ланцюжки символів (тексти) в деякому нескінченому алфавіті. При цьому залишалося відкритим питання про зв’язок цього вхідного алфавіту кодера з даними, що підлягають стисканню (і представлені у вигляді ланцюжків в (іншому) алфавіті, який зазвичай складається із 256 символів-байтів).
В найпростішому випадку можна використовувати в якості вхідного алфавіту саме ці символи (байти) вхідного потоку. Саме так працює метод squashing програми РКРАК (використане статичне кодування Хаффмена, двопрохідний алгоритм). Ступінь стискання при цьому відносно невеликий – близько 50% для текстових файлів.
Значно якісніше стискання можна отримати виділенням із вхідного потоку ланцюжків, що повторюються, і кодування посилань на ці ланцюжки.
Цей метод належить Лемпелю та Зіву і називається LZ77-compression (за роком публікації). Він полягає в наступному: компресор постійно зберігає певну кількість останніх оброблених символів у деякому буфері (який також називається ковзаючим словником – sliding dictionary). Назва “ковзаючий” зумовлена тим, що його довжина постійна: кожного разу, коли компресор кодує наступний ланцюжок, він дописує її в кінець словника та “відрізає” відповідну кількість символів на початку буфера. Під час обробки вхідного потоку символи, що надійшли, потрапляють у кінець буфера, зсуваючи попередні символи та витісняючи найстаріші.
Розміри цього буфера є різними в різних реалізаціях. Очевидно, що використання буфера більших розмірів дозволяє отримати якісніший результат. Алгоритм виділяє (шляхом пошуку в словнику) найдовший початковий підрядок вхідного потоку, що співпадає з одним із підрядків у словнику, і подає на вихід пару (length, distance), де length – довжина знайденого у словнику підрядка, а distance – відстань від нього до вхідного підрядка (тобто фактично індекс підрядка в буфері, віднятий від його розміру). В разі, коли такого підрядка не знайдено, до вихідного потоку просто копіюється черговий символ вхідного потоку.
У найпершій версії алгоритму пропонувалося виконувати найпростіший пошук по всьому словнику. Час стискання за такої реалізації був пропорційний добутку довжини вхідного потоку на розмір буфера, що не є придатним для практичного використання. Але потім було запропоновано використовувати двійкове дерево для пошуку в словнику, що дозволило на порядок збільшити швидкість роботи. Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вхідних символів на два паралельних потоки length та distance. Очевидно, що ці потоки є потоками символів в алфавітах L та D, і до них можна застосувати один із вищенаведених методів (RLE, кодування Хаффмена, арифметичне кодування). Це підводить нас до ідеї дворівневого кодування, найефективнішій серед усіх, що використовуються сьогодні на практиці. Під час реалізації цього методу необхідно домогтися узгодженого виводу обох потоків в один файл. Ця проблема зазвичай розв’язується шляхом почергового запису кодів символів із обох потоків.
1.4. Сімейство алгоритмів 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 – деревом послідовного політерного пошуку.
Час роботи цього алгоритма лінійний за довжиною вхідного потоку та не залежить від розміру словника (для кожного символа, що зчитується, відбувається або один пошук у словнику, або додавання однієї нової комірки). Саме тому він є досить популярним в апаратних реалізаціях (приклад –протокол v42bis).
Кодер LZW додає до словника одну комірку для кожного розпізнаного ланцюжка (тому його можна назвати методом із фразо-розширюваним словником). Коли словник переповнюється, кодер може або припинити його заповнення (“заморозити” словник, як класичний LZW), або очистити (повністю – compress, частково – PKZIP shrinking).
Алгоритм MW (Miller and Wegman), на відміну від LZW, утворює нові комірки словника шляхом склеювання двох рядків (тобто використовує фразо-інкрементний словник): розпізнавши за аналогією з LZW ланцюжок S на вході, він додає до словника нову комірку PS – конкатенацію ланцюжків Р (попереднього розпізнаного ланцюжка) та S (нового). Завдяки цьому він, як правило, швидше адаптується до тексту, але може пропустити деякі ланцюжки. Тому він стискає не набагато краще за LZW, а деколи навіть і гірше.
Алгоритм MW не є префіксним. Тому реалізація словника для нього є складним завданням: звичайно, ми можемо використовувати trie для політерного пошуку (для цього ми запам’ятаємо всі префікси всіх ланцюжків із словника), однак маємо додати до кожного вузла прапорець, що вказує, чи міститься поданий рядок у словнику. До того ж пошук по словнику може вимагати повернення: якщо словник містить рядки abc та abcde, але не містить рядка abcdef (який тільки-но прочитано зі входу), то нам доведеться спочатку зчитати його весь, щоб пересвідчитися, що в словнику його немає, а потім “прокрутити” вхідний потік назад на три символи. Властивість префіксності можна повернути, не втративши адаптивності алгоритму MW, якщо під час розпізнавання чергового ланцюжка S після ланцюжка P додавати до словника не тільки сам ланцюжок PS (як алгоритм MW), а множину АР(P,S) – всі префікси PS, що довші за S. Маємо кодування АР (all prefixes), відкрите Сторером у 1988 р.
Алгоритм АР нарощує словник значно швидше, ніж MW. У той самий час, він зазвичай стискає краще, ніж MW.
Стосовно Y-кодування, відкритого Деніелом Бернстейном, то цей метод додає до словника один рядок на кожний прочитаний символ (подібно до АР), до того ж має властивість префіксності (подібно до LZW), тобто це – літерно-інкрементний метод з літерно-розширюваним словником.
1.5. Алгоритм арифметичного кодування
Теоретично більш простим і набагато привабливішим підходом є сучасний алгоритм, який назвали арифметичним кодуванням. Його найбільш важливими властивостями є здатність кодування символу а з вірогідністю Р появи в тексті кількістю бітів скільки завгодно близьким до теоретичної оцінки, при цьому вірогідність символів може бути на кожному кроці роботи алгоритму різними, що дозволяє ефективно використовувати адаптивне моделювання сумісне з даним алгоритмом кодування. Додатково існує ефективна ідея практичної реалізації алгоритму - досить швидка і не вимагає великих об’ємів пам'яті.
У арифметичному кодуванні символ може відповідати дробовій кількості вихідних бітів. На практиці, звичайно, результат в самому кінці роботи алгоритму повинен бути цілим числом бітів, але, якщо кодувати декілька послідовних найбільш вірогідних символів разом, вони займатимуть значно менше місця.
Складність арифметичного кодування полягає в тому, що алгоритм сам по собі працює з накопичуваною вірогідністю розподілу, що вимагає деякого порядку розміщення символів в початковому алфавіті.
Алгоритм арифметичного кодування зменшує відповідний тексту інтервал по мірі стиснення, збільшуючи кількість бітів, які необхідні для його представлення. Чергові символи тексту скорочують величину інтервалу, виходячи із значень їх вірогідності, які визначаються моделлю.
2. Формулювання поставленої задачі
2.1. Постановка задачі
Написати програму, яка реалізує алгоритм арифметичного кодування-декодування, що виконує стиснення інформації. На вході програма повинна отримати файл; на виході цей файл повинен бути закодованим. Також реалізувати декодування цього файлу. Порівняти ефективність стиснення з різними форматами файлів.
2.2. Функціональні вимоги
Метою даної курсової роботи є написання програми, яка виконує кодування інформації методом «Арифметичне кодування». Для її успішного написання потрібно, щоб виконувались ряд вимог:
Програма повинна надавати користувачу можливість кодувати і декодувати інформацію;
Забезпечення максимальної надійності при кодуванні і декодуванні;
Можливість порівняння кодованого і декодованого файлу;
Додаткові можливості виконання дій над файлами (задання шляху збереження кодованих чи декодованих файлів, зберігати (видаляти) файли після їх кодування (декодування).
3. Реалізація алгоритму арифметичного кодування - декодування
3.1. Загальний опис алгоритму арифметичного кодування - декодування
При арифметичному кодуванні текст представляється числами з плаваючою комою в інтервалі від 0 до 1. В процесі кодування тексту інтервал, що його відображає – зменшується, а кількість бітів для його представлення збільшується. Наступні символи тексту зменшують величину інтервалу, виходячи з значень їх ймовірностей, які визначаються моделлю. Більш ймовірні символи роблять це в меншій мірі ніж менш ймовірні та, таким чином, додають менше бітів до результату.
Перед початком роботи відповідний до тексту інтервал є [0 ; 1). При обробці наступного символу його ширина звужується за рахунок виділення цьому символу частини інтервалу. Наприклад, застосуємо до тексту “еаіі!” алфавіту {а, е, і, о, u, ! } модель з постійними ймовірностями, що задані в таблиці 1.
Таблиця 1. Приклад постійної моделі для алфавіту {а, е, і, о, u, ! }
Символ
Ймовірність
Інтервал
А
0,2
[0,0; 0,2)
Е
0,3
[0,2; 0,5)
І
0,1
[0,5; 0,6)
О
0,2
[0,6; 0,8)
У
0,1
[0,8; 0,9)
!
0,1
[0,9; 1,0)
І кодувальнику, і декодувальнику відомо, що на самому початку інтервал є [0; 1). Після перегляду першого символу “е”, кодувальник звужує інтервал до [0,2; 0,5), який модель виділяє цьому символу. Другий символ “а” звузить цей новий інтервал до першої його п’ятої частина, оскільки для “а” виділено фіксований інтервал [0,0; 0,2). В результаті отримаємо робочий інтервал [0,2; 0,26), бо попередній інтервал мав ширину в 0,3 одиниці та одна п’ята від нього є 0,06. Наступному символу “і” відповідає фіксований інтервал [0,5; 0,6), що застосовано до робочого інтервалу [0,2; 0,26) звужує його до інтервалу [0,23; 0,236). Продовжуючи таким саме способом маємо:
На початку
[0.0; 1.0 )
Після перегляду “е”
[0.2; 0.5 )
Після перегляду “а”
[0.2; 0.26 )
Після перегляду “і”
[0.23; 0.236 )
Після перегляду “і”
[0.233; 0.2336 )
Після перегляду “!”
[0.23354; 0.2336 )
Припустимо, що все те, що декодувальник знає про текст, це кінцевий інтервал [0,23354; 0,2336). Він відразу ж зрозуміє, що перший закодований символ – це “е”, тому що підсумковий інтервал цілком лежить в інтервалі, що був виділений цьому символу відповідно до Таблиці 1. Тепер повторимо дії кодувальника:
Спочатку
[0.0; 1.0 )
Після перегляду “е”
[0.2; 0.5 )
Звідси зрозуміло, що другий символ – це “а”, оскільки це призведе до інтервалу [0,2; 0,26), який цілком містить в собі підсумковий інтервал [0,23354; 0,2336). Працюючи в такий спосіб, декодувальник витягує весь текст.
Декодувальник не має потреби знати значення обох меж підсумкового інтервалу, який був одержаний від кодувальника. Навіть одного значення, що лежить всередині нього, наприклад, 0,23355 вже достатньо. (Інші числа – 0,23354, 0,23357 та навіть 0,23354321 – цілком придатні). Однак, щоб завершити процес, декодувальнику потрібно своєчасно розпізнати кінець тексту. Крім того, одне й те саме число 0,0 можна представити і як “а”, і як “аа”, і як “ааа” і т. д. Для усунення непорозуміння ми повинні позначати завершення кожного тексту спеціальним символом EOF, що відомий і кодувальнику, і декодувальнику. Для алфавіту з таблиці 1 з цією метою, і тільки з нею, буде використовуватися символ “!”. Коли декодувальник зустрічає цей символ, то він завершує свій процес.
Для фіксованої моделі, яка задається моделлю таблиці 1, ентропія 5-ти символьного тексту “еаіі!” буде –log 0,3 – log 0,2 – log 0,1 – log 0,1 – log 0,1 = – log 0,00006 ( 4,22. (Тут застосовуємо логарифм з основою 10, бо вищенаведене кодування виконувалося для десяткових чисел). Це пояснює, чому потрібно 5 десяткових цифр для кодування цього тексту. Таким чином, ширина підсумкового інтервалу є 0,2336 – 0, 23354 = 0,00006, а ентропія – від’ємний десятковий логарифм цього числа. Звичайно ми працюємо з двійковою арифметикою, передаємо двійкові числа та вимірюємо ентропію в бітах.
П’яти десяткових цифр здається забагато для кодування тексту з чотирьох голосних! Мабуть не зовсім вдало було б закінчувати приклад розгортанням, а не стисненням. Однак зрозуміло, що різні моделі дають різну ентропію. Краща модель, побудована на аналізі окремих символів тексту “еаіі!”, є така множина частот символів: {“е” (0,2), “а” (0,2), “і” (0,4), “!” (0,2) }. Вона дає ентропію, що дорівнює 2,89 в десятковій системі відліку, тобто кодує вихідний текст числом з трьох цифр. Однак, більш складні моделі, як відмічалося раніше, дають в загальному випадку набагато кращій результат.
3.1.1. Фіксована модель
Найпростішою моделлю, про яку ішла мова вище, є така модель, в якій частоти символів постійні. Модель з таблиці 1 задає постійні частоти символів для алфавіту {a, e, i, u, o, !}. Строгою моделлю є така модель, в якій частоти символів тексту точно відповідають специфікації моделі.
3.1.2. Адаптивна модель
Дана модаль змінює частоти вже знайдених в тексті символів. Спочатку всі лічильники можуть бути рівними, що відображує відсутність початкових даних, але при перегляді кожного вхідного символу вони змінюються, наближуючись до спостережуваних частот. І кодувальник, і декодувальник використовують однакові початкові значення (наприклад, рівні лічильники) і один і той самий алгоритм оновлення, що дозволить їх моделям завжди залишатися на одному рівні. Кодувальник отримує наступний символ, кодує його та змінює модель. Декодувальник з’ясовує наступний символ на основі своєї поточної моделі, а потім оновлює її.
3.1.3. Проблеми переповнення і завершення кодування
При реалізації алгоритму арифметичного кодування може виникати ряд серйозних проблем:
Від’ємне переповнення
Арифметичне кодування працює за допомогою масштабування накопичених ймовірностей, які надаються моделлю в інтервалі [low; high] для кожного символу, що передається. Припустимо, що low і high так близькі один до одного, що операція масштабування призводить одержані від моделі різні символи до одного цілого числа, яке входить в [low; high]. В такому випадку подальше кодування продовжувати неможливо. Тому кодувальник повинен слідкувати за тим, щоб інтервал [low; high] завжди був досить широким.
Проблема від’ємного переповнення розглядається тільки відносно кодувальника, тому що при декодуванні кожного символу процес крокує за операцією кодування, і від’ємне переповнення не виникне, якщо виконується таке саме масштабування з тими ж самими умовами.
Переповнення
Певний тип змінної може поміщати конкретну довжину бітів, тобто закодоване число може лежати в певній межі. При виході закодованого числа з цієї межі декодувальник може невірно розкодувати символ. Тому потрібно слідкувати щоб не виникало таке переповнення.
Завершення кодування
При завершені процесу кодування необхідно послати унікальний термінальний символ (EOF-символ), а потім послати достатню кількість бітів для гарантії того, що закодований рядок потрапить в підсумковий робочий інтервал.
3.2. Реалізація арифметичного кодування
В даній курсовій роботі використовуємо модель на основі аналізу кожного символу. Така модель буде набагато ефективнішою ніж фіксована, оскільки буде використовувати тільки ті символи які присутні у файлі, а в результаті під символ буде відводитись більший проміжок.
Для забезпечення універсальності програми потрібно забезпечити відкривання файлу у бітовому форматі.
Отже, реалізація арифметичного кодування (декодування) виконується в декілька кроків.
3.2.1. Попередній аналіз файлу
На цьому рівні відбувається аналіз кожного символу, що присутні у файлі, тобто підраховується кількість однакових символів. В результаті роботи процедури створюються чотири масиви, а саме:
mas0 – набір символів, як не повторюються
mas1 – початок проміжку кожного з символів
mas2 – початок проміжку кожного з символів
mas3 – кількість конкретного символу
Реалізацію приведено нижче.
procedure Analize;
var krok,dovz: real;
simbol: byte;
n: integer;
flag: boolean;
f: file of byte;
begin
n:=0;
i:=0;
SetLength(mas0,0);
SetLength(mas1,0);
SetLength(mas2,0);
SetLength(mas3,0);
AssignFile(f,f_name);
Reset(f);
while not eof(f) do
begin
flag:=true;
SetLength(mas0,i+1);
SetLength(mas1,i+1);
SetLength(mas2,i+1);
SetLength(mas3,i+1);
Read(f,simbol);
for j:=0 to Length(mas3)-1 do
if mas0[j]=Char(simbol) then
begin
mas3[j]:=mas3[j]+1;
flag:=false;
break;
end;
if flag then
begin
mas3[i]:=1;
mas0[i]:=Char(simbol);
i:=i+1;
end;
n:=n+1;
end;
CloseFile(f);
krok:=1/n;
n:=i;
dovz:=0;
i:=0;
for i:=0 to n-1 do
begin
mas1[i]:=dovz;
dovz:=dovz+krok*mas3[i];
mas2[i]:=dovz;
end;
end;
3.2.2. Кодування файлу
Цей етап проводиться по вище описаному алгоритмі арифметичного кодування, тобто початковий проміжок встановлюється в (0,1), зчитується символ і поточний проміжок звужується до певних розмірів. Це продовжується поки величина проміжку не стане меншим за фіксоване значення. Щоб ефективніше використовувати пам’ять, підраховуємо ентропію і зберігаємо тільки ту кількість цифр яка рівна ентропії. Отримане число буде дробовим і меншим за одиницю (наприклад, 0.7465374858362834). Тому ‘0.’ можемо не зберігати. Отримане ціле число зберігаємо у файл і процес повторюємо знову поки не дійдемо до кінця файлу.
Реалізація описаного алгоритму приведено нижче.
AssignFile(f1,f_name);
AssignFile(f2,ExtractFileDir(ParamStr(0))+'\Data\Temp.txt');
Rewrite(f2);
Reset(f1);
while not Eof(f1) do
begin
entrop:=0;
Read(f1,simbol);
if Eof(f1) then break;
for j:=0 to Length(mas3)-1 do
if mas0[j]=Char(simbol) then
begin
l:=mas1[j];
h:=mas2[j];
entrop:=entrop+(log10(h-l)*-1);
break;
end;
while h-l>0.0000001 do
begin
Read(f1,simbol);
if Eof(f1) then break;
for j:=0 to Length(mas3)-1 do
if mas0[j]=Char(simbol) then
begin
l2:=mas1[j];
h2:=mas2[j];
entrop:=entrop+(log10(h2-l2)*-1);
break;
end;
if l2<>0 then l3:=((h-l)/(1/l2))+l else l3:=0;
h3:=((h-l)/(1/h2))+l;
if l2<>0 then l:=l3 else l3:=0;
h:=h3;
end;
x:=10;
ss1:='';
ss2:='';
for i:=1 to trunc(entrop) do
x:=x*10;
zz:=(l+h)/2;
ss1:=FloatToStr(trunc(zz*x*10));
for i:=0 to trunc(entrop+1)-Length(ss1) do
ss2:=ss2+'0';
ss1:=ss2+ss1;
write(f2,ss1);
write(f2,' ');
end;
CloseFile(f1);
CloseFile(f2);
Додаткова обробка закодованого файлу
В результаті розробленого алгоритму кодування отримаємо ефект протилежний до стискання. Тому потрібно провести додаткову обробку кодованого файлу. Цей файл складається з набору цифр. Тому є можливість дві цифри організувати як один байт. Отриманий файл буде стиснений в два рази.
Реалізацію приведено нижче.
procedure Compres;
var simb_1,simb_2: string;
sm_1,sm_2: char;
f1,f2: TextFile;
begin
AssignFile(f1,ExtractFileDir(ParamStr(0))+'\Data\Rezylt_2.arf');
AssignFile(f2,ExtractFileDir(ParamStr(0))+'\Data\Temp.txt');
Rewrite(f1);
Reset(f2);
while not Eof(f2) do
begin
r:=0;
Read(f2,sm_1);
simb_1:=sm_1;
if sm_1=' ' then simb_1:='15';
sb_1:=StrToInt(simb_1);
r:=sb_1;
r:=r shl 4;
if Eof(f2) then begin
r:=r or 0;
Write(f1,Char(r));
break;
end;
Read(f2,sm_2);
simb_2:=sm_2;
if sm_2=' ' then simb_2:='15';
sb_2:=StrToInt(simb_2);
r:=r or sb_2;
Write(f1,Char(r));
end;
CloseFile(f1);
CloseFile(f2);
end;
3.3. Реалізація арифметичного декодування
Арифметичне декодування реалізовано подібно до арифметичного кодування, тільки в зворотному порядку. Воно виконується в два етапи.
3.3.1. Додаткова обробка закодованого файлу
Процес зворотній до описаного в кодуванні, тобто один байт розбивається на дві цифри.
Реалізацію приведено нижче.
procedure Decompres;
var sm: char;
n1,n2: byte;
_str: string;
n: integer;
f1,f2: TextFile;
begin
AssignFile(f1,ExtractFileDir(ParamStr(0))+'\Data\Rezylt_2.arf');
AssignFile(f2,ExtractFileDir(ParamStr(0))+'\Data\Temp.txt');
Rewrite(f2);
Reset(f1);
while not Eof(f1) do
begin
Read(f1,sm);
n1:=Byte(sm);
n2:=n1 and 240;
n2:=n2 shr 4;
if n2=15 then Write(f2,' ')
else Write(f2,IntToStr(n2));
n1:=n1 and 15;
if n1=15 then Write(f2,' ')
else Write(f2,IntToStr(n1));
end;
CloseFile(f1);
CloseFile(f2);
end;
3.3.2. Декодування файлу
Реалізацію приведено нижче.
AssignFile(f1,ExtractFileDir(ParamStr(0))+'\Data\Rezylt.txt');
AssignFile(f2,ExtractFileDir(ParamStr(0))+'\Data\Temp.txt');
Rewrite(f1);
Reset(f2);
while not Eof(f2) do
begin
rech:='';
while not Eof(f2) do
begin
Read(f2,sim);
if sim<>' ' then rech:=rech+sim
else break;
end;
rech:='0,'+rech;
rez:=StrToFloat(rech);
rech:='';
i:=0;
while i<Length(mas3) do
begin
l:=mas1[i];
h:=mas2[i];
if (rez>=l) and (rez<=h) then begin
rech:=mas0[i];
break;
end;
i:=i+1;
end;
while h-l>0.0000001 do
begin
i:=0;
while i<Length(mas3) do
begin
l2:=mas1[i];
h2:=mas2[i];
if l2<>0 then l3:=((h-l)/(1/l2))+l else l3:=0;
h3:=((h-l)/(1/h2))+l;
if (rez>=l3) and (rez<=h3) then begin
rech:=rech+mas0[i];
if l2<>0 then l:=l3;
h:=h3;
break;
end;
i:=i+1;
end;
end;
write(f1,rech);
end;
CloseFile(f1);
CloseFile(f2);
3.4. Збереження таблиці
Після виконання процедури аналізу файлу утворюється таблиця, яка бере участь при кодуванні і декодуванні. Ця таблиця містить інформацію про кожен символ, який зустрічається у файлі, а саме: сам символ, його початкова і кінцева межа в проміжку.
Для забезпечення коректного декодування файлу, цю таблицю потрібно зберегти. Реалізована програма проводить збереження таблиці в окремий файл. В цьому файлі спочатку відбувається запис проміжків кожного з символів, після чого записуються самі символи. Також потрібно зберегти кількість символів.
3.5. Проектування інтерфейсу користувача
При проектуванні інтерфейсу було дотримано ряд вимог:
Зручність у використанні;
Присутність тільки потрібної інформації;
Можливість використання основних функцій програми.
Для реалізації інтерфейсу програми арифметичного кодування-декодування немає необхідності використання багатьох компонентів. Програма виконує дві основні функції, а саме: кодування і декодування файлів. Щоб програму було зручніше використовувати, до інтерфейсу додатково винесені компоненти перегляду отриманих результатів і зроблено можливість стирання файлів після їх кодування чи декодування.
Результат розробленого інтерфейсу програми арифметичного кодування-декодування представлено на рис.1.
Рис.1 Головне вікно програми
У верхньому полі «Шлях до файлу» задається файли який буде кодований або декодований.
У полі «Задати директорію збереження файлу» задається шлях для кодованих або декодованих файлів.
«Кодування (декодування) з видаленням поточного файлу» призначені для видалення файлів які кодуються чи декодуються.
Розроблено також лінію прогресу для візуального бачення завершення процесу.
Панель «Інформація результатів» призначена для перегляду інформації про кодований файл: розмір кодованого файлу, розмір закодованого файлу і ефект стиснення.
4. Ефективність стискання арифметичного кодування
Ефективність дії запрограмованого алгоритму арифметичного кодування наведена в таблиці 2.
Таблиця 2. Ефективність арифметичного кодування
Розширення файлу
Розмір файлу до кодування
Розмір файлу після кодування
Ефективність кодування
.txt
163
153
-10
.doc
25
8
-17
.exe
396
515
+119
.jpg
47
78
+31
З наведених прикладів у таблиці 2 можемо зробити висновок, що ефективність стиснення інформації арифметичним кодуванням проявляється тільки при кодуванні файлів, які містять текстові дані. Також ця ефективність залежить від випадкового розміщення символів.
При кодуванні файлів, які містять елементи вже стисненої інформації можемо спостерігати протилежний ефект, тобто файл починає набирати ще більшого розміру. Текстові файли, які містять графічні елементи також будуть набирати більшого розміру.
З таких причин алгоритм «Арифметичне кодування» зручно використовувати для текстової інформації.
5. Інструкція по використанню розробленої програми
Для виконання кодування файлу потрібно виконати наступні дії:
Вибрати файл для кодування. Для цього потрібно нажати на кнопку «Шлях до файлу» і вибрати потрібний файл (рис. 2).
Вибрати опцію «Задати директорію збереження файлу» і задати шлях де буде збережено кодований файл (рис. 3). Якщо дана опція не буде вибрана, то кодований файл буде збережено в папці де знаходиться поточний файл, що кодується.
При виборі опції «Кодування з видаленням поточного файлу» після кодування буде видалено файл, що кодується.
Нажати на кнопку «Кодувати».
Рис. 2 Задання шляху для кодування (декодування) файлу
Рис. 3 Задання шляху для збереження кодованого (декодованого) файлу
Для виконання декодування файлу потрібно виконати такі дії:
Вибрати файл для декодування. Для цього потрібно нажати на кнопку «Шлях до файлу» і вибрати потрібний файл (рис. 2).
Вибрати опцію «Задати директорію збереження файлу» і задати шлях де буде збережено декодований файл (рис. 3). Якщо дана опція не буде вибрана, то декодований файл буде збережено в папці де знаходиться поточний файл, що декодується.
При виборі опції «Декодування з видаленням поточного файлу» після декодування буде видалено файл, що декодується.
Нажати на кнопку «Декодувати».
ВИСНОВОК
З огляду на те, що різні види алгоритмів призначенні для різних типів файлів, алгоритм «Арифметичне кодування» є досить ефективним. Його ефективність найбільше проявляється при кодуванні текстових файлів. При цьому, файли можуть бути стиснені в два або і в три рази. Таку ефективність також можна підвищити використовуючи більш складні моделі.
Алгоритм «Арифметичне кодування» має високу надійність, тобто при декодуванні у файлі не відбувається ніяких змін.
Даний алгоритм має і недоліки, а саме: переповнення, завершення кодування і інші.
Розроблена програма є практичною і зручною для використання. Вона виконує дві основні функції: кодування і декодування файлів. Кодування і декодування відбуваються однозначно. Також програма має декілька додаткових функцій.
СПИСОК ЛІТЕРАТУРИ
Rubin F. Arithmetic stream coding using fixed precision registers, IEEE Transactions IT-25, #6, Nov79, pp. 672 – 675.
Кричевский Р. Е. Сжатие и поиск информации., Москва, 1989 г.
Кохманюк Д. Сжатие информации: как это делаеться., IndexPRO, Киев, №№1,2.
Рябко Б.Я. Сжатие информации спомощью стопки книг. // Проблемы передачи информации.- 1980, т.16, №4. С.16-21.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора