Впервые вопрос о возможности сжатия данных поставил Клод Шеннон в своей работе, посвященной математической теории связи. В этой работе он вывел формулу, по которой подсчитывается энтропия текста (т.е. нижняя оценка среднего количества бит, необходимого для кодирования данного текста наиболее компактным образом. В этой же работе Шеннон определил понятие информации в сообщении.
Однако, Шеннон не был первым, кто задумывался о сущности информации и определении ее количества. Первый шаг на этом пути сделал в 1928 г. Хартли. Основной полученный им результат можно сформулировать примерно так: если в заданном множестве, содержащем N элементов, выделен некоторый элемент x, о котором известно лишь, что он принадлежит этому множеству, то, чтобы найти x, необходимо получить количество информации, равное log2 N. Эту формулу обычно называют формулой Хартли.
Формула Хартли является частным случаем более общей формулы Шеннона, позволяющей найти количество информации в случайном сообщении фиксированного алфавита. Пусть X1, ..., Xn - символы этого алфавита, P1, ..., Pn - вероятности их появления в тексте сообщения, тогда формула Шеннона принимает вид:
Доказательство Шеннона не было конструктивным, т.е. не содержало способа построения этих оптимальных кодов, а лишь показывало их существование.
| Изменена 19.03.2011 06:45 MSK |
|
|