Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Стиснення інформації на основі ефективних кодів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2009
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Група:
КН-32
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет "Львівська політехніка"
Інститут комп'ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Курсова робота
з дисципліни:
“Методи та засоби комп'ютерних
інформаційних технологій”
на тему
Стиснення інформації на основі ефективних кодів
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Завдання на курсову роботу
з дисципліни “ Методи та засоби комп'ютерних
інформаційних технологій ”
Прізвище, ім’я студента Коліда Володимир
Група КН-312
Тема курсової роботи Стиснення інформації на основі ефективних кодів
Спеціальна частина завдання:
1.Розглянути класифікацію методів стиснення інформації.
2. Розробити алгоритм розвя’зку поставленої задачі.
3. Написати програму стиснення інформації на основі метотів Хаффмана та Шеннона-Фенно.
4. Термін завершення роботи – 30 січня 2009 р.
Завдання видано 8 жовтня 2008 р.
Керівник _____________________ Струк Є.С.
Студент______________________ Коліда В.С.
Зміст
1. Вступ_________________________________________________________ 4
2. Історія розвитку теорії стиснення інформації________________________ 5
3. Надлишковість та фактори, що її обумовлюють______________________ 8
4. Основні принципи та області застосування стиснення даних___________11
4.1 Стиснення даних в системах передачі інформації______________ 11
4.2 Стиснення даних як сукупність моделювання і кодування_______12
4.3 Архіватори, як інструмент стиснення інформації_______________14
5. Класифікація методів стиснення___________________________________15
6.Характеристики методів стиснення даних. Інформаційні характеристики дискретних джерел інформації_____________________________________16
7. Кодування Хаффмана____________________________________________20
8. Кодування Шеннона-Фано _______________________________________23
9. Постановка задачі_______________________________________________25
10. Алгоритм розв’язку задачі_______________________________________26
10.1 Алгоритм розв’язку задачі методом Шеннона-Фано___________ 26
10.2 Алгоритм розв’язку задачі методом Хаффмана_______________ 27
11. Програмна реалізація задачі_____________________________________ 28
12. Інструкція користувача_________________________________________ 29
13. Аналіз контрольних прикладів___________________________________ 30
Висновок___________________________________________________32
Список літератури___________________________________________ 33
Додатки:
Додаток 1. Текст файлу form_main.pas
Додаток 2. Текст файлу mat_code.pas
1. Вступ
У XXI столітті інформація має величезне значення. Для прийому, зберігання, передачі, обробки і видачі інформації частіше використовується не папір, а електронні носії, тому потрібне постійне удосконалення носіїв. Об'єм інформації збільшується з кожним днем і тому проблема зберігання даних не вирішиться тільки збільшенням пам'яті носіїв, потрібний зворотний процес - зменшення об'єму інформації, такий процес називається архівацією.
Ще в другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стиснення та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціанованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі.
Стиснення в даний час застосовується практично у будь-якій більш-менш складній системі, що оперує із значними обсягами даних – достатньо навести приклади архівування файлів, форматів аудіо- та відеоданих, які використовують стиснення (МР3, JPEG, GIF, PNG, AVI, MPEG і т.д.), а також цифрового зв’язку, зокрема мобільного. В мобільному зв’язку стандарту GSM швидкість передачі даних 13 кбіт/сек (із досить складним алгоритмом стиснення, який до того ж працює в реальному часі) забезпечує таку ж суб’єктивну якість звуку, як при передачі на швидкості 64 кбіт/сек без стиснення.
Отож стиснення інформації має досить велику роль в сучасних інформаційних системах таких як: бази даних, електронні бібліотеки, система інтернет-ресурсів та ін. І без попередньої обробки інформації було б неефективно використовувати інформаційний простір для її збереження.
2. Історія розвитку теорії стиснення інформації
Стиснення даних – це процедура представлення даних в більш компактній формі за рахунок усунення надлишковості з метою економії ресурсів систем передачі і зберігання інформації.
Ще в давні часи було виявлено, якщо вилучити з тексту всі голосні літери, то більшості випадків цей текст можна безпомилково відновити. Такий "метод стиснення даних" успішно застосовувався у ряді стародавніх складових та словесно-складових писемностей (фінікійська, палестинська, арамейська, шумерська, давньоєгипетська), де кожен символ писемності позначав склад "приголосна+довільна голосна". В давньоєврейській, арабській та санскритській писемностях для позначення голосних використовувались діакритичні значки (невеликі штрихи, гачки і крапки над основними літерами, що позначали приголосні). Це можна вважати першим випадком застосування принципу кодування високоймовірних символів більш короткими кодами порівняно із низькоймовірними. В повній мірі цей принцип вперше було розвинуто англійським вченим-винахідником Семюелом Морзе, який не тільки створив перший діючий телеграфний апарат, а й успішно вирішив задачу, що з’явилася одразу із появою цієї системи зв’язку обмеженої пропускної здатності – задачу ефективного кодування (інший термін для стиснення даних). У азбуці Морзе літери кодуються нерівномірним кодом, тобто довжина кодового слова тим більша, чим менша ймовірність появи символа. Коди, побудовані за таким принципом, не усувають інший вид надлишковості, пов’язаний із статистичними зв’язками між близько розташованими символами.
У 40-х роках вчені, що працювали в області інформаційних технологій, ясно зрозуміли, що можна розробити такий спосіб збереження даних, при якому простір буде витрачатися більш ефективно. Клод Шеннон, вивчаючи нюанси розходжень між семантикою (semantics) (що деяка сутність значить) і синтаксисом (syntax) (як деяка сутність виражається), розробив більшість базових понять цієї теорії. Розуміння того, що те саме значення (семантика) може бути реалізовано різними способами (синтаксис), приводить до закономірного запитання: "Який спосіб вираження чого-небудь є найбільш економічним?" Пошук відповіді на це питання привів Шеннона до думки про ентропію, кількість корисної інформації, що міститься у файлі. Методи стиску намагаються збільшувати ентропію файлу, тобто зменшувати довжину файлу, зберігаючи при цьому всю інформацію.
Однак, Шеннон не був першим, хто задумувався про сутність інформації і визначенні її кількості. Перший крок на цьому шляху зробив у 1928 р. Хартлі. Основний отриманий ними результат можна сформулювати приблизно так: якщо в заданій множині, що містить N елементів, виділений деякий елемент x, про яке відомо лише, що він належить цій множині, то щоб знайти x, необхідно одержати кількість інформації, рівне log2 N. Цю формулу звичайно називають формулою Хартлі.
Формула Хартлі є частковим випадком більш загальної формули Шеннона, що дозволяє знайти кількість інформації у випадковому повідомленні фіксованого алфавіту. Нехай X1, ..., Xn - символи цього алфавіту, P1, ..., Pn - ймовірності їхньої появи в тексті повідомлення, тоді формула Шеннона набуде вигляду:
H = P1*log2(1/ P1) + ... + Pn*log2(1/ Pn),
де H - кількість біт інформації в одному символі повідомлення, чи ентропія символу повідомлення. Це число показує мінімальне середнє число біт, необхідних для представлення одного символу алфавіту даного повідомлення.
У деяких випадках алфавіт повідомлення може бути невідомий, тоді висуваються гіпотези про алфавіт повідомлення. Маючи різні алфавіти, можна досягти різних коефіцієнтів стиснення. Наприклад, текстовий файл, якщо його розглядати як послідовність бітів, має ентропію порядку 0.7 - 0.9, якщо як послідовність байтів, - 0.5 - 0.7, хоча популярні програми стиску зменшують розміри текстових файлів до 0.3 - 0.4 від вихідного розміру.
Доказ Шеннона не був конструктивним, тобто не містив способу побудови цих оптимальних кодів, а лише показував їхнє існування. До появи роботи Шеннона, кодування символів алфавіту при передачі повідомлення по каналах зв'язку здійснювалося однаковою кількістю біт, одержуваною по формулі Хартлі. З появою цієї роботи почали з'являтися способи, що кодують символи різним числом біт у залежності від ймовірності їхньої появи у тексті. Наприклад, часто у файлах деякі значення байта зустрічаються частіше інших. Таким чином, за рахунок використання для кожного значення байта коду різної довжини можна значно зменшити загальний розмір даних. Ця базова ідея лежить в основі алгоритмів стиску Шеннона-Фано (Shannon-Fano) і Хафмана (Huffman). Подібні алгоритми вибирають більш короткі коди для байтів, які часто зустрічаються і більш довгі для байтів, які зустрічаються рідко. Звичайно текстові файли (у яких одні значення байтів повторюються набагато частіше інших) вони стискають досить добре.
Більш тридцяти років алгоритм стиснення Хафмана залишався найбільш популярними методом. Однак у 1977 два дослідники з Ізраїлю запропонували зовсім інший підхід до цієї проблеми. Абрахам Лемпел і Якоб Зів висунули ідею формування "словника" загальних послідовностей даних. При цьому стиснення даних здійснюється за рахунок заміни записів відповідними кодами зі словника. По сьогоднішній день цей метод застосовується у найбільш популярних програмах-архіваторах (WinRar, WinZip). Пізніше були створені методи контекстного моделювання та сортуючих перетворень, які вимагають значно більше обчислювальних ресурсів, ніж словникові, однак забезпечують для текстів на природній мові степінь стиснення, найбільш близьку до максимально можливої.
3. Надлишковість та фактори, що її обумовлюють
Стиснення даних можливе лише в тому випадку, коли вони містять надлишковість. Практично будь-які осмислені дані, що не були попередньо стиснуті, містять надлишковість, тобто можуть бути стиснені. Не можуть бути стиснутими лише дані, що носять абсолютно випадковий характер, з однаковою імовірністю появи всіх можливих символів (наприклад, результати експерименту по підкиданню правильної монети для великої кількості дослідів).
Значною надлишковістю володіють повідомлення на природній мові. Навіть якщо не братии до уваги смислову надлишковість (технічна реалізація усунення якої можлива хіба що за умови застосування апарату штучного інтелекту), статистична надлишковість, обумовлена різною імовірністю появи символів у тексті в залежності від контексту, складає близько 60%, тобто можна сказати, що на кожних 10 символів припадає 6 надлишкових.
Наявність надлишковості в символьних даних (тексти, коди програм, файли довільного вмісту) може бути обумовлена наступними причинами:
1) Різна імовірність появи символів. Безпосередньою причиною надлишковості є те, що символи кодуються однаковою кількістю біт, в той час як найбільш оптимально кодувати часто вживані символи коротшими комбінаціями, рідко вживані – довшими. Цей вид надлишковості наявний практично в будь-яких даних, що не були попередньо стиснуті, якщо тільки вони не є абсолютно випадковими з рівномірним законом розподілу.
2) Статистичний зв’язок між близько розташованими символами (повторення ланцюжків символів). Призводить до того, що повна імовірність появи символа залежить від того, які символи йому передують, тому оптимальна кількість біт для кодування символу залежить від контексту. Також характернний для більшості осмислених даних, оскільки, наприклад, для текстів характерна повторюваність окремих буквосполучень, для кодів програм – часто вживаних послідовностей команд і т.д.
3) Наявність довгих послідовностей однакових символів. Цей вид надлишковості, як буде показано пізніше, є частинним випадком попереднього, однак він найчастіше або з’являється в результаті роботи першої фази алгоритму стиснення, яка покликана усунути надлишковість типу 2) шляхом перетворення/перегрупування даних, або характерний для растрових зображень з великими однотонними полями.
Надлишковість даних аналогового походження (звук, зображення, результати вимірювань фізичних величин), окрім вищевказаних, може мати наступні причини:
1) Кореляція близьких у часі відліків. Аналогічно до 3) для символьних даних, однак для даних аналогового походження процедура передбачення наступного значення є дещо простішою і потребує менших обчислювальних затрат. Причиною надлишковості є те, що аналогова величина на протязі часу спостереження змінюється поступово, тому сусідні в часі значення є близькими за амплітудою. В більшості випадків поточне значення амплітуди може бути з певною похибкою передбачене на основі кількох попередніх значень, тому більш ефективним є кодування саме похибки передбачення, а не самої амплітуди.
2) Завищена роздільна здатність в окремих часових або частотних діапазонах порівняно із характеристиками отримувача інформації. Це характерно в основному для звуку і зображення і пов’язано з особливостями сприйняття інформації органами зору та слуху.
Найбільша степінь надлишковості – відповідно найбільша степінь стиснення та найбільший ефект від використання цієї процедури – характерна для зображень в растровому форматі, та, дещо меншою мірою, для оцифрованого звуку. Використання растрового формату (тобто коли зберігається колір кожної точки зображення) для відеофайлів призвело б до того, що середньостатистичний фільм заледве вмістився б на середньостатистичний вінчестер. Використання кодування форми сигналу без стиснення (тобто коли зберігається оцифроване значення амплітуди звуку в кожен момент часу, найчастіше із частотою дискретизації 44100Гц) призводить до того, що на компакт-диск можливо записати максимум 80 хвилин музики, в той час як при використанні формату МР3 – 5-10 годин чи більше (в залежності від степені стиснення).
Дані вимірювань в системах автоматизованого контролю та управління (оцифровані сигнали аналогових давачів) також містять надлишковість, зумовлену подібністю (близькістю) сусідніх відліків сигналу. Смуга частот, ширина якої загалом і визначає необхідний обсяг даних за одиницю часу, залежить від характеру фізичного процесу, а необхідна точність представлення визначається в першу чергу похибкою давача, а не суб’єктивними вимогами до якості сигналу.
4. Основні принципи та області застосування стиснення даних
4.1 Стиснення даних в системах передачі інформації
Особливо важливу роль відіграє стиснення при передачі даних. Стиснення даних може відбуватись вже на стадії аналого-цифрового перетворення – за рахунок вибору параметрів перетворення (частота дискретизації, інтервал квантування або характеристика квантувача) таким чином, щоб зменшити кількість інформації до мінімально необхідної для забезпечення заданого критерію якості.
Стиснення інформації може підвищувати стійкість систем шифрування (криптосистем), оскільки внаслідок зменшення надлишковості інформація після стиснення носить псевдовипадковий характер. Хоча хороші криптоалгоритми також дають на виході псевдовипадкову інформацію (тому шифрування і виконують після стиснення, а не навпаки), однак чим "випадковішими" є характеристики даних на вході криптосистеми, тим менше додаткової інформації надається криптоаналітику для зламування шифру. Наприклад, якщо використовується простий підстановочний шифр (кожна буква заміняється іншою буквою або символом) і кодується текст на природній мові, то криптоаналітику достатньо підрахувати ймовірності появи окремих символів та виділити часто вживані групи символів для того, щоб практично однозначно відновити невідомий шифр шляхом порівняння із відомими ймовірностями появи символів для даної мови. Якщо ж дані попередньо стиснути, то ймовірності появи символів будуть приблизно однаковими, і дешифрування можна буде здійснити тільки шляхом прямого
перебору всіх можливих варіантів, причому тільки тоді, коли відомий алгоритм стиснення. З останнього випливає, що стиснення може навіть відігравати роль шифрування - за умови, що алгоритм стиснення гарантовано не стане відомий криптоаналітику, або ж має достатньо велику кількість параметрів, сукупність яких може використовуватись в якості ключа шифру.
4.2 Стиснення даних як сукупність моделювання і кодування
Для реалізації алгоритму стиснення в більшості випадків необхідно знати істинні ймовірності появи символів на виході джерела інформації та його дійсну ентропію. Наприклад, якщо ймовірність появи деякого символа в деякий момент часу на виході джерела інформації складає 0.5, а його код утворюється виходячи із припущення про імовірність 0.25, то сформований код символу (за умови застосування оптимального алгоритму) буде 2-бітовим (log 2 0.25), в той час як дійсна оптимальна довжина коду символа повинна бути 1 біт (log 2 0.5).
Істинна структура джерела інформації, як правило, є прихованою, тому ймовірності можна оцінювати лише на основі деякої моделі джерела інформації.
У 1981р. Дж. Ріссанен і Г. Ленгдон запропонували концепцію, згідно якої процес стиснення розділяється на дві частини – моделювання і кодування (Рис. 4.1). Моделювання забезпечує передбачення ймовірності появи наступного символа (тобто модель описує статистичні властивості джерела інформації), а кодування – представлення цього символа -log 2 p(xі) бітами.
Рис. 4.1 Стиснення даних як сукупність моделювання і кодування
Ця структура найкраще описує так звані методи контекстного моделювання. В інших методах це розділення може бути неявним, або ж, якщо наперед відомі характеристики моделі і можна гарантувати, що вони не будуть суттєво змінюватися, моделювання здійснюється при проектуванні системи стиснення, а робота такої системи зводиться тільки до кодування. Однак такий підхід дає загальну уяву про одну з основних проблем стиснення – адекватне визначення статистичних характеристик джерела інформації. Чим точніша оцінка ймовірності появи символа, тим більше степінь стиснення наближається до максимально можливої. Кодування ж, як правило,не представляє проблеми, оскільки існує ряд методів, що дозволяють наблизити середню довжину кодового слова до оптимальної.
4.3 Архіватори, як інструмент стиснення інформації
При збереженні, резервному копіюванні інформації тощо, якої б місткості не були ваші диски, завжди бажано стиснути файли так, щоб вони займали якомога менше місця. Найпростіше це робиться за допомогою програм, які звуться архіваторами. Зауважимо, що ці програми не тільки стискають інформацію в окремому файлі, але й можуть поміщувати в один архів групу (звичайно, споріднених за якоюсь ознакою) файлів.
Існує багато архіваторів. Серед них найбільш відомі: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO. Останнім часом з'явилися програми, які, знаходячись у пам'яті комп'ютера резидентно, архівують та розархівують «на льоту» всі файли, з якими ви працюєте, що дозволяє суттєвим чином заощаджувати простір на жорсткому диску. Такі можливості надають, наприклад, утиліта dblspace операційної системи MS-DOS та програма DIET (T.Matsumoto, Японія).
Існує декілька методів стиснення інформації, що міститься у файлах. Мабуть, найпростішим із них є метод Хаффмана, який полягає у заміні стандартних 8-бітових ASCII-кодів бітовими рядками змінної довжини в залежності від частоти появи символу. До речі, легко зрозуміти, що у текстах найбільш часто зустрічається символ «пропуск», ASCII-код якого має номер 32. Можна поширити цю ідею на пари, трійки і т.д. символів. При цьому можна одержати суттєвий виграш. Дійсно, візьміть, наприклад, дві пари символів «по» та «хщ». Ви можете назвати безліч слів із першим сполученням. Спробуйте відшукати слово, яке містить ото «хщ»! А при стандартному ASCII-кодуванні на кожне зі сполучень витрачається порівну бітів. Серед інших методів, які широко застосовуються в архіваторах для стиснення інформації у файлах, назвемо лише метод Лемпела-Зіва.
Зауважимо, що комп'ютер не «розуміє» ніяких інших кодувань символів крім ASCII-кодування (чи споріднених кодувань). Тому перед використанням архівований файл повинен бути розархівованим!
5. Класифікація методів стиснення
Методи стиснення даних можна розділити на дві великі групи: стиснення без втрат та з втратами.
Методи стиснення з втратами використовуються переважно для звуку і зображень, тобто інформації, що сприймається органами чуття. При цьому розпакована інформація відтворює вихідну із спотвореннями, які або не відчуваються взагалі, оскільки лежать нижче порогу сприйняття, або можуть бути більш чи менш помітними в залежності від степені стиснення. При
цьому максимально можлива степінь стиснення – величина, суб’єктивно обумовлена вимогами отримувача інформації. Наприклад, для звукових файлів формату mp3 деяким не особливо вибагливим слухачам важко помітити різницю між бітрейтами 256 і 128 кбіт/с, хоча розмір файлу (відповідно і степінь стиснення) може відрізнятись в 1,5-2 рази. Формально можна обмежити допустиме стиснення умовою виконання деякого критерію якості, наприклад, щоб степінь спотворення не перевищувала деякої заданої величини.
При стисненні без втрат дані після розпакування посимвольно співпадають із первинними даними, що підлягали стисненню. Ці методи застосовуються насамперед для стиснення довільних цифрових даних в програмах-архіваторах, а також у деяких графічних форматах, при передачі
зображень по факсу і т.п.
Таблиця 5.1. Стиснення без втрат
Тип даних
Метод стиснення
кодування джерел без пам’яті (статистичне кодування)
нерівномірні префіксні коди (Шеннона-Фано, Хаффмена, Голомба)
арифметичне кодування
дані аналогового походження
диференційна імпульсно-кодова модуляція
дельта-модуляція
довільні цифрові дані
словникові методи
методи контекстного моделювання
методи з використанням сортуючих перетворень
зображення
кодування довжин повторів
6. Характеристики методів стиснення даних. Інформаційні характеристики дискретних джерел інформації
При виборі методу стиснення даних необхідно зважати на наступні характеристики:
- степінь стиснення (коефіцієнт стиснення);
- тип даних, для яких стиснення є максимальним;
- швидкість упаковки;
- швидкість розпаковки;
- необхідний об’єм пам’яті при упаковці;
- необхідний об’єм пам’яті при розпаковці;
- складність реалізації;
- можливість роботи в потоці (однопрохідність) – для систем передачі;
- степінь спотворення – для стискування з втратами.
В залежності від області застосування можуть висуватися різні вимоги до таких характеристик, як швидкодія та необхідний об’єм пам’яті при упаковці та розпаковці. Наприклад, для форматів зберігання графічних чи звукових файлів ці характеристики бажано мати мінімальними при розпаковці (для реалізації швидкого перегляду та відтворення), а при упаковці вони можуть бути і значними, якщо більше значення має якість стиснення, а не його швидкість. При застосуванні в системах передачі параметри швидкодії є критичними насамперед при стисненні (оскільки якщо швидкість генерування інформації джерелом буде вищою, ніж швидкість на виході ефективного кодера, інформація буде безповоротно втрачена), а якщо
отримувачем інформації на стороні приймача є людина (наприклад, при телефонній розмові) – то і при розпакуванні.
Для систем передачі важливою є також однопрохідність алгоритму стиснення, тобто можливість ефективного кодера видавати інформацію на вихід до закінчення обробки всього повідомлення: для дискретних джерел інформації – після надходження кожного наступного символу, для аналогових – після оцифрування кожного наступного значення або після обробки порівняно невеликого блоку інформації (тривалість якого є меншою, ніж допустима затримка передачі).
Складність реалізації алгоритму доцільно враховувати, якщо критичними параметрами є час та вартість розробки системи (а також кваліфікація програміста), особливо якщо степінь стиснення не набагато вища, ніж у методу, простішого в реалізації. Інколи доцільно розглянути і варіант використання існуючих програм чи бібліотек функцій архівування, якщо логіка побудови системи допускає таку можливість.
Основною характеристикою, що відображає ефективність методів стиснення, є коефіцієнт стиснення. Для дискретних даних він визначається як
(6.1)
де L, – обсяг відповідно нестиснутих та стиснутих даних. Тобто, наприклад, коефіцієнт стиснення 2 означає, що об’єм стиснутих даних складає половину від об’єму даних джерела. Чим більший коефіцієнт стиснення, тим більш ефективною є система стиснення даних.
Для багатьох методів стиснення результат роботи алгоритму повинен містити не лише стиснуті дані, а і певну кількість службової інформації, необхідної алгоритму розпаковки для коректного відновлення інформації, наприклад, кодову таблицю, кодове дерево, словник і т.д. В цьому випадку загальний коефіцієнт стиснення визначається як
Де Lсп - обсяг службової інформації
Для даних різних типів максимально можливий коефіцієнт стиснення може бути різним, тому ефективність застосування методу для конкретного типу даних можна визначити шляхом порівняння отриманого коефіцієнту стиснення із максимально можливим.
Для стиснення з втратами, як уже було вказано, максимально можлива степінь стиснення залежить від допустимої похибки відтворення. Чим менша допустима похибка, тим більше додаткової інформації слід зберігати і відповідно тим менший максимально можливий коефіцієнт стиснення.
Для стискування без втрат максимально можлива степінь стиснення визначається теоремою Шеннона для каналу без завад. У роботі Клода Шеннона "Математична теорія зв’язку" (1948) вона сформульована так:
Нехай ентропія джерела складає Н біт/символ, а пропускна здатність каналу зв’язку С біт/сек. Тоді існує такий спосіб кодування, що забезпечує середню швидкість передачі симв/сек, де ε - як завгодно мале. Не існує такого способу кодування, при якому швидкість передачі .
Абстрагуючись від каналу зв’язку, цю теорему можна сформулювати наступним чином:
Для будь-якого джерела інформації існує такий спосіб кодування, що середня кількість біт на символ λ буде як завгодно близькою до ентропії джерела Н. Не існує такого способу кодування, при якому λ < Н.
Нагадаємо, що ентропія дискретного джерела інформації з алфавітом Х={ x1 , x2,…,xк } відображає середню кількість інформації, що припадає на символ повідомлення і визначається як
(6.2)
де р(хі) – імовірність появи і-го символу
Величина І(хі) = -log2 p(xi) називається власною інформацією символу хі
і визначає оптимальну кількість біт, необхідну для кодування цього символу.
Надлишковість джерела інформації визначається як
Де Hmax = log2K – максимальна ентропія дискретного джерела без пам’яті з алфавітом із К рівноімовірних символів (дорівнює кількості біт на символ при кодуванні рівномірним двійковим кодом).
Величина - це максимально можливе значення коефіцієнту стиснення для джерела інформації з ентропією Н(Х). Оцінити ефективність методу стиснення можна шляхом порівняння реально отриманого коефіцієнту стиснення К, визначеного за (6.1), із Kmax. Коефіцієнт
стиснення можна оцінити і за співвідношенням середніх довжин кодового слова при рівномірному кодуванні (що дорівнює Нmax) та при вибраному методі:
Середня довжина кодового слова визначається як
де lі – довжина кодової комбінації для символу хі
За величиною λ можна оцінити надлишковість даних після стиснення:
Чим ближча надлишковість стиснених даних до нуля, тим більш ефективним є стиснення.
7. Кодування Хаффмана
Розглянемо статистичне кодування Хаффмана. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символу не є префіксом коду жодного іншого символу. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символу можна задати як шлях від кореня дерева до листа, що містить цей символ.
Нехай вхідний алфавіт складається з чотирьох символів: a, b, c, d, частоти яких відповідно дорівнюють 1/2, 1/4, 1/8, 1/8.
Кодування Хаффмана для цього алфавіту подається таблицею 7.1.
Символ
Частота
Вхідне кодування
Вихідне кодування
A
1/2
00
0
B
1/4
01
10
C
1/8
10
110
D
1/8
11
111
Таб. 7.1. Кодування Хаффмана.
Мал. 7.1. Дерево Хаффмана.
Наприклад, кодом ланцюжка abaaacb, поданого на вході як
00 01 00 00 00 10 01
буде
0 10 0 0 0 110 10
(проміжки додано для зручності читання). Отже, 14 біт на вході дали 11 біт на виході – стискання очевидне! На мал. 7.1 подано двійкове дерево Хаффмана для наведеного коду.
При використанні адаптивного кодування Хаффмана необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці.
Перевагами методу Хаффмана є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).
Кодування Хаффмана має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.
Недоліком кодування Хаффмана є залежність коефіцієнту стискання від близькості ймовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності імовірностей символів; алгоритм фактично “округляє” їх до 1/2!
Цю проблему можна частково вирішити за рахунок блокування вхідного потоку (тобто включення до розгляду нових символів вигляду “ab”, “abc”,..., де a, b, c – символи початкового алфавіту). Однак це не дозволяє повністю позбутися втрат (вони лише зменшуються пропорційно розміру блока) і призводить до стрімкого росту кодового дерева: якщо, наприклад, символами вхідного алфавіту є 8-бітові байти зі значеннями 0...255, то при блокуванні по два символи ми отримуємо алфавіт (і кодове дерево!) із 65536 символів, а при блокуванні по три – 16777216! Таким чином, зростають вимоги до пам’яті та час побудови дерева (а у випадку адаптивного кодування – і час поновлення дерева, а звідси і час стискання).
Втрати ж складатимуть у середньому 1/2 біт на символ при відсутності блокування, а за його наявності – 1/4 і 1/6 біт для блоків довжини 2 та 3 відповідно.
8. Кодування Шеннона-Фано
Кодування Шеннона-Фано є одним з найперших алгоритмів стиснення, який вперше сформулювали американські учені Шенон (Shannon) і Фано (Fano). Даний метод стиснення схожий з кодуванням Хаффмана, яке з'явилося на декілька років пізніше. Головна ідея цього методу - замінити символи, що часто зустрічаються, коротшими кодами, а послідовності, що рідко зустрічаються, довшими кодами. Таким чином, алгоритм грунтується на кодах змінної довжини. Для того, щоб декодер згодом зміг розкодувати стислу послідовність, коди Шеннона-Фано повинні володіти унікальністю, тобто, не дивлячись на їх змінну довжину, кожен код унікально визначає один закодований символ і не є префіксом будь-якого іншого коду.
Xі
Р(хі)
d
5/17
c
4/17
space
3/17
b
3/17
a
2/17
Розглянемо алгоритм обчислення коду Шеннона-Фано (для наочності візьмемо як приклад послідовність ''aa bbb cccc ddddd''). Для обчислення коду, необхідно створити таблицю унікальних символів повідомлення хі і їх ймовірностей p(хі), і відсортувати її в порядку спадання ймовірності символів.
Далі, таблиця символів ділиться на дві групи так, щоб кожна з груп мала приблизно однакову частоту по сумі символів. Першій групі встановлюється початок коду в ''0'', другий в ''1''. Для обчислення наступних біт коду символів, дана процедура повторюється рекурсивно для кожної групи, в якій більше одного символу. Таким чином для нашого випадку отримуємо наступні коди символів:
Символ
Код
d
00
c
01
space
10
b
110
a
111
Довжина коду sі в отриманій таблиці рівна int(-lg p(хі)), якщо символи вдалося розділити на групи з однаковою частотою, інакше, довжина коду рівна int(-lg p(хі)+ 1.
int(-lg p(хі) <= sі <= int(-lg p(xi) + 1
Використовуючи отриману таблицю кодів, кодуємо вхідний потік - замінюємо кожен символ відповідним кодом. Звичайно для розкодування отриманої послідовності, дану таблицю необхідно зберігати разом із стислим потоком, що є одним з недоліків даного методу. У стислому вигляді, наша послідовність набирає вигляду:
111111101101101101001010101100000000000
завдовжки в 39 біт. Враховуючи, що оригінал мав довжину рівну 136 біт, отримуємо коефіцієнт стискування ~28% - не так вже і погано. 9. Постановка задачі
Виходячи з теми курсової роботи та аналізі й узагальненнях , зроблених у процесі огляду літератури, тепер можна чітко сформулювати задачу , яка буде реалізована у даній роботі.
Задача, яку я розв’язую в курсовій роботі, належить до класу задач, пов’язаних із стисненням інформації.
Отже, програма буде виконувати стинення інформації. В основі її алгоритму буде кодування Хаффмана та кодування Шеннона-Фано. При виконанні задачі потрібно оцінити характеристики методів стиснення, до яких можна віднести середню довжину коду, коефіцієнт стиснення коду та довжину стислого повідомлення.
10. Алгоритм розв’язку задачі
10.1 Алгоритм розв’язку задачі методом Шеннона-Фано
Крок 1: Множину з N повідомлень, які кодуються, розташовують у порядку спадання ймовірностей;
Крок 2: Впорядковані за ймовірностями повідомлення розбивають, по можливості, на q ( кількість якісних значень в кодовому алфавіті) рівноймовірних груп;
Крок 3: Кожній з груп, завжди в одній і тій самій послідовності, присвоюють символи алфавіту q (всім повідомленням першої групи - першу якісну ознаку цього алфавіту, всім повідомленням другої групи - другу якісну ознаку тощо);
Крок 4: Створені групи розбивають, по можливості, на рівноймовірні підгрупи, кількість яких дорівнює або менша ніж q (якщо після розбивання в групі залишається одне повідомлення то подальший поділ стає неможливим);
Крок 5: Кожній з утворених підгруп присвоюють якісні ознаки з алфавіту q за кроком 3:
Крок 6: Розбивання та присвоєння ознак алфавіту q повторюють доти, поки після чергового поділу в утворених підгрупах залишиться не більш як одне повідомлення.
10.2 Алгоритм розв’язку задачі методом Хаффмана.
Крок 1: Множину із N повідомлень що кодуються розташовують у порядку спадання ймовірностей;
Крок 2: Останні N0 повідомлень ( 2<N0 < q ) об'єднують у нове повідомлення з ймовірністю, що дорівнює сумі ймовірностей об'єднуваних повідомлень;
Крок 3: Утворену множину ( N - N0 + 1 ) повідомлень розташовують у порядку спадання ймовірностей;
Крок 4: Об'єднують останні q повідомлень і впорядковують множину повідомлень у порядку спадання ймовірностей. Так діють доти, доки ймовірність чергового об'єднаного повідомлення не дорівнюватиме одиниці:
Крок 5: Будують кодове дерево, починаючи з кореня і гілкам цього дерева присвоюють якісні ознаки кодового алфавіту q.
Алгоритм побудови дерева Хаффмана:
Крок 1: Складемо список кодованих символів (при цьому розглядатимемо кожен символ як одноелементне бінарне дерево, вага якого дорівнює вазі символу);
Крок 2: Із списку виберемо 2 вузли з найменшою вагою (під вагою можна розуміти частоту використання символу — чим частіше використовується, тим більше вага);
Крок 3: Сформуємо новий вузол і приєднаємо до нього, як дочірні, два вузли вибраних із списку. При цьому вагу сформованого вузла покладемо рівною сумі дочірніх ваг;
Крок 4: Додамо сформований вузол до списку.
Крок 5: Якщо в списку більше одного вузла, то повторити кроки 2-5.
11. Програмна реалізація задачі
Загальна характеристика програм:
Мова програмування: Borland Delphi 7
Назва програми: mat1_var3_code
Назва модуля
Розмір, текстові рядки
Розмір, байти
Головний модуль
form_main.pas
128
4 037
Другорядний модуль
mat_code.pas
526
13 907
__________________________________________________________________
Призначення програми:
Цю програму розроблено для стиснення текстової інформації. Також її можна використовувати для знаходження ентропії вхідного тексту, побудови алфавіту вхідного тексту, знаходження ймовірності появи даного символу в тексті, визначення розміру та надлишковості тексту.
Вхідні дані програми:
Вхідними даними програми є будь-яка введена текстова інформація.
Вихідні дані програми:
Середня довжина коду.
Коефіцієнт відносної ефективності.
Коефіцієнт стиснення коду.
Довжина стислого повідомлення (біт).
Ймовірність появи символу.
Код символу.
Ентропія символу.
Надлишковість символу.
12. Інструкція користувача
Програма mat1_var3_code є надзвичайно зручною у користуванні. Щоб скористатися програмою потрібно виконати наступні дії:
Запустити програму mat1_var3_code.exe
У вказаний рядок ввести інформацію, яку необхідно стиснути.
(див. мал.12.1)
Вводимо інформацію, яку потрібно стиснути.
Мал. 12.1 Введення інформації для стиснення
13. Аналіз контрольних прикладів
Введемо вхідні дані так, щоб символи максимально повторювались у повідомленні. Нехай повідомлення буде наступним: КУКУШКА_КУКУШОНКУ_КУПИЛА_КАПЮШОН.
Подивимось на результуючі дані.
Метод стиснення Шеннона-Фано:
Метод стиснення Хаффмана:
Характеристика вхідної інформації:
Довжина повідомлення (символів): 32
Кількість символів алфавіту: 11
Ентропія повідомлення: 100,22557
Середня ентропія символу: 3,13205
Довжина символу при рівномірному кодуванні (біт): 4
Довжина повідомлення при рівномірному кодуванні (біт): 128
Абсолютна надлишковість в представленні повідомлення: 27,77443
Середня абсолютна надлишковість в представленні символу: 0,86795
Результати роботи програми:
Середня довжина коду: 3,18750
Коефіцієнт стиснення коду: 1,28404
Максимальний коефіцієнт стиснення коду: 1,36275
Довжина стислого повідомлення (біт): 102
Висновок
Я вважаю, що тема моєї курсової роботи є дуже актуальною в наш час, адже ми живемо зараз в “інформаційному” суспільстві. Інформація відіграє важливу роль в житті людини. Із розвитком людства обсяг інформації невпинно зростає, і тому потрібно весь час збільшувати кількість фізичних носіїв для її зберігання. Носії інформації під час їхнього експлуатування можуть пошкоджуватись, в разі чого виникає необхідність перезапису інформації на інший носій, щоб не втратити її.
Щоб кількість інформації збільшувався, а обсяг пам’яті, яку вона буде займати зменшувався, потрібно якимсь чином перетворювати її...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора