Міністерство освіти інауки України
Черкаський національнийуніверситет ім. Б. Хмельницького
Факультетінформаційних технологій та біомедичної кібернетики/>/>/>/>Курсова робота
з дисципліни: “ Об’єктно — орієнтовнепрограмування ”
на тему: “ Архівація файлів та створення архіваторатекстових файлів ”
по спеціальності: 6.080403 Програмнезабезпечення автоматизованих систем
УКР.ЧНУ. 00051015-08
Виконав:
Студент 2 курсу група
КС-061
Голубченко Ю.С.
Керівник:
Бодрих Р.С.
___________________
дата
___________________
оцінка
___________________
підпис
Черкаси 2008
/>/>/>/>/>Зміст
Зміст. 2
Спосіб представлення інформації на ПК… 3
Ідея кодування з стисненням. 4
Алгоритм Хаффмана. 6
Список використаних джерел. 10
Додатки. 11
/>/>/>/> Спосіб представлення інформації на ПК
Для початку слідсказати, що в пам’яті машини (на дискові чи в ОЗУ) данні зберігаються в виглядіпослідовності нулів та одиниць. Кожна мінімальна комірка файлу зберігає нульабо одиницю. Давайте спробуємо розібратись, що нам, користувачам, може казатиця нескінченна послідовність цифр?
З самого початкувся інформація користувача обмежувалась лише текстами. Тексти складаються зсимволів. Підрахуємо кількість символів, необхідних для того, щоб писати різнітексти. Насамперед, наш національний алфавіт(кирилиця). Додамо латиницю, знакипунктуації, цифри, знаки математичних операцій, символи №, #, @, %, і інші. А також символипсевдографіки, потрібні для малювання таблиць в тексті і деякі інші. Миотримаємо «віртуальний алфавіт», який складається приблизно з 200елементів.
Але як зберегтитекст, написаний в такому великому алфавіті, якщо комп’ютер може зберігати лишенулі та одиниці? Мінімальна комірка (біт) може приймати два значення – 0 та 1.Якщо взяти дві такі комірки, які йдуть одна за одною то така пара може приймати4 значення: «00», «01», «10», «11».Можливо ви вже здогадались, що якщо брати набори з n мінімальних комірок (біт), то числоможливих значень такого набору збільшується і буде дорівнювати степені двійки зпоказником n. Тобто якщо групуємо 2 біта,то число можливих варіантів 2^2=4; якщо три біта, то варіантів значень цієїгрупи (2^3): «000», «001», «010»,«011», «100», «101», «110»,«111» і так для кожної кількості біт в групі.
Ми хочемопідібрати таку кількість біт, група з яких може приймати як мінімум близько 200значень (кожне значення ми ототожнюємо з символом нашого алфавіту). Мінімальнастепінь двійки, яка перебільшує кількість символів віртуального алфавіту –восьма (2^8= 256). Іншими словам, згрупувавши біти по вісім штук, ми зможемокожному значенню такого набору біт (всього 256 таких значень) спів ставити своюбукву, як і було зроблено в стандарті ASCII. Саметому вся пам’ять ПК розділена на байти – групи по 8 біт. До речі саме томуперші масові процесори були восьми розрядні (кар’єра Біла Гейтса почалась звпровадження інтерпретатора мови Basic для систем, побудованих на базі восьми розрядного процесора 8080).
/>/>/>/>/>Ідея кодування з стисненням
Тепер давайтепоміркуємо як же і на чому можливо економити місце при стисненні файлів. Вдеяких файлах зустрічаються досить довгі ланцюги однакових байтів.
Уявіть собі такийфайл:
aaaaabbbccccccccccccccadddddddddddddddd {end of file}.
Файл займає надиску 39 байт. Зрозуміло, що інформація в файлі дещо надлишкова і зберіганняфайлу в такому вигляді недоцільне. Зовсім інша справа, якщо файл буде матитакий вигляд:
5a3b14ca16d {end of file}.
В такому випадкуфайл буде займати лише 11 байт. Слідуючи з цього файл можна записати більшекономічно 39/11= 3.5 разів. На цьому ж прикладі можна описати ще один спосібекономії дискового місця. Як видно файл складається всього з чотирьох символів.Якщо спів ставити кожному з них пару бітів, то отримаємо:
a –«00»,
b –«01»,
c –«10»,
d – «11».
Іншими словамифайл можна закодувати таким чином, що кожен символ буде кодуватися не вісьмома,а двома бітами. І тоді економія буде чотирикратною (8/2=4). Слід зауважити, щоцей варіант буде спільний і однаково ефективний навіть якщо в файлі немаєжодного однакового ланцюга. Зауважте, що для застосування такого алгоритмукількісний склад представлений в файлі байт повинен бути неповним. Наприклад, якщов файлі представлені 200 різних символів, то для однозначної ідентифікаціїкожного з них доведеться використати всі вісім біт ( семи не вистачить, так яккомбінації з семи біт можуть приймати лише 128 значень), що не дозволитьдосягнути ніяких результатів при використанні цього способу стиснення.
Отже, якщо визрозуміли суть приведених прикладів, то вам в повинні бути зрозумілі ідеї,згідно яким проходить стиснення файлів. Зауважте, що знаючи, яким саме правиломкористувались при стисненні, архіви можна буде розпаковувати і отримуватипочаткові файли. Це варіанти архівації без втрати якості.
З деяких піркористувачу стало недостатньо тільки текстів. І користувачі отримали можливістьзберігати на своїх жорстких дисках музику, зображення, відео. Всі ці файлитакож зберігаються в вигляді послідовності байтів. І якщо в тексті втрата хочаб одної букви або знака може мати фатальні наслідки, то в зображенні чи в відеокліпі інформація інколи наскільки надлишкова, що неминуче видалення частиниінформації ніяким чином не вплине на сприйняття людини (за рахунок обмежень,які накладаються зором и слухом). Звідси і ряд методів стиснення з втратоюякості.
/>/>/>/>/>Алгоритм Хаффмана
Це алгоритмархівації без втрати якості. В розглянутих вище прикладах передбачувалось, що,або ж початковий файл складається в основному з однорідних ланцюгів байтів, абож кількість використовуваних символів достатньо мала ( тобто файл складається зневеликої кількості елементів таблиці ASCII). Уявимо собі самий простий випадок, коли в файліпредставлена більша частина таблиці ASCII і майже немає однорідних послідовностей. В такому випадкуприпустимий результат можливо отримати тільки якщо різні байти (символи)зустрічаються в даному файлі з різною частотою. Тоді найбільш часто трапляючисьсимволи можуть бути закодовані меншим числом біт, а ті що зустрічаються доситьрідко навпаки більшим числом біт. В результаті отриманий після кодування файл сбільшою вірогідністю буде меншого об’єму, ніж початковий.
Перш ніж описатиалгоритм перекодування, який дозволяє найбільш часто зустрічаємі символи(байти) кодувати не вісьмома, а набагато меншим числом біт, потрібно вказати наобмеження, який має кожен, навіть самий ефективний алгоритм без втрати якості.
Можна уявити, щовсі файли – це тексти, написані на алфавіті, який складається з 256 літер (таквоно власне і є). Розглянемо всю множину файлів, розмір не перевищує n байт (де n будь – яке число). І припустимо, щоіснує деякий алгоритм кодування, який любий файл стискує з «додатною»ефективністю. Тоді множина всіх їх архівів які входять в склад всіх файлів,розмір яких менше n байт.Згідно нашому припущенню існує відповідність між двома закінченими множинами,кількість елементів яких не співпадає. Звідси можливо зробити досить вагомівисновки: 1) не існує архіватора, який би однаково добре пакував будь-якіфайли, 2) для будь-якого архіватора знайдуться файли, в результаті стисненняяких будуть отримані архіви в кращому випадку не меншого розміру чим початковіфайли.
Тепер почнемоописання алгоритму Хаффмана. Розглянемо його на прикладі наступного файлу:
cccacbcdaaabdcdcddcddccccccccccc {end of file}
Розпишемо частотикожного з символів:
a – 4,
b – 2,
c – 19,
d – 7.
Весь файл займає32 байта. Кожен з символів в початковому файлі кодується згідно таблиці ASCII вісьмома бітами:
a – 01100001,
b – 01100010,
c – 01100011,
d – 01100100,
Крок №1.Розмістимо ці чотири символи в порядку зменшення їх частот:
{(c,19),(d,7),(a,4),(b,2)}
Крок №2. Нанаступному рядку запишемо набір, отриманий з попереднього наступним чином:
замість двохостанніх символів з їх частотами запишемо новий елемент, котрий замість назвисимволу буде мати запис «Вершина #n», а замість частоти – сума частотостанніх двох елементів попереднього набору;
відсортуємоотриманий набір по спаданню.
{(c,19),(d,7),( «Вершина #1», 6)}
Крок №3.Переходимо на крок №2до тих пір, поки набір не буде складатися тільки з одногоелемента: («Вершина #last_number», summa_vseh_chastot):
{(c,19), («Вершина#2», 13)}
{( «Вершина #3», 32)} (візуальна ілюстрація див. Малюнок №1)
Що ж отримали?Розгляньте малюнок. Ви бачите дерево, яке росте з листків! Якщо з’єднати лінієюкожен з елементів «вершина #x» зтими елементами попередніх наборів, сума частот яких зберігається в другійчастині елемента «вершина #x», то ми отримаємо такби мовити дерево(в програмуванні подібні структури називаються бінарнимидеревами).
Суть цієї деревовидноїструктури в тому, щоб кожному з символів спів ставити різне число біт взалежності від його частоти (як вже казалося, в нетиснутому файлі символизберігаються в виді груп по вісім біт). Якщо уважно придивитись в цей малюнок,ви побачите, що кожна з гілок відмічена або нулем або одиницею. Таким чином,якщо уявно пройтись по дереву від кореня до якої-небудь вершини, маючої символ,то послідовність нулів та одиниць, які зустрічаються на вашому шляху, будекомбінацією біт для цього символу. Наприклад, символ «с» як найбільшчасто зустрічаємий буде кодуватися одним бітом «0», символ «d» двома бітами «10» іт.д. (див. Малюнок №2)
Давайтерозглянемо ще один приклад файлу, власне дерево якого має вигляд більшскладний, ніж в попередньому випадку.
Буває так, щочастоти окремих символів однакові або майже однакові, це призводить до того, щотакі символи кодуються одним і тим же числом біт. Однак алгоритм побудовидерева від цього незмінюєтся:
ddddddaaaaaabbbbbbccccdffffffffffdddd{37byte, end of file}
В двійковомувигляді файл буде мати вигляд такий:
01100100 0110010001100100 01100100 01100100 01100100 01100001 01100001 01100001 0110000101100001 01100001 01100010 01100010 01100010 01100010 01100010 0110001001100011 01100011 01100011 01100011 01100100 01100110 01100110 0110011001100110 01100110 01100110 01100110 01100110 01100110 01100110 0110010001100100 01100100 01100100{296 bit, end of file}
Розпишемо частотикожного з символів:
a — 6
b — 6
c — 4
d — 11
f — 10
Весь файл займає37 байт. Кожен з символів в початковому файлі кодується згідно таблиці ASCII вісьмома бітами. Поглянемо, якбудуть кодуватись ці символи в стиснутому файлі. Для цього побудуємо відповіднедерево (не забуваємо сортувати отриманий набір):
1. {(d,11), (f,10),(a,6), (b,6), (c,4)};
2. {(d,11), (f,10),(вершина #1, 10), (a,6)} (зауважте, що сортування по спаданню частот є обов’язковим!);
3. {(вершина #2, 16),(d,11), (f,10)};
4. {(вершина #3, 21),(вершина #2, 16)};
5. {(вершина #4, 37)}
Аналізуючиотримане дерево, розпишемо, як буде кодуватися кожен з символів післястиснення:
a — «11»
b — «100»
c — «101»
d — «00»
f — «01».
В двійковомувигляді файл буде мати такий вигляд:
0000000000001111 11111111 10010010 01001001 00101101 10110100 01010101 0101010101010000 0000хххх{88 bit, end of file}
Стиснутий файлзайняв 11 байт (останні чотири біта хххх записуються будь-які, тому що весьфайл насправді вміщується в 84 біта, що не кратно восьми). Коефіцієнт стисненняпри такому кодуванні дорівнює 3,5.
/>/>Список використаних джерел
1) Д. Ватолин, А.Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов,сжатие изображений и видео. Диалог-МИФИ, 2003 г. 384 стр.
2) Сэломон Д. Сжатиеданных, изображений и звука: Перевод с английского. Техносфера. 2004г.
/>/>/>Додатки
Малюнок №1:
/>
Малюнок №2:
/>