Алгоритм Хаффмана

Алгоритм Хаффмана (англ. Huffman) — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. Используется в программе bzip2 на последнем этапе сжатия данных.

В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.

Этот метод кодирования состоит из двух основных этапов:

  1. Построение оптимального кодового дерева.
  2. Построение отображения код-символ на основе построенного дерева.

Алгоритм

  1. Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.
  2. Последние n0 символов объединяют в новый символ, вероятность которого равна сумме этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности). n0 вычисляется из системы:
    \left\{\begin{matrix} 2 \le n_0 \le m_2 \\ n_0 = m_1 - a(m_2-1) \end{matrix}\right.,
    где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно.
  3. Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.
  4. Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.

Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущего шага и т.д.

Каждые m2 элементов, стоящих на одном уровне, нумеруются от 0 до m2-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home