Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз та реалізація стиснення даних за допомогою алгоритму Хафмана та його модифікацій
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Проблемно-орієнтовані методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Курсова робота
з курсу: “Методи та засоби комп’ютерних інформаційних технологій”
на тему:
“ Аналіз та реалізація стиснення даних за допомогою алгоритму Хафмана та його модифікацій ”
Львів 2011
Анотація.
Гусак В.В. “ Аналіз та реалізація стиснення даних за допомогою алгоритму Хафмана та його модифікацій ”. Курсова робота. – НУ „Львівська політехніка”, каф.: САПР, дисципліна:
“ Методи та засоби комп’ютерних інформаційних технологій ”, 2011.
Курсова робота складається з сторінок, таблиці, рисунків, 1 додатка.
В даній курсовій роботі проаналізовано основні принципи стиснення даних за допомогою алгоритму Хаффмана. Також було розроблено програмну реалізацію методу Хаффмана.
Завдання до курсової роботи
Тема курсової роботи: “ Аналіз та реалізація стиснення даних за допомогою алгоритму Хафмана та його модифікацій "
Постановка задачі:
Проаналізувати методи стиснення даних за допомогою методу Хаффмана та його модифікацій Розробити програмну реалізацію методу стиснення даних за допомогою алгоритму Хаффмана.
Термін здачі: 05.02.11.
Зміст
Вступ
Кодування Шенона-Фано
Метод стиснення Хаффмана
Модифікований метод Хаффмана
Постановка задачі та опис алгоритму
4.1. Алгоритм виконання стиснення методом Хаффмана
4.2. Алгоритм побудови дерева Хаффмана
5.Блок-Схема алгоритму
6.Приклад роботи програми
Висновок
Список використаної літератури
Додаток
Вступ
Ефективна організація обміну інформацією придає все більше значення передусім успішній практичній діяльності людей. Обсяг інформації, необхідної для нормальн ого функціонування сучасного суспільства, росте приблизно пропорційно квадрату розвитку продуктивних сил. Частка робочої сили, зайнятої питаннями забезпечення інформацією, в розвинених країнах починає перевищувати частку робочої сили, зайнятої безпосередньо в сфері виробництва. Застосування методів і коштів автоматизації на всіх етапах звертання інформації дозволяє істотно підвищити ефективність функціонування економіки країни і вивільнити значні трудові ресурси.
Хоч роль інформації може обмежуватися невизначеним емоційним впливом на людину, в чисто технічних (автоматичних) і людино-машинних (автоматизов аних) системах вона частіше за все використовується для вироблення впливу на продуктивність, що здійснюється або коштами інформаційної техніки, або людиною. Якщо процес обробки формалізуємо, він може виконуватися технічними засобами. У сучасних складних системах ці функції покладаються на ЕОМ і мікропроцесори. Якщо процес обробки не піддається формалізації і вимагає творчого підходу, обробка інформації здійснюється людиною. У системах управління най важливішою метою обробки є рішення задачі вибору керуючих впливів (етап прийняття рішення).
Етап відображення інформації повинен передувати етапам, пов'язаним з участю людини, надати людині потрібну йому інформацію за допомогою пристроїв, здатних впливати на його органи почуттів. На етапі такого впливу, інформація використовується для здійснення необхідних змін в системі.
Діяльність людини пов’язана з обробкою матеріалів, енергії та інформації. Відповідно розвиваються науково-технічні дисципліни, що розв’язують питання технології, енергетики, інформатики. Теорія інформації і інформаційна техніка ще порівняно молоді галузі, які отримали поштовх до розвитку з появою електронно-обчислювальних машин, електронних систем передачі інформації і систем автоматизованого керування. Тому центральне місце в теорії інформації займає створена Шеноном теорія зв’язку.
З розвитком технолог ій суспільства в 20 столітті сталася важлива для інформаційних систем переоцінка цінностей - різко зросла вартість продукту, на який до цього майже не звертали уваги - інформації, інформація стала одним з засобів виробництва. Тому була переглянута і структура інформаційних систем.
Найвразливішим місцем в інформаційній системі є канал зв'язку - на нього впливають непередбачувані природні події і до нього мають доступ сторонні особи. В результаті інформація може бути пошкоджена або до неї отримують доступ люди, що не мають на це повноважень. Можливі збитки від подібних ситуацій виправдовують встановлення засобів захисту інформації - систем завадостійкого кодування і шифрування.
В наш час, коли відбувається бурхливий розвиток інформаційних систем, надзвичайно гостро постала проблема передавання інформації по каналам зв'язку, і тепер ця проблема є актуальною не лише з академічної точки зору, адже все більше і більше ПК оснащуються модемами для обміну інформацією на відстані, все більше абонентів підключаються до всесвітньої мережі Internet, і вже не лише державні установи та великі корпорації, але й малі підприємства об'єднують свої комп'ютери в мережі. Відповідно до цього постійно збільшується кількість інформації, що передається по каналам зв'язку. Зрозуміло, ростуть вимоги й до інформаційних систем.
Ідеалом такої ІС є :
Якнайвища швидкість передачи даних
Абсолютна надійність передачі (гарантія цілісності даних)
Гарантія секретності інформації
Низька вартість передачі даних
Для підвищення показників ІС було розроблено багато засобів, які входять в ІС, деякі з них будуть реалізовані і в даному проекті, а саме : Для підвищення швидкості - оптимізуючи кодування, скремблювання. Для підвищення надійності - завадостійке кодування. Для підвищення секретності - шифрування і скремблювання.
1.Кодування методом Шеннона-Фано
Як відмічалося, в більшості випадків знаки повідомлень перетворюються в послідовності двійкових символів. У розглянутих пристроях це перетворення виконувалося без урахування статистичниххарактеристик поступаючих повідомлень.
Враховуючи статистичні властивості джерела повідомлення, можна мінімізувати середнє число символів, що вимагаються для вираження одного знаку повідомлення, що при відсутності шуму дозволяє зменшити час передачі або об'єм запам'ятовуючого пристрою.
Основна теорема Шеннона про кодування для каналу без перешкод. Ефективне кодування повідомлень для передачі їх по дискретному каналу без перешкод базується на теоремі Шеннона, яку можна сформулювати так:
1. При будь-якій продуктивності джерела повідомлень, меншій пропускній спроможності каналу, існує спосіб кодування, що дозволяє передавати по каналу всі повідомлення, що виробляються джерелом.
2. Не існує способу кодування, що забезпечує передачу повідомлень без їх необмеженого накопичення.
У основі доказу лежить ідея можливості підвищення швидкості передачі інформації по каналу, якщо при кодуванні послідовності символів ставити у відповідність не окремим знакам, а їх послідовностям такої довжини, при якій справедлива теорема об їх асимптотичній ймовірності. Зазначимо, що обмежуючись кодуванням типових. послідовностей, ймовірності яких рівні, ми забезпечуємо рівномірне і незалежне надходження символів на вхід каналу, що відповідає повному усуненню надмірності в повідомленні, що передається. Справедливість другої частини теореми, яка вказує на неможливість здійснення передачі виходить з визначення пропускної спроможності каналу як максимально досяжної швидкості передачі інформації, взятої по всій множині джерел заданого класу. Тому якщо пропускна спроможність каналу менше продуктивності джерела, то неминуче накопичення повідомлень на передаючій стороні.
Теорема Шеннона часто приводиться і в іншому формулюванні: повідомлення джерела з ентропією завжди можна закодувати послідовностями символів з об'ємом алфавіту m так, що середнє число символів на знак повідомлення буде як бажано близько до величини H(Z)/logm} але не менше за її.
Дане твердження влаштовується також вказівкою на можливу процедуру кодування, при якій забезпечується рівномірне і незалежне надходження символів на вхід каналу, а отже і максимальна кількість переносимої кожним з них інформації, рівне log m. Як ми встановили раніше, в загальному випадку це можливе, якщо кодувати повідомлення довгими блоками. Вказаний кордон досягається асимптотично, при безмежному збільшенні довжини блоків, що кодуються.
Теорема не вказує конкретного способу кодування, але з неї слідує, що при виборі кожного символу кодової комбінації необхідно старатися, щоб він ніс максимальну інформацію. Отже, кожний символ повинен приймати значення 0 і 1 по можливості з рівними ймовірностями і кожний вибір повинен бути незалежний від значень попередніх символів. Для випадку відсутності статистичного взаємозв'язку між знакам конструктивні методи побудови ефективних кодів були дані уперше американськими вченими Шенноном і Фано. Їх методики істотно розрізняються і тому відповідний код отримав звання коду Шеннона Фано.
Код будують таким чином: знаки алфавіту спілкування виписують в таблицю в порядку убування ймовірностей. Потім їх розділяють на дві групи так. Щоб суми ймовірностей в кожній з груп були можливості однакові. Всім знакам верхньої половини як і перший символ приписують 0, а всім нижнім 1. Кожну з отриманих груп, в свою чергу, розбивають на дві підгрупи з однаковими сумарними ймовірностями і т. д. Процес повторюється доти, поки в кожній підгрупі залишиться по одному знаку. З теореми Шеннона слідує, що цю надмірність також можна усунути, якщо перейти до кодування досить великими блоками.
Потрібно підкреслити, що збільшення ефективності кодування при укрупненні блоків не пов'язані з урахуванням все більш далеких статистичних зв'язків, оскільки нами розглядалися алфавіти з некоррельованими знаками. Підвищення ефективності визначається лише тим, що набір ймовірностей, що виходять при укрупненні блоків можна ділити на більш близькі по сумарних ймовірностях підгрупи.
Розглянута методика Шеннона-Фано не завжди приводить до однозначної побудови коду. Адже при розбиті на підгрупи можна зробити більшою по ймовірності як верхню, так і нижню підгрупи. Від вказаного недоліку вільна методика Хаффмана. Вона гарантує однозначну побудову коду з найменшим для даного розподілу ймовірностей середнім числом символів на букву.
Розглянувши методики побудови ефективних кодів, неважко пересвідчитися в тому, що ефект досягається завдяки привласненню більш коротких кодових комбінацій більш вірогідним знакам і більш довгих менш вірогідним знакам. Таким чином, ефект пов'язаний з відмінністю в числі символів кодових комбінацій.
А це приводить до труднощів при декодуванні. Звичайно, але для розрізнення кодових комбінацій можна ставити спеціальний розділовий символ, але при цьому , значно знижується ефект, якого ми домагалися, оскільки середня довжина кодової комбінації по суті збільшується на символ.
І більш доцільно забезпечити однозначне декодування без введення додаткових символів. Для цього ефективний код необхідно будувати так, щоб ні одна комбінація коду не співпадала з початком більш довгої комбінації. Коди, що задовольняють цю умову, називають префіксними кодами.
Як ми вже бачимо в більшості випадках повідомлення - це послідовності двійкових символів. В побудованій інформаційній системі перетворення відбувається без врахування статистичних характеристик вхідних повідомлень.
Враховуючі статистичні властивості джерела сигналу, можливо мінімізувати середню кількість двійкових символів необхідних для зображення одного символу з вхідного алфавіту, що при відсутності завад дозволяє зменшити час передачі або об’єм запам'ятовуючого пристрою. Таке оптимальне кодування базується на основній теоремі Шенона для каналів без завад.
Шенон довів, що нове повідомлення, складене з символів деякого алфавіту, можна закодувати так, що середня кількість двійкових символів на букву буде як завгодно близька до ентропії джерела повідомлення, але не менша за неї.
Основна проблема в тому, що теорема не описує конкретний спосіб кодування, але з неї випливає, що при виборі кожного символу кодової комбінації необхідно старатися, щоб він ніс максимальну інформацію. Тому кожний символ повинен приймати значення 0 і 1, по можливості з рівними ймовірностями і кожен вибір по можливості повинен бути незалежним від значення попередніх символів.
Для випадку відсутності статистичного зв'язку між буквами конструктивні методи побудови ефективних кодів вперше були запропоновані Шенноном і Фано. Їх методика майже не відрізняється і тому відповідний код отримав назву кода Шеннона-Фано.
Код будується наступним чином: букви алфавіту повідомлення записуються в таблицю в порядку зменшення ймовірності. Далі вони розділяються на дві групи так, щоб суми ймовірностей кожної групи були по можливості однакові.
Всім буквам верхньої половині в якості першого символу приписується 0, а всім нижнім - 1.Кожна з отриманих груп в свою чергу розбивається на дві підгрупи з однаковими сумарними ймовірностями і т.д. Процес продовжується доти, поки в кожній підгрупі не залишиться по одному символу. Розглянута методика не завжди призводить до однозначної побудови коду. Адже при розбитті на підгрупи можна зробити більшою за ймовірністю як верхню, так і нижню підгрупи. Від цього недоліку вільна методика Хаффмена. Вона гарантує однозначну побудову коду з найменшим можливим для даного розподілу ймовірностей середнім числом символів на букву.
Для двійкового коду методика зводиться до наступного: букви повідомлення виписуються в основний стовбець в порядку зменшення ймовірності. Дві останні букви об'єднують в одну допоміжну, якій приписують сумарну ймовірність. Ймовірності букв що не брали участь в об'єднанні і отримана сумарна ймовірність розміщаються в порядку зменшення ймовірності в додатковому стовпці, а дві останні об'єднуються. Так продовжується до тих пір, доки не отримуємо єдину, допоміжну букву з ймовірністю рівною одиниці.
Для побудови кодової комбінації необхідно прослідкувати шлях переходу повідомлення по стовпцям таблиці. Для наглядності будується кодове дерево. З точки, що відповідає ймовірності в 1, направляються дві гілки, причому гілці з більшою ймовірністю присвоюється символ 1. Таке послідовне розгалуження продовжується поки не дійдемо до ймовірностей окремих букв. Далі рухаючись по кодовому дереву зверху вниз можна записати для кожної букви відповідний код.
Розглянувши методику побудови ефективних кодів неважко побачити, що ефект досягається за рахунок присвоєння більш коротких кодових комбінацій символам з більшою ймовірністю. Це призводить до проблем при декодуванні, звичайно можна ставити спеціальний символ розділювач, але це знижує ефект через зростання довжини комбінації.
Більш доцільно забезпечити однозначне декодування без введення додаткових символів Для цього ефективний код треба будувати так, щоб жодна комбінація коду не співпала з початком довшої комбінації. Коди, які задовільняють цю умову називаються префіксними кодами. Наприклад:
01 101 100
Z1 Z2 Z3
буде декодуватися однозначно. Неважко переконатися, що коди отримані за методиками Шеннона-Фано і Хаффмана є префіксними.
2.Метод стиснення Хаффмана
Ідея, що лежить в основі коду Хаффмана, досить проста. Замість того, щоб кодувати всі символи однаковим числом біт (як це зроблено, наприклад, у ASCII кодуванню, де на кожен символ приділяється рівно по 8 біт), будемо кодувати символи, що зустрічаються частіше, меншим числом біт, чим ті, котрі зустрічаються рідше. Більш того, зажадаємо, щоб код був оптимальний або, іншими словами, мінімально-надлишковий.
Першим такий алгоритм опублікував Девид Хаффман (David Huffman) у 1952 році. Алгоритм Хаффмана двохпрохідний. На першому проході будується частотний словник і генеруються коди. На другому проході відбувається безпосереднє кодування.
Визначення 1: Нехай А= {а1, а2…,аn} — алфавіт з n різних символів, W={w1,w2,...,wn} - відповідний йому набір позитивних цілих ваг. Тоді набір бінарних кодів С={с1,с2,...,сn}, такий що:
(1) сi не є префіксом для сj , при i!=j
(2) мінімальна (|cі| довжина коду cj)
називається мінімально-надлишковим префіксним кодом або інакше кодом Хаффмана,
Зауваження:
Властивість (1) називається властивістю префіксності. Воно дозволяє однозначно декодувати коди перемінної довжини.
Суму у властивості (2) можна трактувати як розмір закодованих даних у бітах. На практиці це дуже зручно, тому що дозволяє оцінити ступінь стиску не прибігаючи безпосередньо до кодування.
Надалі, щоб уникнути непорозумінь, під кодом будемо розуміти бітовий рядок визначеної довжини, а під мінімально-надлишковим кодом або кодом Хаффмана - безліч кодів (бітових рядків), що відповідають визначеним символам і володіють визначеним властивостям.
Відомо, що будь-якому бінарному префіксному коду відповідає визначене бінарне дерево.
Визначення 2: Бінарне дерево, що відповідає кодові Хаффмана, будемо називати деревом Хаффмана.
Задача побудови коду Хаффмана рівносильна задачі побудови відповідного йому дерева. Приведемо загальну схему побудови дерева Хаффмана:
Складемо список кодуючи символів (при цьому будемо розглядати кожен символ як одноелементне бінарне дерево, вага якого дорівнює ваги символу).
Зі списку виберемо 2 вузли з найменшою вагою.
Сформуємо новий вузол і приєднаємо до нього, у якості дочірніх, два вузли обраних зі списку. При цьому вага сформованого вузла покладемо рівним сум ваг дочірніх вузлів.
Додамо сформований вузол до списку.
Якщо в списку більше одного вузла, то повторити 2-5.
Приведемо приклад: побудуємо дерево Хаффмана для повідомлення
S="AHFBHCEHEHCЕAHDCEEHHHCHHHDEGHGGЕНСНН".
Для початку введемо кілька позначень:
Символи кодуючого aлфавіту будемо виділяти жирним шрифтом: А, В, С.
Ваги вузлів будемо позначати нижніми індексами: А5, В3, С7.
Складені вузли будемо брати в дужки: ((А5+В3)8+С7)15.
Отже, у нашому випадку А= {А, В, С, D, Е, F, G, Н}, W={2,1,5, 2, 7, 1, 3, 15}.
А2 В1 C5 D2 E7 F1 G3 H15
A2 C5 D2 E7 G3 H15 (F1+В1)2
С5 Е7 G3 Н15 (F1+B1)2 (A2+D2)4
С5 Е7 Н15 (A2+D2)4 ((F1+B1)2 +G3)5
E7H15((F1+B1)2+G3)5 (C5+(A2+D2)4)9
H15 (C5+(A2+D2)4)9 (((F1 + B1)2 +G3) 5+E7)12
H15 ((C5+(A2+D2)4) 9+(((F1 + B1)2 +G3) 5+Е7)12)21
(((C5+(A2+D2)4)9+((( F1 + B1)2 +G3)5+Е7) 12)21+Н15)36
У списку, як і було потрібно, залишився тільки один вузол. Дерево Хаффмана побудоване. Тепер запишемо його в більш звичному для нас виді.
Листові вузли дерева Хаффмана відповідають символам кодованого алфавіту. Глибина листових вузлів дорівнює довжині коду відповідних символів.
Шлях від кореня дерева до листового вузла можна представити у виді бітового рядка, у якій "0" відповідає виборові лівого піддерева, а "1" -правого. Використовуючи цей механізм, ми без праці можемо присвоїти коди всім символам кодованого алфавіту. Випишемо, приміром, коди для всіх символів у нашому прикладі:
A=0010bin С=000 bin Е=011 bin G=0101 bin
B=01001bin D=0011 bin, F=01000bin H=l bin
Тепер у нас є все необхідне для того, щоб закодувати повідомлення S. Досить просто замінити кожен символ відповідної йому кодом:
S'="0010 1 01000 01001 1 000 011 1 011 1 000 011 0010 1 0011 000 011 011 1 1 1 000 1 1 1 0011 011 0101 1 0101 0101 011 1 000 1 1".
Оцінимо тепер ступінь стиску. У вихідному повідомленні S було 36 символів, на кожний з яких приділялося по [log2|A|]=3 біти (тут і далі будемо розуміти квадратні дужки [] як цілу частину, округлену в позитивну сторону, тобто [3,018]=4). Таким чином, розмір S дорівнює 36*3=108 біт.
Розмір закодованого повідомлення S' можна одержати скориставшись зауваженням 2 до визначення 1, або безпосередньо, підрахувавши кількість біт у S'. І в тім і іншому випадку ми одержимо 89 біт.
Отже, нам удалося стиснути 108 у 89 біт.
Тепер декодуємо повідомлення S'. Починаючи з кореня дерева будемо рухатися вниз, вибираючи ліве піддерево, якщо черговий біт у потоці дорівнює "0", і праве – якщо "1". Дійшовши до листового вузла ми декодуємо відповідний йому символ.
Ясно, що дотримуючись цього алгоритму ми в точності одержимо вихідне повідомлення S.
2.2 Модифікований метод Хаффмана
Визначення 3: Код Хаффмана D={d1, d2,...,dn} називається канонічним якщо:
Короткі коди (якщо їх доповнити нулями праворуч) чисельно більше довгих,
Коди однакової довжин чисельно зростають разом з алфавітом.
Далі, для стислості, будемо називати канонічний код Хаффмана просто канонічним кодом.
Визначення 4: Бінарне дерево, що відповідає канонічному кодові Хаффмана, будемо називати канонічним деревом Хаффмана,
Як приклад приведемо канонічне дерево Хаффмана для повідомлення S, і порівняємо його зі звичайним деревом Хаффмана.
Випишемо тепер канонічні коди для всіх символів нашого алфавіту в двійковій і десятковій формі При цьому згрупуємо символи по довжині коду.
B=00000bin=0dec А=0001bin=1dec C=010bin=2dec H=lbin=ldec F=00001bin=ldec D=0010 bin =2dec E=011bin=3dec
G=0011 bin =3dec
Переконаємося в тім, що властивості (1) і (2) з визначення 3 виконуються:
Розглянемо, наприклад, два символи: Е і G. Доповнимо код символу E=011bin=3dec (максимальна довжина коду - довжина_коду)=5-3=2 нулями праворуч: E'=011 00bin=12dec, аналогічно одержимо G'=0011 0bin=3dec. Видно що E'> G'.
Розглянемо тепер три символи: A, D, G. Усі вони мають код однієї довжини. Лексикографічно A<D<G. У такому ж відношенні знаходяться і їхні коди: 1<2<3.
Далі помітимо, що порядковий номер будь-якого листового вузла, на займаному їм рівні, чисельно дорівнює кодові відповідних йому символу. Це властивість канонічних кодів називають числовим (Numerical property).
Пояснимо вищесказане на прикладі. Розглянемо символ С. Він знаходиться на 3м рівні (має довжину коду 3). Його порядковий номер на цьому рівні дорівнює 2 з огляду на два не листових вузли ліворуч), тобто чисельно дорівнює кодові символу С. Тепер запишемо цей номер у двійковій формі і доповнимо його нульовим бітом ліворуч (тому що 2 представляється двома бітами, а код символу С трьома): 2dec=10bin=>0 10 bin. Ми одержали в точності код символу С.
Таким чином, ми прийшли до дуже важливого висновку: канонічні коди цілком визначаються своїми довжинами. Це властивість канонічних кодів дуже широко використовується на практиці. Тепер знову закодуємо повідомлення S, але вже за допомогою канонічних кодів:
Z'="0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1".
Таким чином, ми не змінили довжин кодів, розмір закодованого повідомлення не змінився: |S/|=|Z/|=89 біт.
Тепер декодуємо повідомлення Z', використовуючи властивості канонічних кодів.
Побудуємо три масиви: base[], symb[], offs[]. Де base[i] - кількість нелистових вузлів на рівні i; symb[] - перестановка символів алфавіту, відсортована по двох ключах: первинний - довжина коду, вторинний - лексикографічне значення; offs[i] - індекс масиву symb[], такий що symb[offs[i]] перший аркушевий вузол (символ) на рівні і.
У нашому випадку: base[0..5]={?, 1, 2, 2, 1, 0}, symb[0..7]={B, F, A, D, G, C, E, H}, offs[0..5]={?, 7, ?, 5, 2, 0}.
Приведемо кілька пояснень base[0]=? і offs[0]=? не використовуються, тому що немає кодів довжини 0, a offs[2]=? - т.к. на другому рівні немає листових вузлів.
Тепер приведемо алгоритм , декодування (CANONICAL_DECODE):
code = наступний біт з потоку, length = 1
Поки соdе <base[length]
сode = code <<1
code = code + наступний біт з потоку length = length + 1
3. symbol = symb[offs[length] + code - base [length]]
Іншими словами, будемо пересувати ліворуч у перемінну code біт за бітом із вхідного потоку, доти, поки code < base [length]. При цьому на кожній ітерації будемо збільшувати перемінну length на 1 (тобто просуватися вниз по дереву). Цикл у (2) зупиниться коли ми визначимо довжину коду (рівень у дереві, на якому знаходиться шуканий символ). Залишається лише визначити який саме символ на цьому рівні нам потрібний.
Припустимо, що цикл у (2), після декількох ітерацій, зупинився. У цьому випадку вираження (code - base [length]) суть порядковий номер шуканого вузла (символу) на рівні length. Перший вузол (символ), що знаходиться на рівні length у дереві, розташований у масиві symb[] по індексі offs[length]. Але нас цікавить не перший символ, а символ під номером (code - base [length]). Тому індекс шуканого символу в масиві symb[] дорівнює (offs[length| + (code - base [length])). Інакше кажучи, шуканий символ symbol=symb [offs [length] + code - base[length]].
Приведемо конкретний приклад. Користуючись викладеним алгоритмом декодуємо повідомлення Z'.
Z'="0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1"
Отже, ми декодуємо 3 перших символи: А, Н, F. Ясно, що дотримуючись цього алгоритму ми одержимо в точності повідомлення S.
Це, мабуть, найпростіший алгоритм для декодування канонічних кодів. До нього можна придумати масу удосконалень.
4. Постановка задачі та опис алгоритму
Дана курсова робота передбачає розробити програмний продукт, що повинен розв’язувати важливі питання в галузі стиснення даних методом Хаффмана..
Кодування Хафмана має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті. Таким чином не важко оцінити можливості даного методу та порівняти його з іншими алгоритмами. Наприклад: найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).
Алгоритм побудови дерева Хаффмана
Повернемося до алгоритму побудови дерева Хаффмана. На кожній ітерації ми робили лінійний пошук двох вузлів з найменшою вагою. Ясно, що для цієї мети більше підходить черга пріоритетів, така як піраміда (мінімальна). Вузол з найменшою вагою при цьому буде мати найвищий пріоритет і знаходитися на вершині піраміди. Приведемо цей алгоритм.
Включимо всі кодованні символи в піраміду.
Послідовно витягнемо з піраміди 2 вузли (це будуть два вузли з найменшою вагою).
Сформуємо новий вузол і приєднаємо до нього, у якості дочірніх, два вузли узятих з піраміди. При цьому вага сформованого вузла покладемо рівним сумі ваг дочірніх вузлів.
Включимо сформований вузол у піраміду.
Якщо в піраміді більше одного вузла, то повторити 2-5.
Будемо вважати, що для кожного вузла збережений покажчик на його батька. У кореня дерева цей покажчик покладемо рівним NULL. Виберемо тепер аркушевий вузол (символ) і дотримуючись збережених покажчиків будемo підніматися нагору по дереву доти, поки черговий покажчик не тане дорівнювати NULL. Остання умова означає, що ми добралися до кореня дерева. Ясно, що число переходів з рівня на рівень дорівнює глибині листового вузла (символу), а отже і довжині його коду. Обійшовши в такий спосіб усі вузли (символи), ми одержиимо довжини їхніх кодів.
Схема алгоритму
Контрольний приклад
Висновки
Ідея, що лежить в основі коду Хаффмана, досить проста. Замість того, щоб кодувати всі символи однаковим числом біт (як це зроблено, наприклад, у ASCII кодуванню, де на кожен символ приділяється рівно по 8 біт), будемо кодувати символи, що зустрічаються частіше, меншим числом біт, чим ті, котрі зустрічаються рідше. Більш того, зажадаємо, щоб код був оптимальний або, іншими словами, мінімально-надлишковий.
Першим такий алгоритм опублікував Девид Хаффман (David Huffman) у 1952 році. Алгоритм Хаффмана двохпрохідний. На першому проході будується частотний словник і генеруються коди. На другому проході відбувається безпосереднє кодування.
Варто відзначити, що за 50 років із дня опублікування, код Хаффмана нітрохи не утратив своїй актуальності і значимості. Так із упевненістю можна сказати, що ми зіштовхуємося з ним, у тій або іншій формі (справа в тім, що код Хаффмана рідко використовується окремо, частіше працюючи в зв'язці з іншими алгоритмами), практично щораз коли архівуєм файли, дивимося фотографії, фільми, посилаємо факс або слухаємо музику.
На сьогоднішній день існує близько 100 реалізацій методу стиснення даних Хаффмана і ще більше програмних реалізацій, що говорить про популярність і широко-використовуваність цього формату.
В даній курсовій роботі є програмно-реалізований метод стиснення даних за допомогою алгоритму Хаффмана.
При тестуванні програми я виявила, що програма є ефективною для стиснення текстових файлів, бо вхідний файл займав 268 байт, а закодований – 178 байт.
Список використаної літератури
«Самоучитель по С++»
Автор: Герберт Шилдт ; 2006 рік ; Видавництво : Санкт-Петербург
2)«Visual C++ 6»
Автор: С. Холзнер ; 2004 рік ; Видавництво: Санкт-Петербург
3)«Практикум по С++»
Автор: Глушков С.В. ; 2006 рік ; Видавництво: Харьков
4)«Математическая логика и теория алгоритмов»
Автор: Судоплатов С.В., Овчиннікова Є.В. ; 2004 рік ; Видавництво: Инфра-М
5) http://ru.wikipedia.org/wiki/Код_Хаффмана
Жураковський Ю.П., Полторак В.П. Теорія інформації та кодування: Підручник. – К.: Вища шк. 2001р.
Вернер. Основи кодування. – М.: Техносфера 2004 р.
Текст програми
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include "Unit1.h"
#define ALPH 256
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
FILE* fin;
AnsiString FN;
int tmp, i=0;
int symbol[ALPH];//ìàñèâ êîä-êîëè÷åñòâî âõîæäåíèé;
int symnum;//îáùåå êîëè÷åñòâî ñèìâîëîâ;
int alphnum;//êîëè÷åñòâî ðàçëè÷íûõ ñèìâîëîâ;
int symproc[ALPH][2];//ìàñèâ êîä ñèìâîëà, êîëè÷åñòî, âõîæäåíèÿ ñèìâîëà â òåêñò
int min1i, min2i;
AnsiString codefile, decodefile;
AnsiString tmps;
char* tmpc;
typedef struct telem
{
AnsiString code;//êîäîâå ñëîâî äèíàìû÷íîú äîâæèíè;
int symb;//êîä ñèìâîëó;
int numsymb;//êûëüêûñòü âõîäæåííÿ ñûìâîëûâ;
}Tdata;
Tdata donemas[ALPH];
typedef struct tspisokelem* tep;
struct tspisokelem
{
Tdata data;
tep left, right, next, prev;
};
tep root, nav, end, min1, min2, temp;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void makecode(tep &tree, AnsiString cod)
{
if(tree != NULL)
{
tree->data.code=cod;
makecode(tree->left, tree->data.code+"0");
makecode(tree->right, tree->data.code+"1");
}
}
void makemas(tep &tree)
{
if(tree != NULL)
{
if(tree->data.symb != NULL)
{
donemas[i].symb=tree->data.symb;
donemas[i].numsymb=tree->data.numsymb;
donemas[i].code=tree->data.code;
i++;
}
makemas(tree->left);
makemas(tree->right);
}
}
draw(tep &tree, TCanvas *canv, int x, int y, int i)
{
TLabel *lab, *lab2;
if(tree != NULL)
{
if(tree->data.symb == NULL)
{
canv->MoveTo(x+15, y+30);
canv->LineTo(x-i+15, y+70);
canv->MoveTo(x+15, y+30);
canv->LineTo(x+i+15, y+70);
lab2 = new TLabel(Form1);
lab2->Font->Name="Courier New";
lab2->Left=x+40;
lab2->Top=y+40;
lab2->Color=clLime;
lab2->Caption="1";
Form1->InsertControl(lab2);
lab2 = new TLabel(Form1);
lab2->Font->Name="Courier New";
lab2->Left=x-30;
lab2->Top=y+40;
lab2->Color=clLime;
lab2->Caption="0";
Form1->InsertControl(lab2);
}
canv->Ellipse(x, y, x+30, y+30);
lab = new TLabel(Form1);
lab->Font->Name="Courier New";
lab->Left=x+7;
lab->Top=y+7;
lab->Color=clLime;
lab->Caption=tree->data.numsymb;
if(tree->data.symb != NULL)
26.01.2013 21:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора