355
правок
Изменения
Исправлено определение и добавлен алгоритм
'''''Алгоритм Хаффмана''''' — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.
== Определение ==
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> - алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что: 1.<tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i != j</tex> 2.<tex>\sum\limits_{i \in [1, n]} w_{i}c_{i}</tex> минимальна (<tex>|c_{i}|</tex> --- длина кода <tex>c_{i}</tex>) называется '''Коды''' или кодом Хаффмана'''.}} == Алгоритм == Построение кода Хаффмана''' ('''Huffman codes''') — широко распространенный и очень эффективный метод сжатия данныхсводится к построению соответствующего бинарного дерева по следующему алгоритму: 1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, которыйвесом, равным частоте появления символа в зависимости от характеристик этих данныхтексте. 2. Из списка выберем два узла с наименьшим весом. 3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, обычно позволяет сэкономить от 20% до 90% объемаи присоединим к нему два выбранных узла в качестве дочерних. 4. Добавим к списку только что сформированный узел.}}Рассматриваются данные5. Если в списке больше одного узла, представляющие собой последовательность символовто повторить п. В алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов2---п. С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки5.
== Построение кода Хаффмана Пример ==
<div style="float:right; margin:0;padding:0;">
