Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Понятие меры информации (энтропии), алгоритм Хаффмана.

Наиболее широкое распространение при определении среднего количества информации, которое содержится в сообщениях от источников самой разной природы, получил подход. К. Шеннона. Рассмотрим следующую ситуацию.

Источник передает элементарные сигналы k различных типов. Проследим за достаточно длинным отрезком сообщения. Пусть в нем имеется N ₁ сигналов первого типа, N ₂ сигналов второго типа,..., N_k сигналов k -го типа, причем N ₁ + N ₂ +... + N_k = N – общее число сигналов в наблюдаемом отрезке, f ₁, f ₂,..., f_k – частоты соответствующих сигналов. При возрастании длины отрезка сообщения каждая из частот стремится к фиксированному пределу, т.е.

lim f_i = p_i, (i = 1, 2,..., k),

где р_i можно считать вероятностью сигнала. Предположим, получен сигнал i -го типа с вероятностью р_i, содержащий – log p_i единиц информации. В рассматриваемом отрезке i -й сигнал встретится примерно Np_i раз (будем считать, что N достаточно велико), и общая информация, доставленная сигналами этого типа, будет равна произведению Np_i log р_i. То же относится к сигналам любого другого типа, поэтому полное количество информации, доставленное отрезком из N сигналов, будет примерно равно

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

Если в формуле Шеннона принять, что

р ₁ = p ₂ =... = р_i =... = p_N = 1/ N, то

Знак минус в формуле Шеннона не означает, что количество информации в сообщении – отрицательная величина. Объясняется это тем, что вероятность р, согласно определению, меньше единицы, но больше нуля. Так как логарифм числа, меньшего единицы, т.е. log p_i – величина отрицательная, то произведение вероятности на логарифм числа будет положительным.

Кроме этой формулы, Шенноном была предложена абстрактная схема связи, состоящая из пяти элементов (источника информации, передатчика, линии связи, приемника и адресата), и сформулированы теоремы о пропускной способности, помехоустойчивости, кодировании и т.д.

В результате развития теории информации и ее приложений идеи Шеннона быстро распространяли свое влияние на самые различные области знаний. Было замечено, что формула Шеннона очень похожа на используемую в физике формулу энтропии, выведенную Больцманом. Энтропия обозначает степень неупорядоченности статистических форм движения молекул. Энтропия максимальна при равновероятном распределении параметров движения молекул (направлении, скорости и пространственном положении). Значение энтропии уменьшается, если движение молекул упорядочить. По мере увеличения упорядоченности движения энтропия стремится к нулю (например, когда возможно только одно значение и направление скорости). При составлении какого-либо сообщения (текста) с помощью энтропии можно характеризовать степень неупорядоченности движения (чередования) символов. Текст с максимальной энтропией – это текст с равновероятным распределением всех букв алфавита, т.е. с бессмысленным чередованием букв, например: ЙХЗЦЗЦЩУЩУШК ШГЕНЕЭФЖЫЫДВЛВЛОАРАПАЯЕЯЮЧБ СБСЬМ. Если при составлении текста учтена реальная вероятность букв, то в получаемых таким образом «фразах» будет наблюдаться определенная упорядоченность движения букв, регламентируемая частотой их появления: ЕЫТ ЦИЯЬА ОКРВ ОДНТ ЬЧЕ МЛОЦК ЗЬЯ ЕНВ ТША.

При учете вероятностей четырехбуквенных сочетаний текст становится настолько упорядоченным, что по некоторым формальным признакам приближается к осмысленному: ВЕСЕЛ ВРАТЬСЯ НЕ СУХОМ И НЕПО И КОРКО. Причиной такой упорядоченности в данном случае является информация о статистических закономерностях текстов. В осмысленных текстах упорядоченность, естественно, еще выше. Так, в фразе ПРИШЛ... ВЕСНА мы имеем еще больше информации о движении (чередовании) букв. Таким образом, от текста к тексту увеличиваются упорядоченность и информация, которой мы располагаем о тексте, а энтропия (мера неупорядоченности) уменьшается.