Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ ХАФФМАНА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2009
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Група:
КН-3
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Кафедра ПЗ
КУРСОВА РОБОТА
з курсу: “Методи та засоби комп’ютерних інформаційних технологій”
СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ ХАФФМАНА
ЗМІСТ
ЗМІСТ 2
ВСТУП 2
ПОСТАНОВКА ЗАВДАННЯ 3
1. АНАЛІТИЧНИЙ РОЗДІЛ 3
1.1 Способи стиснення інформації 3
1.2. Алгоритм RLE 4
1.3. Алгоритм KWE 5
1.4. Алгоритм Хаффмана 6
2. ІСНУЮЧІ АНАЛОГИ 8
2.1 WinRar 8
2.2 WinZip 10
3.ПРОЕКТНИЙ РОЗДІЛ 12
3.1. Структури даних для методу Хаффмана 12
3.2. Швидший алгоритм побудови дерева 13
3.3. Алгоритм обчислення кодів Хаффмана 13
3.4. Розмір і формат запису упакованих даних 14
3.5. Кодування даних 15
3.6. Декодування даних 16
4. ІНТЕРФЕЙС ПРОГРАМИ 17
5. ТЕКСТ ПРОГРАМИ 18
6. ЕКСПЕРИМЕНТАЛЬНИЙ РОЗДІЛ 30
Таблиця порівняння стиску файлів різних форматів 31
ВИСНОВОК 31
Використана література 33
ВСТУП
Характерною особливістю більшості типів даних є їх надлишковість. Ступінь надлишковості даних залежить від типу даних. Наприклад, для відеоданих ступінь надлишковості в декілька разів більша ніж для графічних даних, а ступінь надлишковості графічних даних, у свою чергу, більша за ступінь надлишковості текстових даних. Іншим фактором, що впливає на ступінь надлишковості є прийнята система кодування. Прикладом систем кодування можуть бути звичайні мови спілкування, які є ні чим іншим, як системами кодування понять та ідей для висловлення думок. Так, встановлено, що кодування текстових даних за допомогою засобів української мови дає в середньому надлишковість на 20-25% більшу ніж кодування аналогічних даних засобами англійської мови.
Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Коли методи стиснення даних застосовуються до готових файлів, то часто замість терміну "стиснення даних" вживають термін "архівування даних", стиснений варіант даних називають архівом, а програмні засоби, що реалізують методи стиснення називаються архіваторами.
В залежності від того, в якому об'єкті розміщені дані, що підлягають стисненню розрізняють:
Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв'язку або до транспортування на зовнішніх носіях малої ємності;
Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні;
Стиснення (ущільнення) дисків: використовується для підвищення ефективності використання дискового простору шляхом стиснення даних при записі їх на носії інформації (як правило, засобами операційної системи).
ПОСТАНОВКА ЗАВДАННЯ
Написати програму на об’єктно-орієнтованій мові програмування для стиснення даних за методом Хаффмана.Програма повинна кодувати та декодувати дані.
АНАЛІТИЧНИЙ РОЗДІЛ
1.1 Способи стиснення інформації
Існує багато практичних алгоритмів стиснення даних, але всі вони базуються на трьох теоретичних способах зменшення надлишковості даних. Перший спосіб полягає в зміні вмісту даних, другий - у зміні структури даних, а третій - в одночасній зміні як структури, так і вмісту даних.
Якщо при стисненні даних відбувається зміна їх вмісту, то метод стиснення є незворотнім, тобто при відновленні (розархівуванні) даних з архіву не відбувається повне відновлення інформації. Такі методи часто називаються методами стиснення з регульованими втратами інформації. Зрозуміло, що ці методи можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не приводить до суттєвого спотворення інформації. До таких типів даних відносяться відео- та аудіодані, а також графічні дані. Методи стиснення з регульованими втратами інформації забезпечують значно більший ступінь стиснення, але їх не можна застосовувати до текстових даних. Прикладами форматів стиснення з втратами інформації можуть бути: JPEG (Joint Photographic Experts Group) для графічних даних; MPG - для для відеоданих; MP3 - для аудіоданих.
Якщо при стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадкові з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення у порівнянні з незворотними методами стиснення. Приклади форматів стиснення без втрати інформації: GIF (Graphics Interchange Format), TIFF (Tagged Image File Format) - для графічних даних; AVI - для відеоданих; ZIP, ARJ, RAR, CAB, LH - для довільних типів даних. Існує багато різних практичних методів стиснення без втрати інформації, які, як правило, мають різну ефективність для різних типів даних та різних обсягів. Однак, в основі цих методів лежать три теоретичних алгоритми:
алгоритм RLE (Run Length Encoding);
лгоритми групи KWE(KeyWord Encoding);
алгоритм Хафмана.
1.2. Алгоритм RLE
В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. Наприклад, нехай задана така послідовність даних, що підлягає стисненню:
1 1 1 1 2 2 3 4 4 4
В алгоритмі RLE пропонується замінити її наступною структурою: 1 4 2 2 3 1 4 3, де перше число кожної пари чисел -це код даних, а друге - коефіцієнт повторення. Якщо для зберігання кожного елементу даних вхідної послідовності відводиться 1 байт, то вся послідовність займатиме 10 байт пам'яті, тоді як вихідна послідовність (стиснений варіант) займатиме 8 байт пам'яті.
Чим менше значення коефіцієнта стиснення, тим ефективніший метод стиснення. Зрозуміло, що алгоритм RLE буде давати кращий ефект стиснення при більшій довжині послідовності даних, що повторюється. У випадкові розглянутого вище прикладу, якщо вхідна послідовність матиме такий вигляд: 1 1 1 1 1 1 3 4 4 4, то коефіцієнт стиснення буде рівний 60%. У зв'язку з цим найбільша ефективність алгоритму RLE досягається при стисненні графічних даних (особливо для однотонових фонових зображень).
1.3. Алгоритм KWE
В основі алгоритму стиснення за ключовими словами покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Прикладом лексичної одиниці може бути звичайне слово. На практиці, в ролі лексичних одиниць вибираються послідовності символів, що повторюються, які кодуються ланцюжком символів (кодом) меншої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник.
Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано або пізно поточний рядок перестає відповідати якій-небудь фразі словника. У цей момент, коли поточний рядок являє собою останній збіг зі словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символа, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним снмвола, додається в словник. У наступний раз, коли ця фраза з'явиться в повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації.
Алгоритм LZW побудований навколо таблиці фраз (словника), яка відображає рядки символів стиснуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази w і символа К фраза w також міститься в словнику. Якщо всі частинки словника повністю заповнені кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих в словнику фраз).
Алгоритми стиснення цієї групи найефективніші для текстових даних великих обсягів і малоефективні для файлів малих розмірів (за рахунок необхідності зберігання словника).
1.4. Алгоритм Хаффмана
Це алгоритм архівації без втрати якості. В розглянутих вище прикладах передбачувалось, що, або ж початковий файл складається в основному з однорідних ланцюгів байтів, або ж кількість використовуваних символів достатньо мала ( тобто файл складається з невеликої кількості елементів таблиці 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{37 byte, end of file}
В двійковому вигляді файл буде мати вигляд такий:
01100100 01100100 01100100 01100100 01100100 01100100 01100001 01100001 01100001 01100001 01100001 01100001 01100010 01100010 01100010 01100010 01100010 01100010 01100011 01100011 01100011 01100011 01100100 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100100 01100100 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".
В двійковому вигляді файл буде мати такий вигляд:
00000000 00001111 11111111 10010010 01001001 00101101 10110100 01010101 01010101 01010000 0000хххх{88 bit, end of file}
Стиснутий файл зайняв 11 байт (останні чотири біта хххх записуються будь-які, тому що весь файл насправді вміщується в 84 біта, що не кратно восьми). Коефіцієнт стиснення при такому кодуванні дорівнює 3,5.
ІСНУЮЧІ АНАЛОГИ
Серед всього програмного забезпечення існує дуже багато різних програм,які використовують методи стиснення інформації.Ми розглянемо найпоширеніші програми, які користуються популярністю серед користувачів.
Розглянемо такі програми як WinZip та WinRar.
2.1 WinRar
Програма WinRAR призначена для створення і керу вання архівними файлами. Вона є 32-розрядною версією архіватора RAR для ОС Windows 95, 98 і N7.
Програма WinRAR забезпечує:
• повну підтримку архівів RAR і ZІР;
• високий ступінь стиснення інформації завдяки висо коефективному алгоритму стиснення даних;
• стиснення мультимедіа файлів за допомогою спе ціального алгоритму;
• підтримку технології Drag and Drop;
• керування архівами форматів САВ, АRJ і LZH;
• підтримку неперервних архівів (ступінь стиснення інформації в них на 10—50% більший, ніж звичайни ми методами стиснення);
• підтримку багатотомних архівів;
• створення звичайних і багатотомних архівів, що роз паковуються (SРХ, від англ. SelF-eXtracting);
• відновлення фізично пошкоджених архівів;
• підтримку додаткових функцій (шифрування, додання архівних коментарів, протоколювання помилок та ін.)
Для запуску програми WinRAR необхідно двічі клац нути мишею на значку додатка або на Його ярлику. При цьому на екрані відображається головне вікно програми аналогічно вікну папки Windows 98.
Архіватор працює в режимі керування файлами або архівами. При завантаженні програми WinRAR активним є режим керування файлами. Для входження в режим керування архівами треба двічі клацнути мишею на Імені архіву, знаходячись у режимі керування файлами.
Головне вікно програми WinRAR містить смугу заго ловка, рядок меню, панель інструментів, рядок стану і ро бочу область.
У смузі заголовка є кнопки системного меню, згортан ня, розгортання та закриття вікна, а також відображають ся імена поточного диска, папки і програми WinRAR.
Рядок меню включає шість меню: Файл, Команди, История, Избранное, Параметри і ?.
Файл містить команди для вибору і/або перегляду вмісту дисків та папок, а також їх закриття.
Команди включає команди виконання основних функцій програми WinRAR.
История відображає імена файлів, з якими виконува лися дії останнім часом.
Избранное забезпечує додання папок і архівів у папку Избранное.
Параметри містить команди для встановлення пара метрів програми WinRAR.
Меню «?» забезпечує доступ до довідкової системи програми WinRAR.
На панелі інструментів знаходяться кнопки, що повто рюють пункти з меню Команди, а також список дисків, який розкривається для зміни диска.
У робочій області вікна відображається вміст поточної лапки (в режимі керування файлами) або вміст архіву (в режимі керування архівами).
Для кожного файла показуються ім'я, розмір, тип і да та його зміни, а для файлів в архіві додається ще й розмір після архівації.
Для переходу до батьківської папки требадвічі клац нути мишею на папці «..» або натиснути на клавішу «Васkspace».
На панелі інструментів відображаються кнопки ко манд, що відповідають режимам керування файлами й архівами.
У рядку стану знаходяться кнопки «Диск» (для зміни поточного диска) і «Ключ» (для введення пароля). За за мовчуванням значок ключа має жовтий колір, після вве дення пароля — червоний. У середній частині рядка ви водиться розмір виділених файлів або поточний стан, у правій — загальна кількість файлів у поточній папці та їхній розмір.
рис. 3.1 робоче вікно WinRar
2.2 WinZip
WinZip - це дуже популярний і зручний архіватор, створений фірмою Nico Mak Computing архівування інформації в операційних системах типу Windows. В даному посібнику розглянуто WinZip версії 8.1.
Архіватор WinZip працює в оболонці, вікно якої має інтерфейс схожий на Power Archiver але без панелі папок. Проте, архіватор WinZip може також працювати в режимі майстра WinZip (WinZip Wizard), який переважно використовують користувачі-початківці.
Крім цього, WinZip інтегрується в операційну систему Windows. Так після інсталяції архіватора в контекстних меню файлів і папок та в меню File вікна папки з'являється новий пункт Add to Zip який дозволяє поміщати дані об'єкти в ZIP-архіви. Якщо викликати контекстне меню на архівному файлі, то з'являється пункт Extract to... який здійснює його розархівування у вказану користувачем папку.
Виконання операцій з файлами в оболонці WinZip дуже схоже на відповідні дії в Power Archiver. Так, повністю ідентичний порядок створення, відкриття та розархівуваня архівів. Вікно Add у WinZip складається з однієї закладки і додатково містить опції:
• Store file names in 8.3 format - перетворювати довгі імена файлів при архівуванні в DOS-формат (8 - ім'я та 3 - розширення);
• Save full path info - заархівовувати файли із збереженням повних шляхів до них на диску;
• Reset archive attribute - знімати з файлів, що архівуються архівний атрибут.
Вікно Extract у WinZip містить наступні, відмінні від Power Archiver, опції:
• Use folder names - розархівовувати із збереженням структури заархівованих папок. Якщо опція не відмічена, то всі файли будуть розархівовані в одну папку;
• Open Explorer window - відкрити у Windows Explorer папку, куди будуть розархівовані вибрані файли.
Порядок перетворення архівного файлу в саморозархівовуваний ЕХЕ-файл, знищення файлів в архіві, встановлення коментарів, тестування на можливість розархівування та на наявність комп'ютерних вірусів у вказаних архіваторах повністю ідентичний.
Дещо відрізняється у WinZip операція розбиття архіву на томи. Для цього необхідно відкрити архівний файл і натиснути комбінацію клавіш Shift+H, або в пункті меню Action команда Split Появляється діалогове вікно, де у випадаючому списку Part size необхідно вказати розмір тома. При цьому можна вибрати один із стандартних розмірів (1,2М, 1,44М, 2,88М, ЗМ, 4М, 5М, 100М, 650М, 700М) або розмір заданий користувачем.
Для архівувавання файлів за допомогою майстра WinZip, необхідно у класичному вікні програми гнути комбінацію клавіш Shift+W або кнопку Wizard. Відкривається перше вікно майстра, де слід вибрати Next. В наступному вікні потрібно вибрати режим роботи:
• UnZip or install from an existing Zip files - розархівувати ZIP-архів або проінсталювати програму в архіві. Після натискування Next, відкривається вікно, де пропонується знайти архівні файли на ПК, в папці Favorite або на одному із вказаних дисків. Після вибору ОК виводиться список знайдених файлів, де необхідно відмітити потрібний для розархівування файл і натиснути Next. В останньому вікні слід натиснути кнопку Select different folder, вказати папку куди будуть розархівовуватись файли і вибрати Unzip Now;
• Update an existing Zip file - добавити файли до існуючого архіву. Після натискування Next відкривається вікно, де, як і в попередньому випадку, пропонується знайти існуючі архівні файли. У знайденому списку потрібно вибрати ім'я архівного файлу, до якого будуть добавлятись нові файли і натиснути Next. В наступному вікні необхідно натиснути кнопку Add files або Add Folders щоб вибрати, файли або папки, що слід заархівувати і натиснути Zip Now для початку процесу архівування;
• Create a new Zip file - створити новий файл архіву. Після натискування Next відкривається вікно, де слід вказати ім'я архіву та шлях до нього (можна скористатись кнопкою Browse) та знову вибрати Next. Відкривається вікно із кнопками Add files та Add Folders, які дозволяють вибрати файли та папки, що потрібно помістити в архів і кнопкою Zip Now для початку процесу архівування.
рис. 3.2 робоче вікно WinZip
3.ПРОЕКТНИЙ РОЗДІЛ
Для надійної роботи програми перш за все, слід забезпечити автономність і можливість повторного використання коду, який буде написаний. Для цього слід реалізувати алгоритм у вигляді процедури або набору процедур.
Далі, слід визначитися з основними процедурами, які нам потрібні при компресії/декомпресії даних. У загальному випадку, нас би влаштували, мабуть, всього дві процедури:
1) Кодування.
2) Декодування.
Але крім цього програма може видаляти вхідний та вихідний файл, має вбудований текстовий редактор для перегляду файлу,який архівують та зміни його,а також збереження.
3.1. Структури даних для методу Хаффмана
Проектування даних (тобто типів даних, місця зберігання і способу доступу) при створенні будь-якої програми є часто не менш важливою задачею, ніж розробка самого алгоритму. Правильно і ефективно спроектовані дані дозволять швидше написати код алгоритму і зробити цей код ефективнішим, зрозумілішим і безпомилковим.
Розглянемо можливу структуру даних для реалізації методу Хаффмана. Почнемо із задачі побудови і зберігання інформації про двійкове дерево.
Двійкове дерево методу Хаффмана (далі просто дерево) складається з вузлів. Максимальне можливе число вузлів дерева рівне подвоєній довжині повної початкової таблиці символів мінус 1. Для байта (0..255 — всього 256 різних значень) максимальне число вузлів дерева рівне 2(256 - 1 або 511 вузлів.
Оскільки при генерації дерева бажана максимальна швидкодія і розмір максимального дерева невеликий, то програма може розмістити статичний масив вузлів максимального розміру. Елементи масиву використовуватимуться для побудови дерева.
Оскільки для декодування необхідна інформація про дерево і бажано мінімального розміру (її доводиться записувати разом з кодованим буфером), то реально дані краще розмістити у вигляді двох масивів:
1) мінімальна частина, необхідна для декодування (див. типи даних
tNode, tNodes і масив Nodes);
2) допоміжні дані, необхідні для побудови дерева і обчислення коду (див. типи даних tNodeData, tNodesData і масив NodesData).
3.2. Швидший алгоритм побудови дерева
Можна будувати дерево ще швидше. Для цього слід звернути увагу на те, що вузли, що знову генеруються, з 256 по 511 (тобто нові вузли, які ми одержуємо послідовно об'єднуючи по два вузли з мінімальними частотами входжень) утворюють впорядковану за збільшенням частот входжень послідовність. Це дозволяє обмежитися сортуванням тільки базової послідовності вузлів з 0 по 255, а потім для вибору вузлів з мінімальними частотами входжень використовувати різновид сортування, який називається «сортування злиттям». У цьому варіанті порівнюються черговий вузол базової послідовності вузлів з 0 по 255 і черговий вузол послідовності вузлів, що знову генерується, з 256 по 511 і береться мінімальних з них. Для вибору двох вузлів потрібно тільки два порівняння, що явно менше, ніж необхідно порівнянь для сортування.
3.3. Алгоритм обчислення кодів Хаффмана
Обчислення кодів для елементів первинної таблиці (вузли 0..255) можна провести використовуючи або поле «посилання на наступний вузол» (прямий прохід по дереву від вершини до коріння), див. рис. 2.3, або рекурсивним проходом, використовуючи поля «посилання на попередній лівий вузол» і «посилання на попередній правий вузол».
Саме обчислення не представляє складності і розглядатися тут не буде, див. приклад обчислення в пункті 1.4. Після обчислення одержимо масив кодів для кожного з чисел початкової таблиці, як це показано на рис. 2.12.
Розмір даних, що виділяються під код Хаффмана, повинен забезпечувати зберігання:
1) Довжини коду.
2) Коду.
Код Хаффмана може займати від 1 біта (мінімальна довжина коду) до 256 біт (максимальна довжина коду), тобто необхідно зарезервувати 32 байти під зберігання коду.
3.4. Розмір і формат запису упакованих даних
Перш ніж приступати до кодування, після побудови дерева, розумно підрахувати майбутній розмір кодованих даних. Якщо розмір кодованих даних менше розмірів початкових даних, то можна буде приступити до кодування.
Розмір Sd кодованих даних (без дерева і допоміжної інформації) в байтах можна обчислити по формулі:
тут квадратні дужки означають взяття цілої частини числа, [X] = (ціла частина X). Розмір упакованого дерева St можна обчислити так:
тут (Число_вузлів_в_дереві - 256) - число вузлів, дані про які потрібно зберегти, 256 вузлів початкової таблиці зберігати непотрібно. Кожен вузол містить два посилання, максимальне посилання 511 або 9 біт, плюс відомості про довжину дерева — 8 біт.
Розмір допоміжних даних залежить від формату запису упакованих даних. Можна, наприклад, використовувати наступний формат для упакованого буфера: заголовок, упаковане дерево, упаковані дані, рис. 2.13.
Формат упакованих даних
Рис. 3.13
Заголовок (див. рис. 2.13) містить відомості про довжину упакованих даних, необхідні для їх прочитування і розпаковування. Розмір заголовка
Sh = 4 байти. (2.3)
Упаковане дерево може бути записане у форматі показаному на рис. 2.14.
Формат даних упакованого дерева
Рис. 2.14
Розмір дерева (кількість вузлів в дереві) записується в перші 8 біт, далі слідують відповідна кількість записів вузлів. Кожен вузол містить 18 біт, по 9 біт на посилання. Повна довжина упакованого дерева може бути обчислена по формулі (2.2).
Якщо сумарний розмір (див. формули (2.1), (2.2) і (2.3))
S = Sd + St + Sh, (2.4)
менше, ніж розмір початкових даних, то бажаний результат досягнутий — дані можуть бути упаковані.
3.5. Кодування даних
Для кодування даних необхідно два буфери:
1) Буфер з початковими даними.
2) Буфер для кодованих даних.
Оскільки розмір кодованих даних не перевищуватиме розмір початкових даних, то розумно в програмі виділити відразу два однакові буфери — один використовується як «буфер з початковими даними», а другий як «буфер для кодованих даних».
Перш за все в «буфер для кодованих даних» записують заголовок і упаковане дерево. Далі в «буфер для кодованих даних» записують кодовані дані, одержані з початкових даних. Процес кодування байта початкових даних складається з наступних кроків:
1) читання з «буфера з початковими даними» чергового байта;
2) вибір з кодової таблиці відповідного коду;
3) копіювання бітів вибраного коду в «буфер для кодованих даних».
4) копіювання бітів вибраного коду з «буфера для кодованих даних» в архів.
Схематично процес кодування байта початкових даних можна представити як це показано на рис. 2.15. Кодування повторюється для всіх байтів «буфера з початковими даними».
Тепер «буфер для кодованих даних» містить кодовані дані з повною довжиною S, яку можна обчислити по формулі (2.4). Кодовані дані можна записати у файл-архів, а в «буфер з початковими даними» рахувати нову порцію даних і продовжити архівацію.
Процес кодування байта початкових даних
Рис. 2.15
Тут слід помітити, що хоча початкові дані мають завжди фіксовану довжину, розмір кодованих даних може бути різним для різних початкових даних. Тому при збереженні кодованого буфера слід зберегти і відомості про його довжину. У нашому випадку (див. рис. 2.13) повна довжина кодованого буфера може бути прочитана із заголовка.
3.6. Декодування даних
Для декодування даних необхідно:
1) Буфер із кодованими даними.
2) Буфер для декодованих даних.
3) Дані по дереву.
Може показатися, що для декодування досить знання кодів Хаффмана. Але поглянувши на приклад кодів Хаффмана (див. (1.4)), стає очевидним, що пряме порівняння порції кодованих даних з кодами Хаффмана складне через різну довжину кодів. Хоча таке рішення проблеми декодування, мабуть, можливе.
Простіше використовувати наступний алгоритм декодування байта:
Відновлюється структура дерева в Nodes. Достатньо відновити посилання на вищерозміщені вузли, частотні дані для декодування не потрібні.
Поточним вузлом вибирається коріння дерева (n = IndexLast).
Прочитується один біт з файлу-архіву і записується в «буфер із кодованими даними», якщо біт рівний 1, то встановлюється поточним правий попередній вузол, інакше якщо біт рівний 0 — встановлюється поточним лівий попередній вузол.
Повторюється операція прочитування чергового біта кодованих даних і переміщення по дереву (див. крок 3), поки номер поточного вузла не стане менше 256.
Записується номер поточного вузла в «буфер для декодованих даних».
Повторюються операції з кроку 2), поки не декодуємо весь «буфер із кодованими даними».
4. ІНТЕРФЕЙС ПРОГРАМИ
рис.4.1 Головне вікно
рис.4.2 Вбудований текстовий редактор
рис.4.3 вікно про програму
5. ТЕКСТ ПРОГРАМИ
Unit_mzkit.cpp
#include <vcl.h>
#pragma hdrstop
#include "Unit2.h"
#include "Unit_mzkit.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
#include <stdio.h>
#include"Unit1_mzkit.h"
#include <string.h>
#include <math.h>
#define bool unsigned char
#define true 1
#define false 0
FILE *F,*F2;
long FileLength;
// Iмена вхiдного та вихiдного файлiв
char OutputFileName[20], InputFileName[20];
class TSymbol
{
public:
//Частота входження символа
unsigned long Freq;
// Символ i кiлькiсть бiтiв
unsigned char Ch, NumBits;
// Закодований символ в побiтовому записi
bool Bits[256];
void Init(void)
{
Freq = 0;
NumBits = 0;
for (int i = 0; i < 256; i++)
Bits[i] = 0;
Ch = 0;
}
// Перевантажений оператор присвоєння
TSymbol & operator =(TSymbol &S)
{
Freq = S.Freq;
NumBits = S.NumBits;
for (int i = 0; i < 256; i++)
Bits[i] = S.Bits[i];
Ch = S.Ch;
return *this;
}
// Функцiя встановлення бiта з заданим порядковим номером
void SetBit(bool bit)
{
Bits[NumBits] = bit;
NumBits++;
}
}*Alph[256];
// Вузол дерева Хаффмана
struct THuffmanNode
{
public:
// Вказiвник на батькiвський вузол
THuffmanNode *Parent;
// Частота входження
unsigned long Freq;
bool Bit;
// Конструктор
THuffmanNode(int f = 0)
{
Parent = NULL;
Freq = f;
Bit = false;
}
// Функцiя об'єднання вузлiв
THuffmanNode *Merge(THuffmanNode *N)
{
if (Freq > N->Freq)
{
Bit = true;
N->Bit = false;
}
else
{
Bit = false;
N->Bit = true;
}
// Створюємо новий вузол зi значенням, рiвним Freq + N->Freq
Parent = new THuffmanNode(Freq + N->Freq);
N->Parent = Parent;
return Parent;
}
};
unsigned char b;
int NumSymbols;
// Функцiя пiдрахунку частот входження символiв
void CalcFreqs(void)
{
int i, j;
NumSymbols = 0;
fseek(F, 0, 0);
// Читаємо файл по символу
for (i = 0; i < FileLength; i++)
{
fread(&b, 1, 1, F);
for (j = 0; j < NumSymbols; j++)
// Збiльшуємо лiчильник кiлькостi входжень для даного символа
if(b == Alph[j]->Ch)
{
Alph[j]->Freq++;
break;
}
// Якщо символ ще не зустрiчався до цього часу - заносимо його до алфавiту
if(j >= NumSymbols)
{
Alph[j] = new TSymbol();
Alph[j]->Init();
NumSymbols++;
Alph[j]->Ch = b;
Alph[j]->Freq++;
}
}
bool Sorted = false;
TSymbol Temp;
// Впорядковуємо алфавiт за спаданням частот
while(!Sorted)
{
Sorted = true;
for (i = 1; i < NumSymbols; i++)
if (Alph[i-1]->Freq < Alph[i]->Freq)
{
Temp = *Alph[i];
*Alph[i] = *Alph[i-1];
*Alph[i-1] = Temp;
Sorted = false;
}
}
}
// Функцiя кодування за алгоритмом Хаффмана
void CodeHuffman(void)
{
THuffmanNode *Tree[550], *Min1, *Min2, *Curr;
int i, j, t, NumNodes = NumSymbols;
// Створюємо вузли для дерева Хаффмана
for (i = 0; i < NumSymbols; i++)
Tree[i] = new THuffmanNode(Alph[i]->Freq);
// Впорядковуємо вузли iєрархiчно, утворюючи дерево
for(;;)
{
Min1 = Min2 = NULL;
for (i = 0; i < NumNodes; i++)
if (Tree[i]->Parent == NULL)
{
if (Min1 == NULL || Tree[i]->Freq < Min1->Freq)
{
if (Min2 == NULL || Min1->Freq < Min2->Freq) Min2 = Min1;
Min1 = Tree[i];
}
else
if(Min2 == NULL || Tree[i]->Freq < Min2->Freq) Min2 = Tree[i];
}
if (Min2 == NULL)
{
if (Min1)
Min1->Bit = true;
break;
}
Tree[NumNodes++] = Min1->Merge(Min2);
}
// Присвоюємо кожному символу його власний код Хаффмана
for (i = 0; i < NumSymbols; i++)
{
Alph[i]->NumBits = 0;
Curr = Tree[i];
do
{
Alph[i]->SetBit(Curr->Bit);
Curr = Curr->Parent;
}
while(Curr->Parent);
for (j = 0; j < Alph[i]->NumBits / 2; j++)
{
t = Alph[i]->Bits[j];
Alph[i]->Bits[j] = Alph[i]->Bits[Alph[i]->NumBits - j - 1];
Alph[i]->Bits[Alph[i]->NumBits - j - 1] = t;
}
}
// Видаляємо тимчасовi вузли
for (i = 0; i < NumNodes; i++)
if(Tree[i])
delete Tree[i];
}
// Функцiя стиснення даних
void Compress(void)
{
int i, j, k, N, t, HeaderOffset;
unsigned char mask, byte;
// Вiдкриваємо вихiдний файл для запису
FILE *OF = fopen(OutputFileName, "wb+");
if (OF == NULL)
{
perror(OutputFileName);
return;
}
fseek(OF, 0, 0);
fwrite(&FileLength, sizeof(long), 1, OF);
// Записуємо iнформацiю для розкодування:
// символи алфавiту та коди, що їм вiдповiдають
fwrite(&NumSymbols, 1, 1, OF);
for (j = 0; j < NumSymbols; j++)
{
fwrite(&Alph[j]->Ch, 1, 1, OF);
fwrite(&Alph[j]->NumBits, 1, 1, OF);
N = (Alph[j]->NumBits > 0) ? Alph[j]->NumBits : 256;
if (N % 8)
N = ((int)(N / 8) * 8) + 8;
b = 0; t = 0;
for (i = 0; i < N; i++)
{
b <<= 1;
if(Alph[j]->Bits[i]) b |= 1;
t++;
if(t >= 8)
{
fwrite(&b, 1, 1, OF);
t = 0; b = 0;
}
}
if(t > 0) fwrite(&b, 1, 1, OF);
}
HeaderOffset = ftell(OF);
mask = 1;
byte = 0;
fseek(F, 0, 0);
// Записуємо закодованi данi в вихiдний файл
for(i = 0; i < FileLength; i++)
{
fread(&b, 1, 1, F);
for(j = 0; j < NumSymbols; j++)
if (Alph[j]->Ch == b)
{
for (k = 0; k < Alph[j]->NumBits; k++)
{
if (mask == 0)
{
mask = 1;
fwrite(&byte, 1, 1, OF);
byte = 0;
}
if (Alph[j]->Bits[k])
byte |= mask;
mask <<= 1;
}
break;
}
// Якщо j бiльше нiж кiлькiсть символiв у файлi - помилка кодування
if (j >= NumSymbols)
{
ShowMessage("Помилка при кодуваннi файлу");
fclose(OF);
return;
}
}
fwrite(&byte, 1, 1, OF);
fseek(OF, 0, 2);
ShowMessage("файл закодовано");fclose(OF);
}
// Функцiя декодування
void Decompress(void)
{
int i, j, k, n, NumBits;
long NewFileLength;
bool SymbolFound;
bool Buffer[512];
// Вiдкриваємо файл для запису
FILE *OF = fopen(OutputFileName, "wb+");
if(OF == NULL)
{
perror(OutputFileName);
return;
}
// Зчитуємо iнформацiю для розкодування
// та записуємо алфавiт в пам'ять
fseek(F, 0, 0);
fread(&NewFileLength, sizeof(long), 1, F);
fread(&NumSymbols, 1, 1, F);
NumSymbols = (NumSymbols > 0) ? NumSymbols : 256;
for (j = 0; j < NumSymbols; j++)
{
if (!Alph[j])
Alph[j] = new TSymbol();
fread(&Alph[j]->Ch, 1, 1, F);
fread(&Alph[j]->NumBits, 1, 1, F);
n = Alph[j]->NumBits / 8;
if (Alph[j]->NumBits % 8)
n++;
for (i = 0; i < n; i++)
{
fread(&b, 1, 1, F);
for (k = 0; k < 8; k++)
{
if (b & 1)
Alph[j]->Bits[i * 8 + 7 - k] = true;
else
Alph[j]->Bits[i * 8 + 7 - k] = false;
b >>= 1;
}
}
}
fseek(OF, 0, 0);
NumBits = 0;
// Розкодовуємо iнформацiю згiдно з алфавiтом кодiв
for (i = ftell(F); i < FileLength; i++)
{
fread(&b, 1, 1, F);
for (j = NumBits; j < NumBits + 8; j++)
{
if (b & 1)
Buffer[j] = true;
else
Buffer[j] = false;
b >>= 1;
}
NumBits += 8;
while (NumBits >= 256)
{
for (j = 0; j < NumSymbols; j++)
{
SymbolFound = true;
for (k = 0; k < Alph[j...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора