Изменения
Перейти к навигации
Перейти к поиску
Строка 1:
Строка 1: − + Строка 27:
Строка 27: − + Строка 118:
Строка 118: − * [http://habrahabr.ru/post/144200/ Алгоритм Хаффмана на пальцах] // [[Habrahabr.ru]] − * [http://mp.fizteh.urfu.ru/InformationTheory/1.%D0%A2%D0%B5%D0%BE%D1%80.%D0%BA%D1%83%D1%80%D1%81/3.%20%D0%A2%D0%B5%D1%85%D0%BD%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D0%B8_%D0%BE%D0%B1%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B8_%D0%B8%D0%BD%D1%84.%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D1%83%D0%BA%D0%B0%D0%B7%D0%B0%D0%BD%D0%B8%D1%8F/%D0%9B%D0%B0%D0%B1%D0%BE%D1%80%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D1%8B%D0%B5/%D1%811)%20%D0%A1%D0%B6%D0%B0%D1%82%D0%B8%D0%B5%20%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85.%20%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%20%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%20MathCAD%20%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9%20%D0%BC%D0%B5%D1%82%D0%BE%D0%B4/ Пример программы для динамического метода Хаффмана в MathCAD] Строка 127:
Строка 125: + +
нет описания правки
'''Алгоритм Хаффмана''' — [[Адаптивный алгоритм|адаптивный]] [[простой алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952 год]]у аспирантом [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]] при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
'''Алгоритм Хаффмана''' — [[Адаптивный алгоритм|адаптивный]] [[жадный алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952 год]]у аспирантом [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]] при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
В отличие от [[Алгоритм Шеннона — Фано|алгоритма Шеннона — Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m<sub>2</sub> с более чем двумя символами.
В отличие от [[Алгоритм Шеннона — Фано|алгоритма Шеннона — Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m<sub>2</sub> с более чем двумя символами.
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n<sub>0</sub> потомков — символы из предыдущего шага и т. д.
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n<sub>0</sub> потомков — символы из предыдущего шага и т. д.
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от корня до листа дерева, соответствующего текущему символу, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего текущему символу, до его корня, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.
Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2003 Визуализатор кодирования букв русского алфавита]
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/huffman-tree-2003 Визуализатор кодирования букв русского алфавита]
* [http://algolist.manual.ru/compress/standard/huffman.php Сжатие по алгоритму Хаффмана] на algolist.manual.ru
* [http://algolist.manual.ru/compress/standard/huffman.php Сжатие по алгоритму Хаффмана] на algolist.manual.ru
{{методы сжатия}}
{{методы сжатия}}
[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Задачи, решаемые жадным алгоритмом]]
[[Категория:Задачи, решаемые жадным алгоритмом]]
[[de:Shannon-Fano-Kodierung#Huffman-Code]]