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

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

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

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

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

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

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

Ідея кодування з стисненням

Тепер давайте поміркуємо як же і на чому можливо економити місце при стисненні файлів. ............