Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
'Инструкция'
Цитомегаловирус (ЦМВ) представляет собой вирус икосаэдрический формы, 180-250нм в диаметре, принадлежит к семейству герпесвирусов. Вирус оказывает цит...полностью>>
'Документ'
Правовое регулирование качества продукции, работ и услуг. Правовое регулирование финансирования хозяйственной деятельности....полностью>>
'Документ'
Краеведческая интернет – викторина «Имена. События. Даты» посвящена 70-летию Победы в Великой Отечественной войне и 72 годовщине освобождения Смоленщи...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

27

1.6. Доказательство оптимальности кода Хаффмана

Лемма 1. Пусть w1  w2  … wn  1  wn. Существует такой оптимальный префиксный код, что l1  l2  … ln  1  ln.

Доказательство. Пусть C = {c1, c2, …, cn} – некоторый оптимальный префиксный код, а  префиксный код, полученный из C  перестановкой i-го и j-го кодовых слов. Тогда и , а для имеем . Далее

Тогда из следует li  lj. Если же , то . За конечное число перестановок индексов i и j, удовлетворяющих условию , можно получить требуемое неравенство для li  и  lj.

Лемма 2. Пусть w1  w2  … wn  1  wn. Существует такой оптимальный префиксный код C, что l1  l2  …  ln  1 = ln, и кодовые слова и различаются в точности последним символом.

Доказательство. Пусть C – некоторый оптимальный префиксный код, в котором l1  l2  … ln  1  ln (лемма 1), и пусть сn = (сn(1), сn(2), …, сn(ln)). Рассмотрим 2 случая.

Случай 1: нет кодового слова (сn(1), сn(2), …, сn(ln  1), 1  сn(ln)). В терминах дерева это означает, что имеет место одна из двух ситуаций

Поскольку код префиксный, то узел отец (n) не представляет кодового слова. Тогда узел n можно «поднять» на место его отца и, следовательно, уменьшить величину ln , а тем самым и длину полного кода = i=1..n wi li , что противоречит оптимальности кода C. Итак, случай 1 невозможен.

Случай 2: пусть для некоторого i1..n  1 существует кодовое слово сi = (сn(1), сn(2), …, сn(ln  1), 1  сn(ln)). Если i n  1, то утверждение леммы справедливо. Если же i n  1, то li = ln = l 1. Переставим кодовые слова с номерами i  и n  1 (перевесим листья дерева). При этом значение = i=1..n wi li  не изменится, а новый префиксный код будет обладать желаемым (по лемме) свойством. Лемма 2 доказана.

При формулировке следующего утверждения будут использованы обозначения Wn и , как они определены в 1.4 при описании алгоритма Хаффмана. Кроме того, полную длину кода L будем записывать как функцию от набора весов Wn и кодового дерева Tn: L(Wn, Tn). Если Tn – оптимальное кодовое дерево (ОКД), то обозначим Lmin(Wn) = L(Wn, Tn).

Утверждение. Пусть  w1  w2  … wn  1  wn. Пусть – ОКД для , т. е. . Пусть

Тогда – ОКД для Wn , т. е.

.

Доказательство. По построению дерева справедливо

. (1.1)

С другой стороны, пусть Tn – некоторое ОКД для набора весов Wn , а – такое ОКД для набора весов Wn , что удовлетворены все условия леммы 2, тогда

где – дерево, полученное из ОКД заменой поддерева из двух листьев с весами wn  1  и wn на лист с весом . Из неравенств (1.1) и (1.2) получаем требуемое равенство

,

завершая тем самым доказательство утверждения.

Фактически доказанное утверждение есть обоснование индуктивного перехода в доказательстве оптимальности дерева Хаффмана методом математической индукции. Действительно, показано, что из оптимальности предварительно построенного следует оптимальность дерева .

1.7. Неравенство Крафта

Оптимальное кодовое дерево определяет набор длин (l1l2, …, ln) кодовых слов, минимизирующий = i=1..n wi li  и учитывающий требование префиксности кода. Рассмотрим это требование более формально. Оказывается, что на вопрос о том, для каких заданных длин (li)1n кодовых слов существует префиксный код, можно дать точный ответ, найденный Л. Крафтом (L. G. Kraft).

Утверждение (неравенство Крафта). Для того чтобы существовал префиксный код с длинами кодовых слов l1l2, …, ln, необходимо и достаточно выполнение неравенства

