Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2023-01-02 | 36 |
5.00
из
|
Заказать работу |
|
|
Метод Хаффмена
Общие положения
К. Шеннон и Р. Фано предложили в наиболее чистом виде конструкцию кода переменной длины. В этом коде у каждого символа своя длина кодовой последовательности, как в азбуке Морзе. Но в отличие от азбуки Морзе, где конец кодовой последовательности определяется "третьим символом" — паузой, здесь нужно побеспокоиться о том, как определять завершение кода отдельного символа. Предлагается такое ограничение на код: никакая кодовая последовательность не является началом другой кодовой последовательности. Это свойство называется свойством префикса, а код, обладающий таким свойством, называется префиксным кодом.
В предположении, что кодируемые символы появляются в тексте независимо нужно стремиться уменьшать среднее число битов на один символ, т.е. математическое ожидание длины кодовой комбинации случайно выбранного символа, которое равно
где pi — вероятность, а si — длина кодовой последовательности i -го символа.
Получается экстремальная задача.
Задача о префиксном коде. Минимизировать математическое ожидание по всем наборам длин { si }, удовлетворяющим неравенству Крафта.
Теорема Крафта: Для того, чтобы набор целых чисел , мог быть набором длин путей поиска в схеме с исходами, необходимо и достаточно, чтобы
.
Набор, для которого минимально, называется оптимальным. Шеннон и Фано предложили строить код, близкий к оптимальному, следующим способом: разбить все символы на две группы с приблизительно равными суммарными вероятностями, коды первой группы начать с 0, а второй группы — с 1; внутри каждой группы делать то же самое, пока в каждой группе не останется только по одному символу.
|
Элегантный алгоритм для точного решения этой задачи предложил Д. Хаффмен. Алгоритм основывается на нескольких очевидных свойствах оптимального набора {sj}.
Лемма 1. Пусть {р i} — набор вероятностей символов и {s i} — длины оптимальных кодовых комбинаций. Если p1 > р 2 >•••> рп, то s1 < s2 < ••• <sn.
Доказательство. Здесь достаточно сослаться на уже встречавшуюся нам задачу о перестановке, минимизирующей скалярное произведение двух векторов.
Задача о минимуме скалярного произведения Пусть заданы т чисел х1 х2,.., хm и еще т чисел у1, у2,..., ym. Составим пары (х, у), включив каждое х i, и каждое у j ровно в одну пару Затем перемножим числа каждой пары и сложим получившиеся произведения. Требуется найти такое разбиение чисел на пары, при котором значение получившейся суммы будет наименьшим.
Теорема. Наименьшее значение суммы попарных произведений достигается при сопоставлении возрастающей последовательности x, убывающей последовательности у.
Доказательство Покажем, что если найдутся две пары чисел и , такие что и , то значение суммы попарных произведений можно уменьшить, заменив эти две пары парами и Действительно, так как
, то
.
Поскольку число возможных расположении равно т!, т.е. конечное число, то начиная с любого расположения за конечное число шагов мы закончим процесс улучшений на расположении, которое дальше улучшить невозможно. На нем и достигается минимум.
Лемма 2. В обозначениях и предположении леммы 1 две самые длинные кодовые комбинации имеют одинаковую длину, т.е. .
Доказательство. Действительно, пусть и, следовательно, п-я кодовая комбинация — самая длинная. Так как никакая кодовая комбинация не является началом никакой другой, то, сократив n-ю комбинацию до длины (n - 1)-й, мы получим снова уникальную кодовую комбинацию и более короткую, чем раньше, что невозможно для оптимальной кодировки.
Лемма 3. Рассмотрим наравне с исходной задачей Р сокращенную задачу Р', которая получается объединением двух самых редких символов в один символ, — в предположении леммы 1 это два последних символа с суммарной вероятностью . Минимальное значение целевой функции в задаче Р' отличается от значения в задаче Р на , а оптимальный кодовый набор для задачи Р получается из решения для задачи Р' удлинением на один бит кодовой последовательности для объединенного символа.
|
Доказательство. Действительно, каждому кодовому набору для задачи Р' можно так, как сказано в утверждении леммы, сопоставить кодовый набор для задачи Р с равными длинами самых редких символов. Это удлинение и приводит к приращению целевой функции на .
Теперь можно рассуждать так: в задаче Р мы ищем минимум на множестве кодов, которое мы обозначим через Сn , а в задаче Р' — аналогично на множестве Cn-1. В соответствии с леммой 2 в задаче Р можно искать минимум на множестве С' n, собственном подмножестве Сn , состоящем из таких наборов, в которых две самые длинные кодовые последовательности имеют одинаковую длину. Имеется взаимнооднозначное соответствие между Cn-1 и С' n, и значения целевых функций на соответствующих элементах двух множеств отличаются на постоянное слагаемое. Следовательно, и минимумы отличаются на это же постоянное слагаемое, так что минимуму в задаче Р' соответствует минимум на С' n, а он будет минимумом и для задачи Р.
Алгоритм, основанный на этих леммах, описывается в несколько строк: если в алфавите два символа, то нужно закодировать их 0 и 1, а если больше, то соединить два самых редких символа в один новый символ, решить получившуюся задачу и вновь разделить этот новый символ, приписав 0 и 1 к его кодовой последовательности.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!