Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Cохранение данных в двоичных файлах.
  2. III. Особенности участия субъектов малого и среднего предпринимательства в закупках в качестве субподрядчиков
  3. J) просит Генеральную Ассамблею соответственно увеличить бюджетные средства, выделяемые для Рабочей группы, с тем чтобы удовлетворить потребности ее будущей деятельности.
  4. Quot;Мы послали в каждую общину посланника, чтобы вы поклонялись Аллаху и избегали поклонения т а г у т у".
  5. T6. А теперь я бы хотел(а), чтобы Вы оценили Ваше последнее посещение магазина … (МАГАЗИН ИЗ ВОПРОСА Q7) по каждой из перечисленных характеристик, используя шкалу на карточке.
  6. А для того, чтобы просчитать период прохождения одного зала, мы должны период обращения вокруг Ярило - Солнца разделить на 144, либо время прохождения чертога разделить на 9.
  7. А для того, чтобы просчитать период прохождения одного зала, мы должны период обращения вокруг Ярило - Солнца разделить на 144, либо время прохождения чертога разделить на 9.
  8. А чтобы это всё действовало, человек должен всё это знать и понимать. Тот, кто не знает и не понимает, ему информация не доступна.
  9. А чтобы это всё действовало, человек должен всё это знать и понимать. Тот, кто не знает и не понимает, ему информация не доступна.
  10. А. Платонов в своей сказке утверждает, что надо много трудиться, чтобы жить и не умереть, чтобы светить ярким огнём другим и звать к себе безмолвным голосом радости жизни.

Легко закодировать источник с помощью двух символов, независимо от того, каковы их соответствующие вероятности: два кодовых слова должны быть просто 0 и 1, обеспечивая среднюю длину 1. Лучшего кода не существует!.

Усложним задачу. Пусть источник кодируется тремя символами, у каждого из которых есть своя вероятность.

В этом случае процесс кодирования по алгоритму Хаффмена будет состоять из нескольких шагов:

– (этап сокращения) временно объединим два символа с самыми низкими вероятностями в один сложный символ с вероятностью, равной сумме вероятностей отдельных символов.

В результате вместо трёх символов останется только два (один сложный, полученный на первом шаге, со своей вероятностью и последний оставшийся из начального набора). Двух символьный источник легко кодируется символами 0 и 1.

– (этап разделения) сложный символ разделяется на свои компоненты, которым присваиваются коды, имеющие общий префикс, соответствующий коду сложного символа, закреплённого за ним на первом шаге.

Проиллюстрируем эту задачу: Построим кодовое дерево.

 
 


Символ Вероятность Кодовое слово Вероятность
Кодовое

слово

S1 0.5 0.5
0

S2 0.3 10 0.5
1

S3 0.2  

S3
Посчитаем среднюю длину слов созданного кода

S2
S1
L=(0,5х2)+(0,3х2)+(0,2х2)=2.

Посчитаем энтропию данного источника

H=0,5 х log 0,5 +0,3 х log 0,3+0,2 х log 0,2=1,49.

Проверим свойство созданного кода

H<=L<H+1 => 1,49<=2<2,49,

что согласуется с утверждением о пределах средней длины слов кода:

«источник с энтропией H может кодироваться с помощью моментального двоичного кода средней длины L, удовлетворяющего H<=L<H+1».


Дата добавления: 2014-12-19; просмотров: 9 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2021 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав