Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2022-08-21 | 46 |
5.00
из
|
Заказать работу |
|
|
1. Инициализация. Список «подлежащих обработке» узлов состоит из N0 = N узлов, каждому из которых приписана вероятность одного из сообщений.
2. До тех пор, пока число узлов N0 > 1, повторяются следующие действия:
В списке необработанных узлов находим два узла с наименьшими вероятностями. Они исключаются из списка и вместо них вводится новый узел, которому приписывается суммарная вероятность двух исключенных узлов. Новый узел связывается ребрами с исключенными узлами. Число необработанных узлов N0 уменьшается на 1, N0 N0 - 1
После выполнения алгоритма будет получено кодовое дерево кода, который, как доказано выше, имеет наименьшую возможную среднюю длину кодовых слов.
Пример. 12.3. Рассмотрим ансамбль буквенных сообщений {a, b, c, d, e, f} вероятностями букв {0,35, 0,2, 0,15, 0,1, 0,1, 0,1} соответственно. Кодовое дерево и код Хаффмана показаны на рис. 12.2. Энтропия источника H(x) = 2,4016. Средняя длина кодовых слов равна =2,45. Согласно свойствам 1-4 не существует кода для X со средней длиной кодовых слов меньшей, чем 2,45.
Избыточность кода Хаффмана
Из теоремы 12.3 следует, что для построенных по алгоритму Хаффмана кодов средняя длина кодовых слов удовлетворяет неравенству
, (12.4)
где H(x) – энтропия ансамбля.
Разность называется избыточностью неравномерного кода. При кодировании с избыточностью r на каждое сообщение тратится на r бит больше, чем в принципе можно было бы потратить, если использовать теоретически наилучший (возможно, нереализуемый) способ кодирования.
Итак, из (12.4) следует, что для кода Хаффмана избыточность r ≤ 1. Хотелось бы получить более точную оценку средней длины кодовых слов. Р. Галлагер, получил гораздо более точную оценку избыточности, наложив ограничение на максимальную из вероятностей сообщений.
|
Теорема 12.5. Пусть P1 – наибольшая из вероятностей сообщений конечного дискретного ансамбля. Тогда избыточность кода Хаффмана для этого ансамбля удовлетворяет неравенствам
где H(P1) = –P1 log P1 – (1– P1)log(1– P1) – энтропия двоичного ансамбля, и
s = 1 – log e – log log e» 0,08607.
Код Шеннона - Фано
Рассмотрим источник, выбирающий буквы из множества X ={1,...,N} с вероятностями {P1,…,PN}. Считаем, что буквы упорядочены по убыванию вероятностей, т.е. P1 ≥ P2 ≥ … ≥ PN.
Кодирование Шеннона-Фано имеет большое сходство с кодированием Хаффмана. Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность 'aa bbb cccc ddddd'. Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения xi и их вероятностей P(xi), и отсортировать её в порядке невозрастания вероятности символов.
Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1'. Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:
Кодирование Шеннона-Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса (разве что как упражнение в учебных целях). В большинстве случаев, длина закодированной последовательности, по данному методу, равна длине закодированной последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются не оптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным. Такие отличии в степени сжатия возникают из-за нестрогого определения способа деления символов на группы.
|
|
|
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!