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

Черкаський національний університет ім. Б. Хмельницького

Факультет інформаційних технологій та біомедичної кібернетики

Курсова робота

з дисципліни: “Об'єктно - орієнтовне програмування ”

на тему: “ Архівація файлів та створення архіватора текстових файлів ”

по спеціальності: 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 {endoffile}.

Файл займає на диску 39 байт. Зрозуміло, що інформація в файлі дещо надлишкова і зберігання файлу в такому вигляді недоцільне. Зовсім інша справа, якщо файл буде мати такий вигляд:

5a3b14ca16d {endoffile}.

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

a – "00",

b – "01",

c – "10",

d – "11".

Іншими словами файл можна закодувати таким чином, що кожен символ буде кодуватися не вісьмома, а двома бітами. І тоді економія буде чотирикратною (8/2=4). Слід зауважити, що цей варіант буде спільний і однаково ефективний навіть якщо в файлі немає жодного однакового ланцюга. Зауважте, що для застосування такого алгоритму кількісний склад представлений в файлі байт повинен бути неповним. Наприклад, якщо в файлі представлені 200 різних символів, то для однозначної ідентифікації кожного з них доведеться використати всі вісім біт ( семи не вистачить, так як комбінації з семи біт можуть приймати лише 128 значень), що не дозволить досягнути ніяких результатів при використанні цього способу стиснення.

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--