Неопеределенность Клода Шеннона


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



Все началось с моего давнего хорошего друга, Клода Шеннона, который в 1948 году заложил фундамент нового, в то время неизвестного, научного направления – теории информации. Для многих страждущих сей факт послужил предметом многих и долгих споров. Ведь как же так? Человечество привыкло воспринимать информацию лишь качественно, но никак не количественно. Как часто это бывало, сама мысль о теории информации настигла Шеннона во время работы над правительственным проектом в области криптографии. Во времена Второй Мировой Войны. Война - извечный двигатель прогресса.



Вклад Шеннона в современную жизнь невероятно велик. Информация повсюду - она управляет, создает, уничтожает, является ключом ко всему. Скорость и точность ее передачи – жизненно важные характеристики современного мира. Шеннон не просто придал информации математическую форму, но и доказал ряд гениальных теорем, практическую пользу от которых человечество получило лишь спустя много лет, с приходом интегральных микросхем и больших вычислительных ресурсов. Обязательно прочтите его биографию.



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



Информационная энтропия - мера неопределённости информации. Например, у вас есть источник, который генерирует поток символов некоторого алфавита. Алфавит состоит из 5 элементов и известно, что один из символов в рамках данного алфавита имеет гораздо большую вероятность появления, допустим 0.5, а другие делят между собой 0.1 и 0.2. Тогда неопределенность появления символа с большей вероятностью мала, но велика для других символов. То есть появление первым символа с вероятностью 0.1 станет большей неожиданностью.



Математически двоичная энтропия символа a с вероятностью появления p(a) определяется не иначе как







Оперируя понятием энтропии теория информации предсказывает среднее количество бит для оптимального сжатия символа алфавита. Строка s = a1a1a1a2a3a4a4a5 состоящая из 8 элементов рассмотренного выше алфавита будет иметь следующую энтропию:







Значение энтропии показывает среднее минимальное количество бит требуемых для шифрования или оптимального сжатия строки без потери информации. В нашем примере она равна 27 битам. Размерность энтропии (бит) вытекает из основания логарифма равного 2.



Для наглядной иллюстрации возьмем алфавит из двух символов. Вероятности символов определяют энтропию алфавита. Равновероятные символы порождают максимальную энтропию и минимальное количество бит необходимое для кодирования символа алфавита равно 1. Во втором случае энтропия минимальна, так как известно, что символ a1 почти всегда будет выходом с источника. Количество требуемых бит для кодирования символа составляет 0.08 бита. Третий случай подобен первому и имеет очень высокий показатель энтропии.







Заметим, что получаемая цифра лишь теоретическая оценка. Для практического применения еще необходимо разработать алгоритм, который будет ей удовлетворять.



Ну, и наконец, что же за процесс такой – «энтропийное кодирование»? Известная теорема Шеннона гласит, что «существует предел сжатия без потерь, зависящий от энтропии источника». То есть чем более предсказуема получаемая информация, тем лучше её можно сжать. Таким образом, энтропийное кодирование есть процесс максимизации энтропии символов исходного сигнала путем усреднения вероятностей их появления с источника.



Гений.


For more complete information about compiler optimizations, see our Optimization Notice.