Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Утиліта стискання файлів за алгоритмом арифметичного кодування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Курсовий проект
Предмет:
Системне програмне забезпечення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
/
Курсовий проект
На тему:
«Утиліта стискання файлів за алгоритмом арифметичного кодування»
З дисципліни «Системне програмне забезпечення»
Завдання
Написати програму, яка реалізує алгоритм арифметичного кодування-декодування, що виконує стиснення інформації. На вході програма повинна отримати файл, а на виході цей файл повинен бути закодованим. Також реалізувати декодування цього файлу. Порівняти ефективність стиснення з різними форматами файлів. Програма має виконувати такі функції:
надавати користувачу можливість кодувати та декодувати файли;
забезпечити максимальну надійність при кодуванні та декодуванні;
надавати можливість порівняння кодованого та декодованого файлу;
надавати додаткові можливості виконання дій над файлами (задання шляху збереження кодованих чи декодованих файлів, зберігати (видаляти) файли після їх кодування (декодування).
Утиліта має бути орієнтована під ОС Windows XP, ОС Windows 7 та ОС Windows 8.
Анотація
В даному курсовому проекті наведено процес створення утиліти, яка стискає файли за алгоритмом «Арифметичне кодування».
Для відкривання вхідного та створення вихідного файлу, були використані системні виклики System.IO.FileStream платформи .Net framework 4.0. Також було використано багатопотоковість, що в свою чергу забезпечило більш швидку роботу та більш високу надійність даного програмного забезпечення.
Для визначення розміру вхідного та вихідного файлу було використано системну функцію GetFileSizeEx бібліотеки kernell32.dll.
В якості середовища розробки даної утиліти було використано Microsoft Visual Studio 2010, оскільки це середовище є сучасним та потужним засобом створення програмних продуктів. Також, дане середовище є потужним інструментом в створені графічного інтерфейсу користувача.
Утиліта має графічний, інтуітивно зрозумілий, інтерфейс користувача. В результаті роботи програми, а саме кодуванні вхідного файлу, на виході ми отримуємо закодований файл з розширенням «cf», в якому міститься інформація, закодована за алгоритмом «Арифметичне кодування».
Зміст
Вступ………………………………………………………………………..5
Теоретичні відомості…………………………………………………..6
Процеси, потоки та багатопотоковість………………………..6
Загальні характеристики методів стискання інформації…….8
Кодування Хаффмена…………………………………………..9
Дворівневе кодування. Алгоритм Лемпеля-Зіва……………..10
Сімейство алгоритмів LZ78(LZW, MW, AP, Y)………………11
Алгоритм арифметичного кодування…………………………12
Аналіз завдання та способи його вирішення………………………..14
Аналіз завдання…………………………………………………14
Блок-схема алгоритму кодування……………………………..14
Опис блок-схеми алгоритму кодування…………………...16
Блок-схема алгоритму декодування…………………………..16
Опис блок-схеми алгоритму декодування………………...18
Розробка програми……………………………………………………19
Вибір мови та середовища програмування…………………..19
Бібліотеки, які використовуються при написанні програми..19
Розробка блок-схеми роботи програми кодування……..…..20
Розробка блок-схеми роботи програми декодування……….25
Опис інтерфейсу та тестування програми…………………………...29
Опис інтерфейсу програми…………………………………….29
Тестування програми…………………………………………..30
Ефективність стиснення файлів за алгоритмом
«Арифметичне кодування»…………………………………….33
Висновок…………………………………………………………………..34
Список використаної літератури………………………………………..35
Додаток А…………………………………………………………………36
Вступ
Необхідність кодування інформації виникла ще задовго до появи електронних обчислювальних машин. Кодування, в більшості випадків, використовувалося для захисту важливої інформації.
З появою комп’ютерної техніки виникла ще й проблема стискання інформації, оскільки зросли обсяги даних, потрібно було передавати інформацію на далекі відстані з максимальною надійністю, захистити інформацію від несанкціонованого доступу і т.д. З розвитком комп’ютерних мереж, зокрема, Internet, обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримки швидкодії мережі.
Арифметичне кодування є одним з перспективних методів стиску інформації, та, в деякому розумінні, її шифруванні. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску – ентропії вхідного потоку.
Програми для стиснення інформації зажди будуть актуальними, оскільки, не залежно від того, скільки пам’яті є на накопичувальних пристроях, зажди хочеться зберігати якомога більше потрібної користувачу інформації. Також, завдяки стисненню файлів можна підвищити швидкість передачі інформації по локальних чи глобальних мережах на великі відстані.
Теоретичні відомості
Стиснення інформації є невід’ємною складовою комп’ютерної техніки. Отже, стиснення інформації – це процедура перекодування даних, яка проводиться з метою зменшення їхнього обсягу, розміру, об’єму. На даний момент, методів стиснення інформації є дуже багато, такі як: RLE, Лемпеля-Зіва, кодування Хаффмена тощо. Алгоритм, який я вибрав (Арифметичне кодування), наразі є одним з найефективніших алгоритмів, оскільки досягає теоретичної границі стиснення інформації. Для пришвидшення і надійності роботи програми використовується багатопотоковість.
Процеси, потоки та багатопотоковість
Потоком (потік керування, нитка, 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, що базується на перетворенні кольорів, які практично неможливо розрізнити людським оком).
Кодування має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потоку на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи.
Перший підхід: продивитися вхідний потік і побудувати кодування на основі зібраної статистики (це потребу двох проходів по файлу, що звужує сферу застосування таких алгоритмів). У вихідний потік в такому випадку має бути записано схему кодування, що застосовувалося. Цією схемою потім скористається декодер. Приклад – статистичне кодування Хаффмена.
Другий підхід – використовувати так званий адаптивний кодер (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
Рис. 2.1 Блок-схема алгоритму стискання інформації
Ні
Так
Так
Рис. 2.1 «продовження»
Опис блок-схеми алгоритму
Першим крок є відкриття вхідного файлу, тобто файлу, який користувач бажає стиснути. Після цього відбувається визначення розміру цього файлу та ініціалізація адаптивної моделі, тобто задання початкових значень таблиць перекодування (таблиці, в яких кожному символу присвоюється певний індекс) і масиву накопичених частот(масив, в який записується частота появи певного символу в тексті). Коли ініціалізацію адаптивної моделі буде завершено, відбувається ініціалізація побітового вводу та коду перед початком стискання. Опісля всіх підготовчих операцій, відбувається саме кодування. Завантажується перший символ і передається на кодування, якщо кодування пройшло успішно, вже закодований символ записується у вихідний файл і робиться перевірка на кінець вхідного файлу. Якщо файл ще не закінчився, то завантажується наступний біт і операції повторюються, якщо ж файл закінчився, то відбувається очистка буфера побітового вводу, закриваються вхідний і вихідний файли, визначається кінцевий розмір вихідного файлу і завершується виконання програми.
Блок-схема алгоритму декодування
Блок-схема алгоритму декодування файлів за алгоритмом «Арифметичне кодування» наведена на Рис. 2.2
Рис. 2.2 Блок-схема алгоритму декодування стиснутого файлу
Ні
Так
Рис. 2.2 «продовження»
Опис блок-схеми алгоритму декодування
Спершу відкривається стиснутий файл і визначається його розмір. Після цього відбувається ініціалізація адаптивної моделі, тобто задання початкових значень таблиць перекодування (таблиці, в яких кожному символу присвоюється певний індекс) і масиву накопичених частот(масив, в який записується частота появи певного символу в тексті) і відбувається ініціалізація побітового вводу. Опісля всіх підготовчих операцій відбувається саме декодування. Воно починається з завантаження першого біта стиснутого файлу і передачі його на декодування. Після декодування відбувається вивід декодованого біта у вихідний файл і перевіряється чи файл закінчився. Якщо файл не закінчився, то наступним кроком завантажується наступний біт і повторюються операції декодування. Якщо ж файл закінчився, то вхідний і вихідний файли закриваються і визначається розмір вихідного файлу.
Розробка програми
3.1. Вибір мови та середовища програмування
В якості мови програмування я вибрав C#, оскільки ця мова є об’єктно- орієнтованою, має безпечну систему типізації і надає широкий вибір інструментів для розробника. Дане програмне забезпечення написано під платформу Microsoft .Net Framework 3.5 і вище.
Утиліта буде написана в середовищі програмуванні Microsoft Visual Studio 2010, оскільки дане середовище має зручний інтерфейс, широкий набір інструментів для створення графічного інтерфейсу користувача, інтерфейс для багатопотоковї розробки. Також дуже важливою особливістю даного середовища є легкість тестування та від лагодження програмних продуктів, які в ньому розробляються.
3.2. Бібліотеки, які використовуються при написанні програми
System.Collections.Generic - використовується для реалізації списку потоків.
System.ComponentModel - використовується для реалізації подій натискання на кнопки та зміни в формах наших вікон.
System.Data - містить класи для доступу до даних з різних джерел і для управління цими даними.
System.Drawing – використовується для настроювання вікна повідомлень яке викликається з вже існуючою форми.
System.Linq містить класи та інтерфейси, які підтримують запити, які використовують LINQ.
System.Text містить класи, що представляють кодування ASCII і Юнікод, абстрактні базові класи для перетворення блоків символів в блоки байтів і назад і клас підтримки, керуючий об'єктами String і форматує такі об'єкти без створення проміжних екземплярів String.
System.Windows.Forms – використовується для та під час створення нових форм, у тому числі і початкової форми вікна утиліти. Містить у собі опис всіх елементів які є у вікні(Button, Form, MessageBox, MessageBoxButtons, MessageBoxIcon, TextBox та ін.) та всіх параметрів вікон (розміри, положення на екрані, іконка, режим роботи та режим відображення, можливість нажаття на клавіші керування та ін.);
System.IO – використовується для створення потоків вводу та виводу текстових даних у файли
System.Diagnostics – в цьому просторі імен передбачені класи, які дозволяють здійснювати взаємодію з системними процесами
System.Threading – містить в собі класи і інтерфейси, які дають можливість використовувати потоки і багатопотоковість.
System.Runtime.InteropServices – використовується для завантаження DLL-бібліотек які не прив’язані до даної мови програмування, або створені не на даному комп’ютері (в проекті – більшість DLL-бібліотек використані для реалізації функцій виключення або перевантаження комп’ютера а також для роботи з привілегіями).
3.3. Розробка блок-схеми роботи програми кодування
Блок-схема роботи програми кодування наведена на Рис. 3.1
Рис. 3.1 Блок-схема роботи програми кодування
Ні
Так
Рис. 3.1 «продовження»
Опис блок-схеми роботи програми кодування
InitializeComponent() – це внутрішня функція вікна, яка ініціалізує елементи, які є у формі. Іншими словами, ініціалізуються всі графічні елементи програми.
Вибір файлу, який потрібно стиснути:
Потрібний файл вибирається за допомогою системного виклику DialogResult result = openFileDialog1.ShowDialog().
Якщо файл був успішно відкритий if (result == DialogResult.OK), то наступним кроком буде створення хендлу вхідного файлу, для подальшого визначення його розміру системною функцією GetFileSizeEx(handle, out fileSize).
Створення вихідного файлу:
Послідовність дій при створенні вихідного файлу така сама, як і в пункті (2), тільки з однією відмінністю: замість функції openFileDialog1.ShowDialog() використовується saveFileDialog1.ShowDialog().
Ініціалізація адаптивної моделі:
Програма повинна працювати з моделлю, яка надає пару перекодованих таблиць index_to_char [] і char_to_index [], і масив накопичених частот cum_freq []. Причому до нього висуваються такі вимоги:
cum_freq [i-1]> = cum_freq [i];
ніколи не робиться спроба кодувати символ [i], для якого:
cum_freq [i-1] = cum_freq [i];
cum_freq [0] <= Max_frequency.
Якщо дані умови дотримані, значення в масиві не повинні мати зв'язку з дійсними значеннями накопичених частот символів тексту.
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;
}
Ініціалізація побітового виводу та коду перед початком стиснення:
В даному кроці встановлюються початкові значення для подальшого кодування.
public void start_outputing_bits()
{
buffer = 0;
bits_to_go = 8;
}
public void start_encoding()
{
// Повний кодовий інтервал
low = 0L;
high = top_value;
bits_to_follow = 0L;
}
Наступний крок - безпосереднє кодування:
Спершу, завантажується перший символ файлу і передається на кодування.
Кодування одного символу виконує функція encode_symbol();
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;
}
}
Після цих кроків робиться перевірка на кінець файлу
if (ch == -1)
break;
Якщо файл ще не закінчився, то попередні дії виконуються ще раз
Останнім кроком є очистка буфера побітового вводу dataout.WriteByte((byte)(buffer >> bits_to_go)), і закриття вхідного та вихідного файлів
dataout.Close();
datain.Close();
а також визначається розмір вихідного файлу за допомогою функції GetFileSizeEx(), якій у параметри передаєть хендл вихідного файлу та змінна, у яку буде збережно розмір файлу.
3.4. Розробка блок-схеми роботи програми декодування
Блок-схема роботи програми декодування наведена на Рис. 3.2
Ні
Так
Рис. 3.2 Блок-схема роботи програми декодування
Рис. 3.2 «продовження»
Опис блок-схеми роботи програми декодування
InitializeComponent() – це внутрішня функція вікна, яка ініціалізує елементи, які є у формі. Іншими словами, ініціалізуються всі графічні елементи програми.
Вибір файлу, який потрібно стиснути:
Потрібний файл вибирається за допомогою системного виклику DialogResult result = openFileDialog1.ShowDialog();
Якщо файл був успішно відкритий if (result == DialogResult.OK), то наступним кроком буде створення хендлу вхідного файлу, для подальшого визначення його розміру системною функцією GetFileSizeEx(handle, out fileSize).
Створення вихідного файлу:
Послідовність дій при створенні вихідного файлу така сама, як і в пункті (2), тільки з однією відмінністю: замість функції openFileDialog1.ShowDialog() використовується saveFileDialog1.ShowDialog().
Ініціалізація адаптивної моделі:
Програма повинна працювати з моделлю, яка надає пару перекодованих таблиць index_to_char [] і char_to_index [], і масив накопичених частот cum_freq []. Причому до нього висуваються такі вимоги:
cum_freq [i-1]> = cum_freq [i];
ніколи не робиться спроба кодувати символ [i], для якого:
cum_freq [i-1] = cum_freq [i];
cum_freq [0] <= Max_frequency.
Якщо дані умови дотримані, значення в масиві не повинні мати зв'язку з дійсними значеннями накопичених частот символів тексту.
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;
}
Ініціалізація побітового вводу виконується функцією start_inputing_bits(). Дана функція задає початкові параметри для декодування.
void start_inputing_bits()
{
bits_to_go = 0;
garbage_bits = 0;
}
Наступним кроком є вже безпосередньо декодування. Починається декодування із завантаженням першого символу стиснутої інформації
buffer = datain.ReadByte(), який згодом передається на вхід функції decode_symbol(), яка виконує декодування і запис вже декодованого символу у вихідний файл.
int decode_symbol()
{
// Ширина інтервалу
long range;
// Накопичена частота
int cum;
// символ, який декодується
int symbol;
int a;
// Визначення поточної частоти
range = (long)(high - low) + 1;
// Знаходження значення накопиченої частоти
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 >=
06.01.2014 03:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора