Переходные зависимости

В предыдущем пункте предполагалось, что следующий символ в последователь­ности не зависит от предыдущего символа. Однако если такая зависимость суще­ствует, тогда вероятности, связанные с блоками символов, меняются. Например, рассмотрим снова алфавит X из двух символов и предположим, что к нему приме­нимы следующие переходные вероятности:

Таким образом, вероятность того, что за символом А последует символ А, рав­на 0,9; вероятность того, что за символом В последует символ А, равна 0,1 и т. д. Несложно доказать непротиворечивость матрицы переходов при вероятностях появления отдельных символов А и В, равных 0,8 и 0,2 соответственно.

Теперь разработаем код для алфавита Y, составленного из комбинаций этих символов по два. Мы получим:

На уже рассмотренном рисунке (нижний граф)показан код Хаффмана для данного случая, а в средней части таблицы — полученная в результате статистика. Обратите внимание на то, что энтропия Y меньше, чем в случае, когда следующие друг за другом символы неза­висимы (1,292 против 1,444). Поскольку вероятности для отдельных символов ос­тались теми же самыми (Ра = 0,8, Рв = 0,2), то чем это объясняется? Ответ состоит в том, что вероятности переходов добавляют информацию. Когда становится из­вестен первый символ последовательности, мы получаем больше информации о том, какой символ появится следующим. Поэтому неопределенность уменьша­ется, и суммарная энтропия также снижается. Другими словами, в последователь­ностях появляется избыточность. Так, например, существует значительная избы­точность в предложениях на английском языке.

Для случая зависимых символов средняя длина кода равна 1,44, что дает эффективность 1,292/1,44 = 0,897. В нижней части таблицы показано, что произойдет, если проигнорировать переходные вероятности и предположить, что следующие друг за другом символы независимы даже в том случае, если они зави­симы. В этом случае используются те же коды, что и для независимых символов (АА = 0, АВ =11, ВА= 100, ВВ =101). Однако теперь для второй по частоте ком­бинации ВВ используется самое длинное кодовое слово 101, поэтому средняя дли­на кодового слова оказывается равной 1,48, что больше средней длины, получав­шейся при использовании оптимального кода Хаффмана.

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