Объединение символов

Энтропия и эффективность кодирования

Рассмотрим случайную переменную с множеством возможных значений (х₁ х₂,..., x_N), принимаемых с вероятностями (P₁, Р₂,..., P_n), где Р, означает вероятность резуль­тата x_i. Определим нижнюю границу средней длины кода. Мы знаем, что мерой информации для х_i является log(1/Р). Поэтому в идеальном слу­чае мы сможем представить значение x_i- кодовым словом длины L_i = log(l/P_i) бит. Однако в большинстве случаев log(l/P_i) не является целым числом, и лучшее, что мы можем сделать, — это выбрать ближайшее целое число L_i такое что

Умножая на Р_i и суммируя по всем кодовым словам, получаем:

Таким образом, оптимальный код позволяет получить среднюю длину кода, не более чем на 1 бит превосходящую энтропию оригинального набора символов. Таким образом, энтропия случайной переменной X может интерпретироваться как мини­мальное среднее число битов, необходимых для отображения одного значения X.

Можно показать, что код Хаффмана удовлетворяет данному неравенству. При­мер приводится в таблице. Средняя длина кода составляет 2,184, а энтропия рав­на 2,167. Обратите внимание на то, что не все отдельные кодовые слова удовлет­воряют неравенству. Однако в среднем это неравенство выполняется.

Предположим, что у нас есть источник, генерирующий символы из алфавита X, состоящего всего из двух символов А и В, встречающихся с вероятностью 0,8 и 0,2. Энтропия при такой схеме составляет 0,8 log(l,25) + 0,2 log(5) = 0,722. Но лучшее, что можно сделать в данном случае, — это использовать по одному биту для каждого кодового слова (например, А = 0, В = 1). Если определить эффективность кода как отношение энтропии источника (среднее число битов информации в сим­воле) к средней длине кодового слова (среднее число битов, используемых для кодирования одного символа), тогда эффективность этого кода будет равна 0,722.

Эффективность кода можно повысить, если объединить символы в блоки и ко­дировать эти блоки символов. Например, если мы будем кодировать по два симво­ла одновременно, тогда можно рассматривать полученные в результате блоки сим­волов как новый алфавит Y, состоящий из четырех символов (АА, АВ, ВА, ВВ). Если символы алфавита X следуют в сообщениях независимо друг от друга, тогда вероятности, с которыми в них встречаются символы алфавита Y, будут равны: Раа = 0,64; Р_Ав = 0,16; Рва = 0,16; Р_Вв = 0,04. На рисунке показан код Хаффмана для такого варианта объединения символов в блоки, а в верхней части таблицы ниже статистика этого кода. В результате мы получаем код со средней длиной 1,56 при эн­тропии, равной 1,444, таким образом, эффективность кода составляет 0,926, что значительно лучше, чем при кодировании исходных символов без группировки. Обратите внимание на то, что информация источника не изменилась. Энтропия случайной переменной X равна 0,722, а энтропия К равна 0,722 • 2 = 1,444, то есть все также по 0,722 бита на символ. Еще лучших результатов можно достичь, объединив символы по три. В данном случае эффективность кода составит 2,167/2,128 = 0,992. Энтропия все также будет составлять 0,722 бит на символ (2,167/3).

Можно показать, что эффективность оптимального кода для независимых по­следовательностей символов может быть повышена путем объединения символов, как это было показано ранее. Для блока из К символов мы получим следующее соотношение:

Таким образом, среднее количество битов на одно значение случайной пере­менной X можно сделать сколь угодно близким к энтропии, выбирая все большие размеры блоков.