Теоретичні відомості

⇐ ПредыдущаяСтр 4 из 11Следующая ⇒

Лабораторна робота № 2

Тема:Побудова дерева Хаффмана.

Мета:Скласти програму побудови дерева Хаффмана.

Теоретичні відомості

Бінарне дерево — це упорядковане дерево степеня 2, що має додатково дві властивості:

1) воно може бути пустим, не маючи жодного вузла;

2) будь-який вузол може мати другого сина (правого) за відсутності першого (лівого).

Обхід двійкових дерев в прямому та оберненому порядках в точності відповідає таким же обходам звичайних дерев.

При симетричному обході двійкового дерева з коренем n, лівим піддеревом Т₁ та правим піддеревом Т₂, спочатку проходять піддерево Т₁, потім корінь n, далі піддерево Т₂.

Представлення двійкових дерев:

Якщо іменами вузлів двійкового дерева є номери 1,2,..., n, то структурою для представлення цього дерева буде масив cellspace записів з полями leftchild (лівий син) і rightchild (правий син), оголошений наступним чином:

var

cellspace: array [1..maxnodes] of record;

leftchild: integer;

rightchild: integer

end;

В цьому представленні cellspace [i]. leftchild є лівий син вузла і, а cellspace [i]. rightchild – правий син. Значення 0 в обох полях вказує на те, що вузол і немає синів.

Прикладом застосування двійкових дерев в якості структур даних служить задача конструювання кодів Хаффмана. Для цього припускаємо, що маємо повідомлення, які складаються з послідовності символів. В кожному повідомленні символи незалежні і з’являються з відомою ймовірністю, що не залежить від позиції в повідомленні.

Задача конструювання кодів Хаффмана полягає в наступному: маючи множину символів і значення ймовірностей їх появи в повідомленнях, побудувати такий код з префіксною властивістю, щоб середня довжина коду (у імовірнісному сенсі) послідовності символів була мінімальною. Потрібно мінімізувати середню довжину коду для того, щоб зменшити довжину ймовірного повідомлення (тобто, щоб стиснути повідомлення). Чим коротше середнє значення довжини коду символів, тим коротше закодоване повідомлення.

Спосіб знаходження оптимального префіксного коду називається алгоритмом Хаффмана. В цьому алгоритмі знаходяться два символи a і b з найменшими ймовірностями появи та замінюються одним фіктивним символом, наприклад х, який має ймовірність появи, рівну сумі ймовірностей появи символів a і b. Потім, використовуючи цю процедуру рекурсивно, знаходимо оптимальний префіксний код для меншої множини символів ( де символи a і b замінені одним символом х). Код для вихідної множини символів одержується з кодів замінених символів шляхом додавання 0 і 1 перед кодом символу, який замінюється, і ці два нових коди приймаються як коди замінених символів. Наприклад, код символу а буде відповідати коду символу х з доданим нулем перед цим кодом, а для коду символу b перед кодом символу х буде додана одиниця.

Можна розглядати префіксні коди як шляхи на двійковому дереві: проходження від вузла до його лівого сина відповідає 0 в коді, а до правого сина –– 1. Якщо ми помітимо листки дерева кодованими символами, то одержимо представлення префіксного коду у вигляді двійкового дерева. Префіксна властивість гарантує, що немає символів, які були би мітками внутрішніх вузлів дерева (не листків), і навпаки, помічаючи кодованими символами тільки листки дерева, ми забезпечуємо префіксну властивість коду цих символів.

Для реалізації алгоритму Хаффмана ми використовуємо ліс, тобто сукупність дерев, чиї листки будуть помічені символами, для яких розробляється кодування, а корені помічені сумою ймовірностей всіх символів, які відповідають листкам дерева. Ми будемо називати ці сумарні ймовірності вагою дерева. Спочатку кожному символу відповідає дерево, що складається з одного вузла, вкінці роботи алгоритму ми одержимо одне дерево, всі листки якого будуть помічені кодованими символами. В цьому дереві шлях від кореня до будь – якого листка представляє код для символу – мітки цього листка, складеного по схемі, згідно з якою лівий син вузла відповідає 0, а правий –– 1.

Важливим етапом в роботі алгоритму є вибір з лісу двох дерев із найменшими вагами. Ці два дерева комбінуються в одне з вагою, рівною сумі ваг складових дерев. При злитті дерев створюється новий вузол, який стає коренем об’єднаного дерева і який має в якості лівого і правого синів коренів старих дерев. Цей процес продовжується до тих пір, поки не утвориться одне дерево. Це дерево відповідає коду, який при заданих ймовірностях має мінімально можливу середню довжину.

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