Трудность передачи информации зависит от числа возможных сообщений, которые должны быть распознаны получателем. Если это число невелико, то процесс передачи менее сложен, чем при большом числе возможных сообщений. Например, чтобы различить десять возможных сообщений, необходимо передать только одну десятичную цифру (0, 1, 2, ј, 9), а для различения 100 возможных сообщений понадобятся уже две десятичные цифры (00, 01, 02, ј, 99). Каждая дополнительная цифра позволяет увеличить число распознаваемых сообщений в 10 раз. Таким образом, количество информации, необходимой для того, чтобы мы могли различить N сообщений, растет, если говорить на математическом языке, как логарифм числа N, т.е. как log N.

Простейший список возможных сообщений состоит из двух сообщений. Чтобы передать одно из них, необходим символ, принимающий два значения. Количество информации, которую может передать источник, содержащий два равновероятных сообщения, называется битом и служит основной единицей измерения информации. Символ, представляющий такое количество информации, обычно является двоичной цифрой, 0 или 1. Один бит позволяет различать две равновероятные возможности (0, 1), два бита позволяют различать четыре возможности (00, 01, 10, 11), и т.д. Если число равновероятных возможностей равно N, то количество информации, необходимое для представления одной из них, равно log₂N битов. Например, чтобы передать одно из 32 возможных сообщений, отправитель мог бы послать получателю последовательность из log₂32 = 5 битов. Эта последовательность из 5 двоичных знаков сообщит получателю, какое из 32 возможных сообщений было передано.

Другой подход к той же проблеме можно пояснить на примере игры в 20 вопросов. Один из участников игры задумывает нечто, а другой пытается это отгадать с помощью 20 вопросов, допускающих ответы только типа «да – нет». Предположим, например, что первый из участников игры задумывает «Чарлз Диккенс». Второй участник игры может задать вопрос: «Это реальное лицо?», а затем спросить: «Этот человек жив?» и т.д. С каждым вопросом число вариантов отгадки уменьшается до тех пор, пока задуманное не будет идентифицировано. На языке теории информации можно сказать, что второй участник игры (отгадывающий задуманное) с каждым вопросом может получать самое большее один бит информации. С помощью 20 вопросов он может различить самое большее 2²⁰ (т.е. приблизительно миллион) различных объектов.

Если второй участник игры задает свои вопросы не слишком задумываясь, то ему скорее всего понадобится их гораздо больше. Например, чтобы идентифицировать один объект из миллиона возможных, может потребоваться миллион вопросов типа «Задуманный объект – это x?» Чтобы максимально использовать задаваемые вопросы, каждый вопрос должен делить множество возможных ответов примерно на две равные части. Тогда после первого вопроса останется только 500 000 возможных ответов, после второго – только 250 000, и т.д., пока, наконец, после 20-го вопроса не останется только один возможный ответ. Таким образом, в случае N равновероятных сообщений для выбора сообщения требуется около log N битов, а в игре в 20 вопросов для идентификации задуманного объекта требуется log N вопросов, допускающих ответы типа «да – нет».

Если заранее известно, что первый участник игры более чем в половине случаев задумывает «Уильяма Шекспира», то имеет смысл, задавая первый вопрос, спросить: «Это Уильям Шекспир?» Более чем в половине случаев отгадка будет найдена с помощью одного вопроса, и поэтому в среднем число вопросов окажется меньше, чем в описанной выше процедуре. Таким образом, если возможные ответы не равновероятны, то для идентификации наиболее вероятных кандидатов разумнее использовать более короткие последовательности вопросов (и, соответственно, более длинные для идентификации менее вероятных кандидатов).

Точно также и не всегда равновероятны сообщения, порождаемые источниками информации. Если одно сообщение имеет намного более высокую вероятность, чем другие, то для его идентификации мы можем использовать более короткое представление и более длинные – для других, менее вероятных. Предположим, например, что источник генерирует одно из четырех сообщений A, B, C и D с вероятностями ¹/₂, ¹/₄, ¹/₈ и ¹/₈. Каждое сообщение из этого списка можно было бы представить кодовым словом в два бита (например, представить A кодовым словом 00, B – кодовым словом 01, C – кодовым словом 10 и D – кодовым словом 11). Средняя длина такого представления составляет два бита. Мы могли бы также представить сообщение A кодовым словом 0, B – кодовым словом 10, C – кодовым словом 110 и D – кодовым словом 111. Приняв на выходе некоторую последовательность битов, получатель может решить, какое из четырех сообщений было передано. Средняя длина такого представления равна (¹/₂ ґ1) + (¹/₄ ґ2) + (¹/₈ ґ3) + (¹/₈ ґ3) = 1,75 бита. Таким образом, представление с переменной длиной кодовых слов в среднем оказывается короче, и при его достаточно продолжительном использовании мы сэкономили бы биты (1,75 по сравнению с 2). В какой-то степени это согласование имеется уже в коде Морзе, где чаще встречающиеся буквы обозначаются более короткими комбинациями точек и тире. Минимальная средняя длина представления ограничена некоторой фундаментальной величиной, называемой энтропией источника.

Источник информации можно представить в виде случайной величины X, принимающей одно из конечного числа возможных значений {1, 2, ј, m} с вероятностью p_i (p_i – вероятность того, что X = i). Энтропия случайной величины X по определению равна

где логарифмы берутся по основанию 2 и энтропия измеряется в битах. Такое определение энтропии связано с определением энтропии в термодинамике. Энтропия устанавливает нижнюю границу средней длины любого двоичного представления случайной величины.

Рассмотрим случайную величину X, принимающую значения {a, b, c} с вероятностями (¹/₂, ¹/₄, ¹/₄). Код для этой случайной величины мог бы иметь вид (0, 10, 11). Увидев строку 01001110, получатель мог бы однозначно разбить ее на 0, 10, 0, 11, 10, что декодируется в строку {a, b, a, c, b}, причем необходимости в специальном символе для обозначения конца кодированного слова не возникает. Заметим, что средняя длина такого кода составляет (¹/₂ ґ1) + (¹/₄ ґ2) + (¹/₄ ґ2) = 1,5 бита, т.е. совпадает с энтропией источника.

Так же, как мы определили энтропию одной случайной величины, можно определить энтропию последовательности, или множества, случайных величин. Коэффициент энтропии такой последовательности равен пределу отношения энтропии последовательности к числу элементов этой последовательности и называется энтропией сообщения на символ. Если случайные величины коррелированы, то энтропия последовательности меньше суммы энтропий ее элементов.

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

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

Для простоты предположим, что английский алфавит состоит из 26 букв и одного пробела. В простейшей модели все знаки равновероятны. Можно показать, что энтропия такой модели равна log 27 = 4,76 бита на букву. Но в реальном английском языке буквы не равновероятны (например, буква E встречается с большей вероятностью, чем Q). Используя относительные частоты различных букв для вычисления энтропии, мы получили бы оценку около 4,03 бита на букву. Таков был бы коэффициент энтропии, если бы буквы английского алфавита встречались независимо друг от друга.

Но это не так. Например, за буквой Q почти всегда следует U, и т.д. Воспользовавшись условными распределениями, мы могли бы построить более точную оценку коэффициента энтропии английского языка. Например, если воспользоваться моделью, в которой каждая буква зависит только от предыдущей, то получится оценка примерно в 3,3 бита на букву. Рассматривая распределение букв, которое зависит от трех предыдущих букв, мы получаем оценку примерно в 2,8 бита на букву.

Однако всю сложность зависимостей, существующих в реальном английском языке, ни одна из этих моделей полностью не передает. Зато играя в игру, аналогичную игре в 20 вопросов, и состоящую в угадывании следующей буквы, можно получить гораздо более точные оценки коэффициента энтропии английского языка. Эксперименты с образцами английских текстов показывают, что коэффициент энтропии немного больше, чем 1 бит на букву. Это означает, что в английском языке существует значительная избыточность, которую можно устранить с помощью подходящего кодирования. Например, не составляет никакого труда декодировать следующее английское предложение:

TH ј R ј ј S ј NLY ј N ј W ј Y

T ј F ј LL ј N TH ј V ј W ј LS

ј N TH ј S S ј NT ј NC ј .

IS ONLY ONE WAY

FILL IN THE VOWELS

THIS SENTENCE,

хотя почти половина букв отсутствует. Как показывают оценки коэффициента энтропии, английский язык, вообще говоря, допускает примерно четырехкратное сжатие, если воспользоваться для этого идеальным сжимающим алгоритмом. Например, 300-страничное издание Повести о двух городах Чарлза Диккенса можно было бы сократить до объема в 75 страниц такой же печати. Разумеется, в сжатом варианте буквы алфавита от A до Z использовались бы примерно одинаковое число раз, поэтому сжатый текст мог бы выглядеть, как «ZQRRLEWј». Тем не менее механизм «растяжения» позволил бы восстановить первоначальный текст Повести о двух городах слово в слово.

Непосредственное применение алгоритма Хаффмана для нахождения оптимального кода требует знания характерного для данного источника информации распределения вероятностей. Однако во многих случаях, как и в примере с английским языком, распределение вероятностей либо неизвестно, либо слишком сложно для того, чтобы его можно было использовать для кодирования. Но и в этих случаях можно придумать такие алгоритмы, которые восстанавливают распределение вероятностей по эмпирическим данным, а затем используют полученную информацию для сжатия данных. Такие алгоритмы называются универсальными. Широко известным примером может служить алгоритм Лемпеля – Зива, который не требует знания статистики источника информации и тем не менее асимптотически оптимален (см. ниже). Основная идея заключается в составлении словаря или таблицы, часто встречающихся фраз и в представлении новых фраз по их префиксам в таблице. Последовательность букв прежде всего необходимо разбить на последовательности, не встречавшиеся ранее. Например, двоичную строку 11010011011100 мы разбиваем на последовательности 1, 10, 100, 11, 0, 111, 00. Затем вместо того, чтобы передавать биты каждой фразы, мы передаем указатель фразы и значение ее последнего бита. Например, если мы используем для указателя три бита, то нашу исходную строку представляем последовательностью (000, 1), (001, 0), (010, 0), (001, 1), (000, 0), (100, 1), (101, 0) и т.д. Самое удивительное заключается в том, что, как показали А.Лемпель и Я.Зив, для всех «хороших» источников информации их алгоритм асимптотически оптимален в смысле сходимости коэффициента сжатия к энтропии. Таким образом, для всех достаточно длинных массивов алгоритм Лемпеля – Зива (не требующий никаких допущений относительно распределения вероятностей источника) позволяет достичь таких же результатов, как если бы мы заранее знали вероятностное распределение и построили для него оптимальный код.

Описанный алгоритм – лишь один из широкого класса аналогичных адаптивных алгоритмов, действующих на основе словаря и называемых алгоритмами Лемпеля – Зива. Они просты, обладают высоким быстродействием и реализуются как с помощью программного обеспечения, так и аппаратно. Их используют, чтобы «удвоить» емкость памяти для хранения данных или эффективную скорость передачи модема, поскольку в большинстве случаев они позволяют вдвое сжать английские тексты.

назад   дальше