10.30 Базовые определения теории информации

Количество информации, содержащееся в символе, которое определяется частотой его появления, равно:

log₂(1/p_i)   [бит]

Отсюда среднее количество информации на один произвольный символ равно:

E называют средним количеством информации на символ или энтропией источника информации. Результатом отдельного альтернативного выбора может быть <0> или <1>. Тогда всякому символу соответствует некоторая последовательность <0> и <1>. Такая последовательность является кодировкой символа. Энтропия одной буквы русского языка равна примерно Е₁≈4,35 бит.

Если при некотором кодировании символов i-ый символ имеет длину N_i, то средняя длина слов равна:

Если предположить, что набор символов можно поделить на равновероятные подмножества, то L=E. Следует иметь в виду, что на самом деле всегда E ≤ L (следствие теоремы кодирования Шеннона).

Так как на практике отдельные символы встречаются с разной вероятностью, то кодирование с постоянной длиной кодовых слов обычно является избыточным. Так все стандартные 8-битовые кодировки русского алфавита являются избыточными. Значение энтропии для русского языка ≤ 4,35. Для точной оценки энтропии следует учесть вероятности различных пар и троек символов. Такой учет из-за корреляционных зависимостей может понизить значение Е. Учет вероятности всевозможных групп символов может понизить Е почти до уровня ≈1 бит на символ.

Представленные выше логарифмические зависимости косвенно подтверждаются законом Меркеля (1885 г). Время реакции испытуемого при требовании выбора определенного предмета из N имеющихся пропорционально log(N).

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

Обычный способ определения энтропии текста базируется на модели Маркова для текста. При этом вероятность появления очередного символа предполагается независимой от предыдущего символа (что, разумеется не всегда верно).

Если мы имеем n-буквенный алфавит и используем m-ичныйое кодовое представление (m уровней сигнала, при m=2 получем двоичное представление), то для передачи одной буквы может требоваться ~log(n)/log(m) элементарных сигналов.

Основная теорема кодирования. При кодировании сообщения, разбитого на N-буквенные блоки, можно, выбрав N достаточно большим, добиться того, чтобы среднее число двоичных элементарных сигналов, приходящихся на одну букву исходного сообщения, было сколь угодно близко к отношению количества информации, содержаейся в одной букве, к одному биту (Е).

В общем случае взаимозависимых букв значение энтропии Е одной буквы следует заменить удельной энтропией Е_∞ = lim(E(N))/N) при N → ∞, где Е(N) - энтропия из N букв.

Разность R = 1 - E_∞/H₀ показывает, насколько меньше единицы отношение предельной энтропии E_∞ к величине H₀ = log(n), которая характеризует наибольшую информацию, содержащуюся в одной букве алфавита с данным числом букв. Шеннон назвал эту разность избыточностью языка. Избыточность русского языка превышает 50%.

Одной из заслуг Шеннона является установление факта зависимости ограничения пропускной способности канала от уровня шума.

Иногда энтропия выражается в битах в секунду. Если для канала без памяти энтропия символа равна Е, и если источник генерирует один символ каждые t секунд, то энтропия в битах в секунду равна E/t.

Если по линии связи в единицу времени можно передать L элементарных сигналов, принимающих m различных значений, то скорость передачи сообщений не может быть больше чем:

v = (L log(m))/E букв/ед. времени

Числитель этого выражения зависит лишь от канала связи, а знаминатель характеризует само сообщение.

Для каждого канала без памяти, емкость канала С=supI(X;Y) имеет следующее свойство (теорема Шеннона).

<Передатчик> → X → <Канал с шумом> → Y → <Приемник>

Для любого e> 0 и R<C, для достаточно большого N, существует код длиной N и скорость передачи ≥ R и алгоритм декодирования, при котором максимальная блочная ошибка ≤ e.

Если вероятность ошибки при передаче бита (BER) p_b приемлема, то достижимы скорости передачи вплоть до R(p_b), где

