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

 

Міністерство освіти і  науки України

Національний університет  «Львівська політехніка»

Кафедра ЕОМ

 

Курсовий проект

На тему:

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

З дисципліни «Системне програмне  забезпечення»

 

 

 

 

 

 

 

 

 

 

Львів 2013

 

Завдання

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

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

Утиліта має бути орієнтована  під ОС Windows XP, ОС Windows 7 та ОС Windows 8. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Анотація

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

Для відкривання вхідного та створення вихідного файлу, були використані системні виклики System.IO.FileStream платформи .Net framework 4.0. Також було використано  багатопотоковість, що в свою чергу  забезпечило більш швидку роботу та більш високу надійність даного програмного забезпечення.

Для визначення розміру вхідного та вихідного файлу було використано  системну функцію GetFileSizeEx бібліотеки kernell32.dll.

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

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

 

Зміст

Вступ………………………………………………………………………..5

1. Теоретичні відомості…………………………………………………..6
1. Процеси, потоки та багатопотоковість………………………..6
2. Загальні характеристики методів стискання інформації…….8
3. Кодування Хаффмена…………………………………………..9
4. Дворівневе кодування. Алгоритм Лемпеля-Зіва……………..10
5. Сімейство алгоритмів LZ78(LZW, MW, AP, Y)………………11
6. Алгоритм арифметичного кодування…………………………12
2. Аналіз завдання та способи його вирішення………………………..14
1. Аналіз завдання…………………………………………………14
2. Блок-схема алгоритму кодування……………………………..14
1. Опис блок-схеми алгоритму кодування…………………...16
3. Блок-схема алгоритму декодування…………………………..16
1. Опис блок-схеми алгоритму декодування………………...18
3. Розробка програми……………………………………………………19
1. Вибір мови та середовища програмування…………………..19
2. Бібліотеки, які використовуються при написанні програми..19
3. Розробка блок-схеми роботи програми кодування……..…..20
4. Розробка блок-схеми роботи програми декодування……….25
4. Опис інтерфейсу та тестування програми…………………………...29
1. Опис інтерфейсу програми…………………………………….29
2. Тестування програми…………………………………………..30
3. Ефективність стиснення файлів за алгоритмом

«Арифметичне кодування»…………………………………….33

Висновок…………………………………………………………………..34

Список використаної літератури………………………………………..35

Додаток А…………………………………………………………………36

 

Вступ

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

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

Арифметичне кодування є  одним з перспективних методів  стиску інформації, та, в деякому  розумінні, її шифруванні. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску – ентропії вхідного потоку.

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

 

1. Теоретичні відомості

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

1. Процеси, потоки та багатопотоковість

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

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

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

• стан регістрів;
• системний стек ядра ОС (kernel stack);
• стек користувача (user stack), розташований в адресному просторі процесу;
• блок змінних оточення потоку.

Потік містить такі елементи:

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

• стек потоку (ділянка пам'яті, де перебувають локальні змінні потоку й адреси повернення функцій, що викликані  у його коді).

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

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

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

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

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

2. Для підтримки потоків  потрібно менше ресурсів, ніж  для підтримки процесів (наприклад,  немає необхідності виділяти  для потоків адресний простір).

3. Для обміну даними  між потоками може бути використана  спільна пам'ять (адресний простір  їхнього процесу). Це ефективніше,  ніж застосовувати засоби міжпроцесової  взаємодії.

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

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

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

1.2. Загальні характеристики методів стискання інформації

Методи стискання інформації мають досить довгу історію. Найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).

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

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

Надалі будемо розглядати компресор (compressor) як програму, що перетворює масив символів деякого алфавіту в інший, бажано меншого за розміром. Часто роль цього масиву виконує  безструктурний двійковий файл (подібний до файла MS-DOS або UNIX), а роль масиву символів вхідного алфавіту – 256 можливих значень  байта (але не завжди). Відповідно, декомпресор (decompressor) – програма, що виконує зворотнє перетворення, до того ж виконує  його однозначно. Таким чином, ми виключаємо з розгляду методи стискання, що втрачають  інформацію (наприклад, метод стискання  зображень JPEG, що базується на перетворенні кольорів, які практично неможливо  розрізнити людським оком).