Код Гаффмана: відмінності між версіями

[перевірена версія][перевірена версія]
Вилучено вміст Додано вміст
Скасування редагування № 30125943 користувача 212.90.61.31 (обговорення) Варто почати з обговорення
Мітка: Скасування
джерела
Рядок 1:
'''Алгоритм Гаффмана''' (або '''коди Гафмена'''<ref name="mit">{{cite book|
'''Алгоритм Гаффмана'''&nbsp;— [[Адаптивний алгоритм|адаптивний]] [[жадібний алгоритм]] оптимального [[префіксний код|префіксного]] кодування алфавіту з мінімальною надмірністю. Був розроблений аспірантом [[Массачусетський технологічний інститут|Массачусетського технологічного інституту]] [[Девід Гаффман|Девідом Гаффманом]] при написанні ним курсової роботи та надрукований в статті [[1952|1952 року]] «A Method for the Construction of Minimum-Redundancy Codes».<ref>{{Cite journal | last1 = Huffman | first1 = D. |authorlink1=David A. Huffman| 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}}</ref> В даний час{{Коли}} використовується в багатьох програмах стиснення даних [[Стиснення без втрат|без втрат]].
|author-link=Томас Кормен
|first=Томас
|last=Кормен
|authorlink2=Чарльз Лейзерсон
|first2=Чарльз
|last2=Лейзерсон
|authorlink3=Рональд Рівест
|first3=Рональд
|last3=Рівест
|authorlink4=Кліфорд Стайн
|first4=Кліфорд
|last4=Стайн
|year=2019
|title=[[Вступ до алгоритмів]]
|edition=3
|publisher= [[К.І.С.]]
|isbn=978-617-684-239-2
|ref=harv
| розділ=16.3: Коди Гафмена
|сторінки=443-451
'''Алгоритм Гаффмана'''}}</ref>)&nbsp;— [[Адаптивний алгоритм|адаптивний]] [[жадібний алгоритм]] оптимального [[префіксний код|префіксного]] кодування алфавіту з мінімальною надмірністю. Був розроблений аспірантом [[Массачусетський технологічний інститут|Массачусетського технологічного інституту]] [[Девід Гаффман|Девідом Гаффманом]] при написанні ним курсової роботи та надрукований в статті [[1952|1952 року]] «A Method for the Construction of Minimum-Redundancy Codes».<ref>{{Cite journal | last1 = Huffman | first1 = D. |authorlink1=David A. Huffman| 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}}</ref> В даний час{{Коли}} використовується в багатьох програмах стиснення даних [[Стиснення без втрат|без втрат]].
 
На відміну від [[Алгоритм Шеннона-Фано|алгоритму Шеннона&nbsp;— Фано]], алгоритм Гаффмана залишається завжди оптимальним і для [[вторинний алфавіт|вторинних алфавітів]] m<sub>2</sub> з більш ніж двома символами.
Рядок 76 ⟶ 97:
== Застосування ==
 
Стиснення даних Гаффмана застосовується під час стиснення фото- і відеозображень ([[JPEG]], стандарти стиснення [[Moving Picture Experts Group|MPEG]]), в архіваторах[[архіватор]]ах ([[PKZIP]], [[LZH]] та інінших), в протоколах передачі даних MNP5 і MNP7.
 
== Примітки ==