Инструменты пользователя

Инструменты сайта


examination:computer_science:question7

Вопрос №7 Алфавитное неравномерное двоичное кодирование. Префиксный код. Код Хаффмана

Алфавитное неравномерное двоичное кодирование - кодирование при котором символы некоторого первичного алфавита кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться.

Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует. Хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа.

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом:

0 10 0 11 0 11 10

Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами.

0 10 0 11 0 11 10

0 100 11 0 11 10

Префиксные коды широко используются в различных областях информационных технологий. На них основаны многие алгоритмы сжатия информации. Их используют различные протоколы. К префиксным кодам относятся такие распространённые вещи, как: • Юникод, • телефонные номера, • Код Хаффмана, • Код Фибоначчи и мн. другие.

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

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

1.Построение оптимального кодового дерева.

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

Алгоритм

  1. Подсчитываются вероятности появления символов первичного алфавита в исходном тексте (если они не заданы заранее)
  2. Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.
  3. Последние m2 символов объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение. Вероятность этого символа равна суммарной вероятности удаленных символов. Затем вставляют новый символ в список остальных на соответствующее место (по вероятности)
  4. Предыдущий шаг повторяют до тех пор, пока в списке не меньше m2 символов.
  5. Последние n0 символов объединяют в новый символ, вероятность которого равна 1. n0 вычисляется из системы,где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно.

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

Построение дерева Хаффмана

Бинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана. Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.

Общая схема построения дерева Хаффмана:

  • Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
  • Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).
  • Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
  • Удалим выбранные узлы из списка.
  • Добавим вновь сформированный узел к списку.
  • Если в списке больше одного узла, то повторить 2-6.

Примечания

Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

examination/computer_science/question7.txt · Последние изменения: 2014/01/15 12:15 (внешнее изменение)