Sep. 15th, 2011

Некоторое время назад я заметил, что большое количество работников индустрии информационных технологий имеют крайне смутное представление о том, что такое информация, что одновременно смешно и печально. Кто-то по этому вопросу ударяется в неконструктивную философию, кто-то вспоминает полторы формулы из теории информации, не особо вникая в их смысл. Между тем, мне кажется, есть довольно хороший путь к пониманию, и этот путь пролегает через сжатие данных. Когда речь заходит о сжатии, большинство вспоминают про RLE, алгоритмы семейства LZ и коды Хаффмана (на них основана zlib, а что еще нужно?). Но это все равно что сказать "Программирование? Да-да, знаю. Фортран и Кобол".
Поскольку мне наивно кажется, что в сжатии данных я кое-что понимаю, я решил сделать образовательную серию постов, в которой мы, пользуясь школьной математикой и несколькими банальными идеями и наблюдениями, выведем некоторые важные факты теории информации и напишем на чистом функциональном языке компрессор, который будет сжимать лучше, чем zip, rar, bzip2 и 7z в их дефолтных режимах. Потом оглядимся вокруг, в том числе на физику, и в результате, надеюсь, что-то поймем об информации.

Часть 1. Изобретаем арифметик

( Read more... )

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

Сам Шеннон получил свою знаменитую формулу совсем иначе. Он рассматривал источники, выдающие сообщения с вероятностями Pi, и искал такую функцию H, которая бы выражала объем информации в сообщении, была бы мерой неопределенности.

К искомой функции он предъявлял следующие требования:
1. H должна быть непрерывной функцией от Pi.
2. Если все сообщения равновероятны, т.е. Pi = 1/N, то H(N) должна монотонно возрастать c ростом N: чем больше вариантов разных равновероятных сообщений, тем больше информации несет одно сообщение.
3. Если сообщение разбивается на несколько последовательно идущих, то мера Н информации в нем должна быть взвешенной суммой значений Н для частей. Например, если нам нужно передать сегодняшнее число, то не важно, пошлем мы месяц и день в одном сообщении или сначала месяц, а потом день, количество переданной информации должно быть одинаковым в обоих вариантах. Если вероятности и сообщения представить в виде дерева, где в узлах стоят сообщения, а дугам приписаны вероятности посылки следующих сообщений (например, из корня идут дуги к вариантам первого бита сообщения, из них - к вариантам второго бита и т.д., примерно как при построении дерева для кодов Хаффмана),

то
H(узла) = сумма по исходящим веткам от: P(ветки)*H(ветки).

Оказывается, этих требований достаточно, чтобы искомую функцию вывести.( Read more... )

(начало серии постов здесь)

В предыдущей части мы увидели, что вычисленная в лоб по вероятностям символов информационная энтропия файла дает оценку снизу по сжатию для оперирующего этими вероятностями арифметического кодера, однако простой zip умудряется сжать текст в полтора раза лучше. Все дело в том, что до этого момента мы рассматривали лишь индивидуальные символы, не обращая внимания на то, что их порядок не совсем случаен: текст состоит не из произвольной последовательности символов, а из слов языка и знаков пунктуации. Если мы прочитали последовательность букв "функц", то можем быть почти уверены, что следующая буква будет "и". Когда в английском тексте встречается буква "q", то если этот текст не про Аль-Каиду, следующая буква почти наверняка будет "u". Как это можно формализовать? Рассматривая текущий символ как случайную величину Х, можно предыдущий символ считать другой наблюдаемой одновременно с Х случайной величиной Y. Понятно, что мат.ожидание и дисперсия у них будут одинаковые, но раз они как-то связаны, можно предположить, что между ними будет корреляция. Попробуем посчитать коэффициенты корреляции для символов i и i-k:( Read more... )

(начало цикла здесь)

В предыдущей части мы довольно простыми наблюдениями и соображениями пришли к алгоритму PPM. Большая часть данных в нем сжимается в длинных контекстах, в большинстве из которых встречается не так много различных символов. При этом очень важную роль играет псевдо-символ ухода, обозначающий все еще невстреченные в данном контексте символы. Если переоценить его вероятность, то часто встречающиеся в данном контексте символы будут иметь меньшую вероятность и будут сжаты хуже. Если же недооценить вероятность ухода, то при появлении новых символов в контексте на кодирование символа ухода уйдет слишком много бит. Нужно найти наиболее адекватную оценку вероятности ухода, но фактически это значит, что нам нужно оценить вероятность события, которое еще ни разу не наступало (вероятность встречи символа, который еще ни разу не встречался). Классический тервер тут бессилен. Можно поиграть в баесианца и применить правило Лапласа или другую оценку, основанную на произвольно выбранном априорном распределении вероятностей. ( Read more... )

В предыдущих частях мы без особенных усилий построили компрессор, который жмет сильнее, чем zip, rar, bz2 и 7z в их режимах по-умолчанию. Однако примененным технологиям хоть и не 30 лет, как LZ, но не меньше 15. Куда продвинулся прогресс за это время?
( Read more... )

(этот пост следует читать только после предыдущих)

К этому моменту столько раз было произнесено слово "энтропия", что стоит взглянуть, что за ним скрывается в физике, и есть ли у нее связь с информационной энтропией помимо схожести формул.

Понятие энтропии впервые было введено Клаузиусом в классической термодинамике в середине 19-го века для того, чтобы нельзя было поставить кондиционер на паровоз и получить вечный двигатель. ( Read more... )