.

Доказательство. 1) Необходимость (из существования префиксного кода следует неравенство Крафта). Рассмотрим кодовое дерево, соответствующее префиксному коду с длинами кодовых слов l1l2, …, ln.

Обозначим  число листьев на k-м уровне (k = 0, 1, …, K, где K – максимальная длина кодового слова или высота кодового дерева). Очевидно, . Можно дать более точную оценку. Наличие листа на уровне i исключает узлов на уровне k (k  i). Если на уровне i имеется листьев, то они «обрывают» поддеревья с узлов на уровне k. Следовательно, число узлов на уровне k не превосходит

,

а следовательно,

.

Отметим, что на последнем уровне строгое неравенство «<» выполняется тогда, когда дерево является не строго бинарным, а код, соответственно, неполным. Разделив обе части полученного неравенства на и сгруппировав слагаемые, получим

или

.

Заменяя суммирование по уровням на суммирование по листьям, получаем

.

2) Достаточность (из неравенства Крафта следует существование префиксного кода). Пусть выполняется неравенство Крафта. Переходя от суммирования по листьям к суммированию по уровням, получим

.

Отсюда следует, что и для всех слагаемых выполняется

,

и, следовательно, для всех k 1..K

. (1.3)

Далее рассмотрим полное ровное дерево высоты K. Будем строить кодовое дерево по уровням от корня вниз, удаляя лишние узлы и ветки. Начнем с , которое может принимать значения 0, 1, 2. Выберем в соответствии с l1l2, …, ln . Рассмотрим . Очевидно, после выбора на втором уровне останется 4  2 узлов, из которых нужно выбрать листьев. Поскольку в силу неравенства (1.3) имеем , то этот выбор возможен. Далее рассмотрим третий уровень. На нем свободных для выбора осталось узлов. Из неравенства (1.3) следует, что , т. е. опять-таки выбор листьев возможен. Повторяя этот процесс до k = K, получим требуемое кодовое дерево. Доказательство завершено.

Теперь можно сформулировать задачу построения оптимального префиксного кода как задачу нахождения такого набора , который минимизирует при заданном наборе и при ограничениях: 1)  целые и для ; 2) (свойство префиксности).



Похожие документы:

  1. Рабочая программа дисциплины “структуры и алгоритмы обработки данных” Для подготовки дипломированных специалистов по направлениям

    Рабочая программа
    ... (построение дерева, кодирование и декодирование), доказательство оптимальности кода Хаффмена, неравенство Крафта, теорема кодирования в отсутствие ... представленного в конъюнктивной нормальной форме. Доказательство NP-полноты задачи о выполнимости. ...
  2. В. В. Лидовский Информация о курсе

    Реферат
    ... , что коду 10 соответствует символ C, коду 0 - A и т.д. Построим коды Хаффмена для значений ... арифметическое кодирование. Математическое доказательство его "выгодности" по ... квазисовершенный код - оптимален. Общий способ построения оптимальных кодов пока ...
  3. Методика построения линейных систематических кодов (образующая матрица). Процедура декодирования линейных кодов. Коды Хемминга. Коды Хемминга с проверкой на четность

    Документ
    ... Хаффмана). Прямая теорема Шеннона для дискретного канала связи с шумом. Понятие и типы кодов ... Понятие и свойства непрерывных кодов. Построение оптимальной шкалы квантования. Поэлементный ... поиска. Поиск решений доказательством теорем. Общие сведения; ...
  4. Экзаменационные вопросы для специальности поисои (заочный факультет) по дисциплине «Моделирование систем обработки информации»

    Экзаменационные вопросы
    ... неопределенности. Свойства энтропии и их доказательства. Энтропия взаимосвязанных событий. Свойства энтропии ... Оптимальные системы счисления. Основные параметры кодов. Способы представления кодов. Эффективное кодирование, теорема Шеннона. Код Хаффмена ...
  5. Примерные ответы на профильные билеты Е. А. Еремин, А. П. Шестаков

    Документ
    ... является тавтологией1. Проведем доказательство путем упрощения исходного ... адекватности и простоты и оптимальности. Требование адекватности модели ... и PNG, а также метод Хаффмана (PNG и JPG — о ... ей HTML-код. В режиме Код отображается только HTML-код. В ...

Другие похожие документы..