Автор работы: Пользователь скрыл имя, 16 Октября 2013 в 20:42, реферат
Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.
Алгоритм Хаффмана
Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.
Определение
Определение: |
Пусть — алфавит из n различных символов, — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов , такой, что: 1. не является префиксом для , при 2. Сумма минимальна. ( — длина кода ) называется кодом Хаффмана. |
Алгоритм
Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:
1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, весом, равным частоте появления символа в тексте.
2. Из списка выберем два узла с наименьшим весом.
3. Сформируем новый узел
с весом, равным сумме весов
выбранных узлов, и
4. Добавим к списку
только что сформированный
5. Если в списке больше одного узла, то повторить пункты со второго по пятый.
Пример
Дерево Хаффмана для слова "Миссисипи"
Для примера возьмём слово "
Узел |
и |
м |
п |
с |
Вес |
4 |
1 |
1 |
3 |
По алгоритму возьмем два символа с наименьшей частотой — это м и п. Сформируем из них новый узел мп весом 2 и добавим его к списку узлов:
Узел |
и |
мп |
с |
Вес |
4 |
2 |
3 |
Затем объединим в один узел узлы мп и c:
Узел |
и |
мпс |
Вес |
4 |
5 |
И, наконец, объединяем два узла и и мпс. Итак, мы получили дерево Хаффмана и соответствующую ему таблицу кодов:
Символ |
и |
м |
п |
с |
Код |
0 |
100 |
101 |
11 |
Таким образом, закодированное слово "миссисипи" будет выглядеть как "1000111101101010". Длина закодированного слова — 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит.
Корректность алгоритма Хаффмана
Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
Лемма (1): |
Пусть — алфавит, каждый символ которого встречается с частотой . Пусть и — два символа алфавита с самыми низкими частотами. Тогда для алфавита существует оптимальный префиксный код, кодовые слова символов и в котором имеют одинаковую максимальную длину и отличаются лишь последним битом. |
Доказательство: |
|
Возьмем дерево , представляющее произвольный оптимальный префиксный код для алфавита . Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы и — листья с общим родительским узлом, находящиеся на максимальной глубине. Пусть символы и имеют общий родительский узел и находятся на максимальной глубине дерева . Предположим, что и . Так как и — две наименьшие частоты, а и — две произвольные частоты, то выполняются отношения и . Пусть дерево — дерево, полученное из путем перестановки листьев и , а дерево — дерево полученное из перестановкой листьев и . Разность стоимостей деревьев и равна:
что больше либо равно , так как величины и неотрицательны. Величина неотрицательна, потому что — лист с минимальной частотой, а величина является неотрицательной, так как лист находится на максимальной глубине в дереве . Точно так же перестановка листьев и не будет приводить к увеличению стоимости. Таким образом, разность тоже будет неотрицательной. Таким образом, выполняется неравенство . С другой стороны, — оптимальное дерево, поэтому должно выполняться неравенство . Отсюда следует, что . Значит, — дерево, представляющее оптимальный префиксный код, в котором символы и имеют одинаковую максимальную длину, что и доказывает лемму. |
|
Лемма (2): |
Пусть дан алфавит , в котором для каждого символа определены частоты . Пусть и — два символа из алфавита с минимальными частотами. Пусть — алфавит, полученный из алфавита путем удаления символов и и добавления нового символа , так что . По определению частоты в алфавите совпадают с частотами в алфавите , за исключением частоты . Пусть — произвольное дерево, представляющее оптимальный префиксный код для алфавита Тогда дерево , полученное из дерева путем замены листа внутренним узлом с дочерними элементами и , представляет оптимальный префиксный код для алфавита . |
Доказательство: |
|
Сначала покажем, что стоимость дерева может быть выражена через стоимость дерева . Для каждого символа верно , значит, . Так как , то
из чего следует, что
или
Докажем лемму от противного. Предположим, что дерево не представляет оптимальный префиксный код для алфавита . Тогда существует дерево такое, что . Согласно лемме (1), элементы и можно считать дочерними элементами одного узла. Пусть дерево получено из дерева заменой элементов и листом с частотой . Тогда , что противоречит предположению о том, что дерево представляет оптимальный префиксный код для алфавита . Значит, наше предположение о том, что дерево не представляет оптимальный префиксный код для алфавита , неверно, что и доказывает лемму. |
|
Теорема: |
Алгоритм Хаффмана дает оптимальный префиксный код. |
Доказательство: |
|
Справедливость теоремы непосредственно следует из лемм (1) и (2) |