и E₂(p_b) является двоичной энтропийной функцией

E₂(p_b)= -[p_b log p_b + (1- p_b) log(1-p_b)]

Для любого p_b, скорости передачи выше R(p_b) не достижимы.

Для случая "белого" гауссова шума, когда все частоты имеют равные уровни, а амплитуды имеют гауссово распределение имеем:

где N_S - средняя мощность сигнала, а N_N - средняя можность шума. Из этой формулы непосредственно следует традиционная формула теоремы Шеннона для канала с заданной полосой пропускания и уровнем шума.

Энтропия указывает предельный уровень сжатия данных архиваторами. Написать программу, которая бы обеспечила более высокий уровень сжатия теоретически невозможно. Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский обладает одной из самых высоких уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на 30% больше.

Энтропия составных событий. Условная энтрпия

Пусть имеется два независимых опыта Х и У с таблицами вероятностей исходов:

Рассмотрим составной эксперимент , состоящий в том, что одновременно выполняются испытания Х и У. Такой эксперимент может иметь km исходов:

X1Y1,X1Y2,...,X1Ym; A2Y1, X2Y2,...,X2Ym;....; XkY1, XkY2,...,XkYm,

где X1Y1 означает, что эксперимент X имел исход X1, а эксперимент Y - исход Y1. Понятно, что неопределенность эксперимента XY будет больше неопределенности каждого из X и Y в отдельности. Энтропия T(XY=E(X) + E(Y).

Если теперь предположить, что результаты опытов X и Y не являются независимыми. В этом случае уже нельзя предполагать, что энтропия составного опыта XY может быть равна сумме энтропий X и Y. Энтропия составного опыта XY будет равна:

E(XY) = - p(X1Y1)log(p(X1Y1)) - p(X1Y2)log(p(X1Y2)) - ... - p(X1Ym)log(p(X1Ym)) - ...
- p(X2Y1)log(p(X2Y1)) - p(X2Y2)log(p(X2Y2)) - ... - p(X2Ym)log(p(X2Ym)) - ...
- p(XkY1)log(p(XkY1)) - p(XkY2)log(p(XkY2)) - ... - p(XkYm)log(p(XkYm)) ,

Здесь уже нельзя заменить вероятности p(X1Y1), p(X1Y2) и т.д. произведениями вероятностей (p(X1Y1) не равно p(X1)p(Y1), а p(X1)p_X1(Y1) - условная вероятность события Y1 при условии X1. Энтропия Е_Х(У) называется условной энтропией опыта Y при условии реализации опыта X.

E_X(Y) = p(X1)E_X1(Y) + p(Y2)E_X2(Y) + ... + p(Xk) E_Xk(Y) или

E(XY) = E(X) + E_X(Y)

В любом случае

0 ≤ E_X(Y) ≤ E(Y)

Условные значения энтропии для двухбуквенных и трехбуквенных комбинаций в русском языке равны:

E₀=log(32)=5; E₁=4,35; E₂= 3,52; E₃= 3,01

При языковых исследованиях следует учитывать то, что появление в тексте определенной буквы меняет распределение вероятностей для следующей. Так появление буквы "е" делает весьма вероятным появление еще одной буквы "e". Но появление комбинации "ee" делает появление еще одного "e" крайне мало вероятным. Примеров таких корреляций можно привести достаточно много.

Для языков, использующих латинский алфавит, частоты использования отдельных букв весьма различны. Так если разместить символы букв по мере убывания их частоты использования, то для английского языка мы получим _ETAONRI..., для немецкого - _ENISTRAD... и для французского - _ESANITUR... .Во всех случаях символ _ обозначает пробел между словами.

Классическое определение информационной энтропии (H) выглядит как:

где p_i - вероятность того, что реализуется конкретное значение х_i (i может принимать значения от 1 до n. I(x) - целочисленная случайная функция (информационное содержимое Х).

Литература