рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Використання дерев

Реферат Курсовая Конспект

Выберите учебное заведение

Використання дерев

Використання дерев - раздел Образование, Графи P Дерева Знаходять Широке Застосування При Реалізації Трансляторів, При Роботі ...

Дерева знаходять широке застосування при реалізації трансляторів, при роботі з арифметичними виразами, для створення і роботи з частотними словниками, в системах економічного кодування сповіщень, тощо.

КОДИ ХАФФМАНА.Це приклад, коли двійкові дерева використовуються в якості структур даних. Нехай маємо сповіщення, в якому символи незалежні і з’являються з відомими ймовірностями. Наприклад, в сповіщені є символи а, б, в, г, д, які з’являються в сповіщені з ймовірностями 0.12, 0.4, 0.15, 0.08 та 0.25, відповідно. Треба закодувати кожний символ так, щоб його код був префіксом коду усього сповіщення. Таке (префіксне) свойство дозволяє легко декодувати рядок з нулів та одиниць так, що послідовно вилучають префікси (коди символів) із цього рядка. Легко запропонувати такий код: а - 000, б - 001, в - 010, г - 011, д – 100. Для цього кода середня длина дорівнює 3.

А чи можна винайти інший код з меншою середньою довжиною? Дійсно, є код з префікс ним свойством, середня довжина чкого для даного приклада дорівнює 2.15. Спосіб винаходу оптимального префіксного коду називається алгоритмом Хаффмана. В цьому алгоритму спочатку знаходять два символа з найменшими ймовірностями їх появи і заміняють фіктивним символом, ймовірность якого визначається як сума ймовірностей знайдених двох символів (в нашому прикладі це символи а та д). Далі, з тих, що лишилися, знаходять символ з найменшою ймовірністю його появи і додають до фіктивного символа і т.д. На рис. 7. 36 показано етапи створення дерева Хаффмана.

Рис. 7.36. Етапи створення дерева Хаффмена

Спочатку вилучають символи а (0.12) та г (0.08), далі – в(0.15), потім - д (0.25), потім - б (0.40). Префіксні коди - це путі на дереві: путь від вузла до лівого сина відповідає 0 в коді, а до правого сина -1. Символи, що кодуються, в дереві Хаффмана розташовані тілько на листях, це забезпечує префіксне свойство кодів. В даному випадку символи а, б, в, г, д отримали відповідні коди: 1111, 0, 110, 1110, 10.

ЧАСТОТНІ СЛОВНИКИ.Дерева використовують для визначення того, які слова в тексті використовувалися і скільки разів. В цьому випадку у вузлі зберігаеться в якості ключа само слово і лічильник кількості його появ.

Для рішення такої задачі краще підходить дерево пошуку, що також називають лексикографічним деревом. Для кожного слова тексту виконуються такі дії:

- пошук слова в дереві,

- у разі його відсутності слово додається в новий вузол дерева, з лічильником, що дорівнює 1;

- У випадку, коли слово в дереві знайдено, його лічильник збільшується на 1.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Графи P

ДИНАМІЧНІ СТРУКТУРИ ДАНИХ R... Особливості динамічних структурP Лінійні зв язні списки P...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Використання дерев

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Особливості динамічних структур
Динамічні структури даних по визначенню характеризуються: Ø відсутністю фізичної суміжності елементів структури в пам'яті, Ø мінливістю і непередбачу

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

Застосування лінійних списків
Лінійні списки знаходять широке застосування в додатках, де непередбачені вимоги на розмір пам'яті, необхідної для збереження даних; велике число складних операцій над даними, особливо операцій

Основні поняття
Нелінійним розгалуженим списком є список, елементами якого можуть бути теж списки. Якщо один з покажчиків кожного елемента списку задає порядок зворотний до порядку, встановлюваному іншим покажч

Застосування списків
Найбільше впровадження списки знайшли у мові програмування LISP. LISP – це мова обробки списків. Усі дані в LISP представляються у вигляді списків, структура елемента списку включає

Логічна структура, визначення
Граф - це складна нелінійна багатозв’язна динамічна структура, що відображає властивості і зв'язки складного об'єкта і має наступні властивості: - на кожен елемент (вузол,

Машинне представлення орграфів
Існують два основних методи представлення графів у пам'яті ЕОМ: матричний, тобто масивами, і зв'язними нелінійними списками. Вибір методу представлення залежить від природи даних і операцій, вик

Алгоритми обробки графів
Алгоритми обробки графів аналогічні алгоритмам обробки нелінійних списків, до яких можуть бути віднесені графи. Як приклад приведемо програму, що знаходить найкоротший шлях між двом

Основні визначення
Дерево - це граф, що характеризується наступними властивостями: - існує єдиний елемент (вузол, вершина), на який не посилається ніякий інший елемент - який називається корене

Логічне представлення і зображення дерев
Мається ряд способів графічного зображення дерев (див. рис. 7.17). 1). Використання діаграм Венна, що наочно показують вкладеність піддерев. 2). Спосіб,

Бінарні дерева
Відрізняють m-арні дерева, тобто такі дерева в яких напівступінь виходу кожної вершини менше або дорівнює m (де m може дорівнювати 0,1,2,3 і т.д.). Якщо напівступінь виходу кожної вершини в точн

Типи бінарних дерев
Очевидно, що дерева, що складаються з n вершин, можуть бути побудовані по-різному. У залежності від того, як будуються дерева, розрізняють: ідеально збалансовані дерева, збалансовані і не збалан

Основні операції над деревами
Над деревами визначені наступні основні операції: - обхід дерева у визначеному порядку, - пошук вузла з заданим ключем, - додавання нового вузла, - видалення вуз