Энтропия и избыточность алфавита

Энтропия алфавита – это количество информации, приходящееся на один символ. Символы равновероятного алфавита несут максимальную информационную нагрузку

H_max = log₂ N, где N – объем алфавита.

Алфавиты природных языков не являются равновероятными. Например, относительная частота появления отдельных символов русского языка изменяется от 0,175 до 0,002.

Вследствие статистических свойств алфавита информационная нагрузка на один символ снижена на

∆H = H_max - H_ср = 0,65 бит/ символ.

Избыточностью алфавита называется уменьшение информационной нагрузки на один символ вследствие неравновероятности и взаимозависимости появления его символов.

Информационная избыточность, характеризующая относительную недогруженность алфавита рассчитывается так:

Равномерные коды

Равномерные кодыхарактеризуются минимальной разрядностью кодовых слов, которая рассчитывается по формуле

где N – объем исходного алфавита А;

M – объем кодового алфавита В;

[log_M N] означает целую часть числа log_M N

Рассмотрим эти формулы для случая двоичного кодирования (т. е. при М = 2). Минимальная разрядность равномерного кода для алфавита объемом 8 символов будет равна

r _min =log₂ 8 =3 двоичных символа

А для 9-буквенного алфавита

r_min = [log₂ 9]+1 =[3,17]+1 = 3 +1 = 4 дв. симв

Неравномерные коды

Неравномерные кодыхарактеризуются средней длиной кодового слова

l_i – длина кодового слова i-го символа;

p_i – вероятность появления i-го символа;

N – объем исходного алфавита.

Например, если алфавит А = {a, b, c, d, e} с вероятностями появления символов в сообщении (p_a = 0,5; p_b = 0,2; p_c = 0,1; p_d = 0,15; p_e = 0,05) закодирован двоичным неравномерным кодом (a – 0; b – 10; c – 1110; d – 110; e – 1111), то средняя длина кодового слова для такого алфавита будет

Таким образом, средняя длина кодового слова есть сумма длин всех кодовых слов, взятых с весом, равным вероятности появления кодируемого символа.

Количество и объем информации

Оптимальное кодирование

Метод Шеннона – Фано

Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в строку).

Шаг 2. Не меняя порядка символов, делим их на две группы так, чтобы суммарные вероятности символов в группах были по возможности равны.

Шаг 3. Приписываем группе слева "0", а группе справа "1" в качестве элементов их кодов.

Шаг 4. Просматриваем группы. Если число элементов в группе более одного, идем на Шаг 2. Если в группе один элемент, построение кода для него завершено.

Метод Хаффмана

Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в столбец).

Шаг 2. Объединяем два символа с наименьшими вероятностями. Символу с большей вероятностью приписываем "1", символу с меньшей – "0" в качестве элементов их кодов.

Шаг 3. Считаем объединение символов за один символ с вероятностью, равной сумме вероятностей объединенных символов.

Шаг 4. Возвращаемся на Шаг 2 до тех пор, пока все символы не будут объединены в один с вероятностью, равной единице.