Перегляд вихідного коду сторінки Код Гаффмана

У Вас нема дозволу на редагування цієї сторінки з такої причини:

Ваша IP-адреса знаходиться в діапазоні, який заблоковано у всіх вікі Фонду Вікімедіа.

Блокування зроблено ‪EPIC‬. Причиною вказано Open proxy/Webhost: See the help page if you are affected.

Початок блокування: 08:48, 2 липня 2024
Закінчення блокування: 08:48, 2 липня 2025

Ваша поточна IP-адреса: 206.189.44.186. Заблокований діапазон — 206.189.32.0/20.

Будь ласка, додайте всі вказані подробиці до будь-яких запитів, які Ви будете робити. Якщо ви вважаєте, що вас заблокували помилково, ви можете знайти додаткову інформацію та інструкції в глобальній політиці Без відкритих проксі.

В іншому випадку, щоб обговорити блокування, будь ласка, опублікуйте запит на розгляд на Мета-вікі. Ви також можете надіслати електронний лист до VRT-черги стюардів за адресою stewards@wikimedia.org, вказавши усю вищезазначену інформацію.

Ви можете переглянути та скопіювати вихідний текст цієї сторінки:

'''Алгоритм Гаффмана''' (або '''коди Гафмена'''<ref name="mit">{{CLRS|chapter=16.3: Коди Гафмена}}</ref>)&nbsp;— [[Адаптивний алгоритм|адаптивний]] [[жадібний алгоритм]] оптимального [[префіксний код|префіксного]] кодування алфавіту з мінімальною надмірністю. Був розроблений аспірантом [[Массачусетський технологічний інститут|Массачусетського технологічного інституту]] [[Девід Гаффман|Девідом Гаффманом]] при написанні ним курсової роботи та надрукований в статті [[1952|1952 року]] «A Method for the Construction of Minimum-Redundancy Codes»<ref>{{Cite journal | last1 = Huffman | first1 = D. | authorlink1 = Девід Гаффман | title = A Method for the Construction of Minimum-Redundancy Codes | doi = 10.1109/JRPROC.1952.273898 | journal = [[Proceedings of the IRE]] | volume = 40 | issue = 9 | pages = 1098–1101 | year = 1952 | url = http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf | accessdate = 30 Вересня 2017 | archive-date = 15 Грудня 2010 | archive-url = https://web.archive.org/web/20101215184132/http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf }}</ref>. Нині{{Коли}} використовується в багатьох програмах стиснення даних [[Стиснення без втрат|без втрат]].

На відміну від [[Алгоритм Шеннона — Фано|алгоритму Шеннона&nbsp;— Фано]], алгоритм Гаффмана залишається завжди оптимальним і для [[вторинний алфавіт|вторинних алфавітів]] m<sub>2</sub> з більш ніж двома символами.

Цей метод кодування складається з двох основних етапів:
# Побудова оптимального кодового дерева
# Побудова відображення код-символ на основі побудованого дерева

== Кодування Гаффмана ==
Один з перших алгоритмів ефективного кодування інформації був запропонований 1952 року [[Девід Гаффман|Девідом Гаффманом]]. Ідея алгоритму така: знаючи ймовірності появи символів у повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілої кількості бітів. Символам з більшою ймовірністю ставляться у відповідність коротші коди. Коди Гаффмана володіють властивістю [[префіксний код|префіксності]] (тобто жодне кодове слово не є префіксом іншого), що дозволяє однозначно їх декодувати.

Класичний алгоритм Гаффмана на вході отримує таблицю частот з якими зустрічаються символи у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Гаффмана (Н-дерево).
# Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, яка може бути рівною або ймовірності, або кількості входжень символу у стиснене повідомлення.
# Вибираються два вільних вузли дерева з найменшими вагами.
# Створюється їхній батьківський вузол з вагою, рівною їх сумарній вазі.
# Вузол-батько додається в список вільних вузлів, а два його нащадки видаляються з цього списку.
# Одній дузі, котра виходить з вузла батька, ставиться у відповідність біт 1, інший&nbsp;— біт 0.
# Кроки, починаючи з другого, повторюються доти, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.
[[Файл:HuffmanCodeAlg.png|300px|міні|Кодування Гаффмана]]
Припустимо, у нас є наступна таблиця частот:
{| class="wikitable"
! 15 || 7 || 6 || 6 || 5
|-
| A || B || C || D || E
|}
Цей процес можна подати як побудову [[Дерево (теорія графів)|дерева]], корінь якого&nbsp;— символ з сумою ймовірностей об'єднаних символів, отриманий при об'єднанні символів з останнього кроку, його n<sub>0</sub> нащадків&nbsp;— символи з попереднього кроку і&nbsp;т.&nbsp;д.

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

Для даної таблиці символів коди Гаффмана будуть виглядати так:
{| Class = "wikitable"
! A || B || C || D || E
|-
| 0 || 100 || 101 || 110 || 111
|}

Оскільки жоден з отриманих кодів не є префіксом іншого, вони можуть бути однозначно декодовані при читанні їх з потоку. Крім того, найчастіший символ повідомлення А закодований найменшою кількістю біт, а найрідкісніший символ E&nbsp;— найбільшою.

При цьому загальна довжина повідомлення, що складається з наведених у таблиці символів, складе 87 біт (в середньому 2,2308 біта на символ). При використанні рівномірного кодування загальна довжина повідомлення склала б 117 біт (рівно 3 біти на символ). Зауважимо, що [[Інформаційна ентропія|ентропія]] джерела, яке незалежним чином породжує символи із зазначеними частотами, складає ~ 2,1858 біта на символ, тобто [[Надмірність інформації|надмірність]] побудованого для такого джерела коду Гаффмана, що розуміється, як відмінність середнього числа біт на символ від ентропії, становить менше 0,05 біта на символ.

Класичний алгоритм Гаффмана має ряд істотних недоліків. По-перше, для відновлення вмісту стиснутого повідомлення декодер повинен знати таблицю частот, якою користувався кодер. Отже, довжина стиснутого повідомлення збільшується на довжину таблиці частот, яка повинна надсилатися попереду даних, що може звести нанівець всі зусилля щодо стиснення повідомлення. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів по повідомленню: одного для побудови моделі повідомлення (таблиці частот і Н-дерева), іншого для власне кодування. По-друге, надмірність кодування обертається на нуль лише в тих випадках, коли ймовірності кодованих символів є оберненими степеням числа 2. По-��ретє, для джерела з ентропією, що не перевищує 1 (наприклад, для двійкового джерела), безпосереднє застосування коду Гаффмана позбавлене сенсу.

== Адаптивне стиснення ==

Адаптивне стиснення дозволяє не передавати модель повідомлення разом з ним самим і обмежитися одним проходом по повідомленню як при кодуванні, так і при декодуванні.

У створенні алгоритму адаптивного кодування Гаффмана найбільші складнощі виникають при розробці процедури поновлення моделі чергових символів. Теоретично можна було би просто вставити всередину цієї процедури повну побудову дерева кодування Гаффмана, однак, такий алгоритм стиснення мав би неприйнятно низьку швидкодію, оскільки побудова Н-дерева&nbsp;— це занадто велика робота і виконувати її при обробці кожного символу нерозумно. На щастя, існує спосіб модифікувати вже наявне Н-дерево так, щоб відобразити обробку нового символу.

Оновлення дерева при зчитуванні чергового символу повідомлення складається з двох операцій.

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

Друга операція&nbsp;— [[перестановка]] вузлів дерева&nbsp;— потрібна тоді, коли збільшення ваги вузла призводить до порушення властивості впорядкованості, тобто тоді, коли збільшена вага вузла стає більшою, ніж вага наступного за порядком вузла. Якщо і далі продовжувати обробляти збільшення ваги, рухаючись до кореня дерева, то дерево перестане бути деревом Гаффмана.

Щоб зберегти упорядкованість дерева кодування, алгоритм працює в такий спосіб. Нехай нова збільшена вага вузла дорівнює W+1. Тоді починаємо рухатися по списку у бік збільшення ваги, поки не знайдемо останній вузол з вагою W. Переставимо поточний і знайдений вузли між собою в списку, відновлюючи таким чином порядок у дереві (при цьому батьки кожного з вузлів теж зміняться). На цьому операція перестановки закінчується.

Після перестановки операція збільшення ваги вузлів продовжується далі. Наступний вузол, вага якого буде збільшена алгоритмом,&nbsp;— це новий батько вузла, збільшення ваги якого викликало перестановку.

== Переповнення ==
У процесі роботи алгоритму стиснення ваги вузлів у дереві кодування Гаффмана неухильно зростають. Перша проблема виникає тоді, коли вага кореня дерева починає перевищувати місткість комірки, в якій він зберігається. Як правило, це 16-бітове значення і, отже, не може бути більшим, ніж 65535. Друга проблема, яка заслуговує ще більшої уваги, може виникнути значно раніше, коли розмір найдовшого коду Гаффмана перевищує місткість комірки, яка використовується для того, щоб передати його у вихідний потік. Декодеру все одно, якої довжини код він декодує, оскільки він рухається зверху вниз по дереву кодування, вибираючи з вхідного потоку по одному біту. А кодер повинен починати від листа дерева і рухатися вгору до кореня, збираючи біти, які потрібно передати. Зазвичай для цього використовують змінну цілого типу і, коли довжина коду Гаффмана перевершує розмір цілого типу в бітах, настає переповнення.

Можна довести, що максимальну довжину код Гаффмана для повідомлень з одним і тим самим вхідним алфавітом матиме, якщо частоти символів утворюють [[послідовність Фібоначчі]]. Повідомлення з частотами символів, рівними числам Фібоначчі до Fib(18),&nbsp;— це відмінний спосіб випробувати роботу програми стиснення за Гаффманом.

== Масштабування ваг вузлів дерева Гаффмана ==

Беручи до уваги сказане вище, алгоритм поновлення дерева Гаффмана повинен бути змінений таким чином: при збільшенні ваги потрібно перевіряти її на досягнення допустимого максимуму. Якщо ми досягли максимуму, то необхідно «масштабувати» вагу, зазвичай поділивши вагу листка на [[Цілі числа|ціле число]], наприклад, 2, а потім перерахувавши ваги всіх інших вузлів.

Однак при діленні ваги навпіл виникає проблема, пов'язана з тим, що після виконання цієї операції дерево може змінити свою форму. Пояснюється це тим, що ми ділимо цілі числа і при діленні відкидаємо дробову частину.

Правильно організоване дерево Гаффмана після масштабування може мати форму, яка значно відрізняється від початкової. Це відбувається тому, що масштабування призводить до втрати точності нашої статистики. Але зі збором нової статистики наслідки цих «помилок» практично сходять нанівець. Масштабування ваги&nbsp;— досить дорога операція, оскільки вона призводить до необхідності заново будувати все дерево кодування. Але оскільки необхідність у ній виникає відносно рідко, то з цим можна змиритися.

''Виграш від масштабування''

Масштабування ваги вузлів дерева через певні інтервали дає несподіваний результат. Незважаючи на те, що при масштабуванні відбувається втрата точності статистики, тести показують, що воно призводить до кращих показників стиснення, ніж якщо б масштабування відкладалося. Це можна пояснити тим, що поточні символи стисненого потоку більше «схожі» на своїх близьких попередників, ніж на тих, які зустрічалися набагато раніше. Масштабування призводить до зменшення впливу «давніх» символів на статистику і до збільшення впливу на неї «недавніх» символів. Це дуже складно виміряти кількісно, але, в принципі, масштабування позитивно впливає на ступінь стиснення інформації. Експерименти з масштабуванням в різних точках процесу стиснення показують, що ступінь стиснення сильно залежить від моменту масштабування ваги, але не існує правила вибору оптимального моменту масштабування для програми, орієнтованої на стиск будь-яких типів інформації.

== Застосування ==

Стиснення даних Гаффмана застосовується під час стиснення фото- і відеозображень ([[JPEG]], стандарти стиснення [[Moving Picture Experts Group|MPEG]]), в [[архіватор]]ах ([[PKZIP]], [[LZH]] та інших), в протоколах передачі даних MNP5 і MNP7.

== Примітки ==
{{reflist}}

== Посилання ==
* [http://www.webcenter.ru/~xander/HuffmanCode/huffcode.html Код Гаффмана] ([http://web.archive.org/web/20070927224229/http://www.webcenter.ru/~xander/HuffmanCode/huffcode.html WebArchive])
* [https://web.archive.org/web/20060613060343/http://rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2001 Візуалізатор побудови дерева для m<sub>2</sub>=2]
* [http://algolist.manual.ru/compress/standard/huffman.php Стиск по алгоритму Гаффмана] {{Webarchive|url=https://web.archive.org/web/20130405073331/http://algolist.manual.ru/compress/standard/huffman.php |date=5 Квітня 2013 }} на algolist.manual.ru


{{refimprove|дата=грудень 2015}}
{{Алгоритм-доробити}}
{{ВП-портали|Програмування|}}
{{Методи стиснення даних}}

[[Категорія:Алгоритми стиснення без втрат]]
[[Категорія:Двійкові дерева]]

Шаблони, використані на цій сторінці:

Шаблон:Ambox (переглянути вихідний код) (захищено)
Шаблон:Asbox (переглянути вихідний код) (захищено)
Шаблон:CLRS (редагувати)
Шаблон:Category other (переглянути вихідний код) (захищено)
Шаблон:Cite book (переглянути вихідний код) (захищено)
Шаблон:Cite journal (переглянути вихідний код) (захищено)
Шаблон:Hlist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Icon (переглянути вихідний код) (захищено)
Шаблон:Ifempty (переглянути вихідний код) (захищено)
Шаблон:MetaPicstub (переглянути вихідний код) (захищено)
Шаблон:Navbox (переглянути вихідний код) (захищено)
Шаблон:Nobr (переглянути вихідний код) (захищено)
Шаблон:Refimprove (переглянути вихідний код) (частково захищено)
Шаблон:Reflist (переглянути вихідний код) (захищено)
Шаблон:Reflist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Webarchive (переглянути вихідний код) (захищено)
Шаблон:\ (переглянути вихідний код) (частково захищено)
Шаблон:Алгоритм-доробити (редагувати)
Шаблон:ВП-портали (переглянути вихідний код) (захищено)
Шаблон:Вступ до алгоритмів (редагувати)
Шаблон:Коли (переглянути вихідний код) (частково захищено)
Шаблон:МалПорталу (переглянути вихідний код) (захищено)
Шаблон:МалПорталу/шаблон (переглянути вихідний код) (захищено)
Шаблон:Методи стиснення даних (редагувати)
Шаблон:Не перекладено (переглянути вихідний код) (захищено)
Шаблон:Недостатньо джерел (переглянути вихідний код) (частково захищено)
Шаблон:Нп (переглянути вихідний код) (захищено)
Шаблон:Обговоріть шаблон на СО (переглянути вихідний код) (частково захищено)
Шаблон:Портали (переглянути вихідний код) (захищено)
Шаблон:Портали/+ (переглянути вихідний код) (захищено)
Модуль:Arguments (переглянути вихідний код) (захищено)
Модуль:Category handler (��ереглянути вихідний код) (захищено)
Модуль:Category handler/blacklist (переглянути вихідний код) (захищено)
Модуль:Category handler/config (переглянути вихідний код) (захищено)
Модуль:Category handler/data (переглянути вихідний код) (захищено)
Модуль:Category handler/shared (переглянути вихідний код) (захищено)
Модуль:Citation/CS1 (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/COinS (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Configuration (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Identifiers (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Utilities (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Whitelist (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/styles.css (переглянути вихідний код) (захищено)
Модуль:Date (переглянути вихідний код) (захищено)
Модуль:Icon (переглянути вихідний код) (захищено)
Модуль:Icon/data (переглянути вихідний код) (захищено)
Модуль:If empty (переглянути вихідний код) (захищено)
Модуль:Message box (переглянути вихідний код) (захищено)
Модуль:Message box/ambox.css (переглянути вихідний код) (захищено)
Модуль:Message box/configuration (переглянути вихідний код) (захищено)
Модуль:Namespace detect/config (переглянути вихідний код) (захищено)
Модуль:Namespace detect/data (переглянути вихідний код) (захищено)
Модуль:Navbar (переглянути вихідний код) (захищено)
Модуль:Navbar/configuration (переглянути вихідний код) (захищено)
Модуль:Navbar/styles.css (переглянути вихідний код) (захищено)
Модуль:Navbox (переглянути вихідний код) (захищено)
Модуль:Navbox/configuration (переглянути вихідний код) (захищено)
Модуль:Navbox/styles.css (переглянути вихідний код) (захищено)
Модуль:Portal (переглянути вихідний код) (захищено)
Модуль:Portal/images/other (переглянути вихідний код) (захищено)
Модуль:TableTools (переглянути вихідний код) (захищено)
Модуль:Webarchive (переглянути вихідний код) (захищено)
Модуль:Yesno (переглянути вихідний код) (захищено)
Модуль:Не перекладено (переглянути вихідний код) (захищено)

Повернення до сторінки «Код Гаффмана».

Отримано з https://uk.wikipedia.org/wiki/Код_Гаффмана