![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Часть 2. Информационная энтропия
В предыдущей части мы на ровном месте переизобрели арифметическое сжатие и получили формулу среднего количества бит на символ при оптимальном сжатии для случая статического разбиения на интервалы. Внезапно она внешне совпала с Шенноновской формулой информационной энтропии.
Сам Шеннон получил свою знаменитую формулу совсем иначе. Он рассматривал источники, выдающие сообщения с вероятностями Pi, и искал такую функцию H, которая бы выражала объем информации в сообщении, была бы мерой неопределенности.
К искомой функции он предъявлял следующие требования:
1. H должна быть непрерывной функцией от Pi.
2. Если все сообщения равновероятны, т.е. Pi = 1/N, то H(N) должна монотонно возрастать c ростом N: чем больше вариантов разных равновероятных сообщений, тем больше информации несет одно сообщение.
3. Если сообщение разбивается на несколько последовательно идущих, то мера Н информации в нем должна быть взвешенной суммой значений Н для частей. Например, если нам нужно передать сегодняшнее число, то не важно, пошлем мы месяц и день в одном сообщении или сначала месяц, а потом день, количество переданной информации должно быть одинаковым в обоих вариантах. Если вероятности и сообщения представить в виде дерева, где в узлах стоят сообщения, а дугам приписаны вероятности посылки следующих сообщений (например, из корня идут дуги к вариантам первого бита сообщения, из них - к вариантам второго бита и т.д., примерно как при построении дерева для кодов Хаффмана),
то
H(узла) = сумма по исходящим веткам от: P(ветки)*H(ветки).
Оказывается, этих требований достаточно, чтобы искомую функцию вывести. Рассмотрим сначала ситуацию, когда все вероятности равны: Pi=1/N. Обозначим A(N) = H(1/N, 1/N, 1/N...). Тогда выбор из s^m равновероятных вариантов эквивалентен (по третьему условию) m выборам из s вариантов. Например, передача одного из s^m=256 равновероятных символов эквивалентна передаче m=8 двоичных s=2 символов. Т.е.
A(s^m) = m * A(s)
Аналогично, для некоторых других t и n
A(t^n) = n * A(t)
Мы можем вообразить сколь угодно большое n и найти такое m (для произвольных s и t), что
s^m <= t^n < s^(m+1)
Возьмем от этого всего логарифм:
m * log(s) <= n * log(t) < (m+1) * log(s)
и разделим на n*log(s):
m/n <= log(t)/log(s) < (m+1)/n
или
log(t)/log(s) - m/n < 1/n
По второму условию на H, она (и, соответственно, А) монотонна по N, а значит
A(s^m) <= A(t^n) < A(s^(m+1))
m * A(s) <= n * A(t) < (m+1) * A(s)
разделим на n * A(s) и получим
m/n <= A(t) / A(s) < m/n + 1/n
или
A(t) / A(s) - m/n < 1/n
Вычтем полученное чуть выше аналогичное неравенство для логарифмов и получим
|A(t) / A(s) - log(t) / log(s)| < 2/n
А т.к. n может быть сколь угодно большим, то
А(x) = K*log(x)
где K - произвольная положительная (чтобы соблюсти второе условие) константа. Основание для логарифма можно выбрать произвольно.
Теперь, если у нас есть выбор из n вариантов (одно из n возможных сообщений) с вероятностями Pi=Ni / M, где М - общий знаменатель для дробей, выражающих вероятности, то выбор из М равновероятных вариантов можно представить как сперва выбор из n вариантов с вероятностями P1..Pn, а затем, когда выбран вариант i, выбор из Ni равновероятных вариантов. По третьему условию, общий выбор из М можно представить двумя способами:
отсюда
Если вероятности не являются рациональными числами, то в силу условия на непрерывность для них можно получить тот же результат через рациональные числа и пределы.
Шеннон обозначил эту меру буквой Н в честь Ральфа Хартли (есть также мнение, что в честь H-теоремы Больцмана). Когда Джон фон Нейман увидел эту формулу, он сказал Шеннону: "Тебе стоит назвать ее энтропией, по двум причинам. Во-вервых, твоя функция неопределенности уже используется в статистической механике под таким названием, так что у нее уже есть имя. А во-вторых, и это более важно, никто в действительности не понимает, что такое на самом деле энтропия, поэтому в спорах у тебя всегда будет преимущество". :)
Итак, у нас есть формула, которая описывает предел сжатия для статического арифметика и одновременно служит мерой информации. Тут стоит сделать паузу и посмотреть поближе, как эта функция от вероятностей выглядит и как себя ведет при разных аргументах.
Для двоичного алфавита с вероятностью одного символа P и вероятностью другого 1-Р, H(P) выглядит так:
Пунктиром обозначены два ее слагаемых - вклад каждого из двух символов в размер сжатого сообщения. Что занятно, символ занимает больше всего места, когда его вероятность равна 1/е (в этом можно убедиться, найдя производную от -p*log2(p)), причем вне зависимости от общего числа символов.
Для алфавита из трех символов можно построить график H(p1, p2, 1-p1-p2):
Во всех случаях H=0, когда какая-то одна вероятность равна 1, а остальные 0. Максимум энтропии достигается, когда все вероятности равны: Pi=1/N, H(1/N, 1/N, ...) = log2(N).
Вот еще несколько примеров для 16 символов и разных распределений вероятностей между ними:
Можно видеть, что это действительно мера неопределенности: если мы точно знаем следующий символ (сообщение, исход), то никакой неопределенности нет, Н=0; если мы ничего не знаем и все исходы равновероятны, неопределенность максимальна, если же мы знаем что-то, что делает какие-то исходы более вероятными, чем другими, то неопределенность меньше, чем в случае полного незнания.
Имея описанный в предыдущей части range coder и зная, что для лучшего сжатия интервалы должны соответствовать вероятностям символов, можно сделать компрессор, который будет подсчитывать распределение символов в файле, сжимать его и записывать результат в файл вместе с табличкой частот символов (256 штук по 2 байта на символ). Вот полный проект с исходниками и ехе-шником: zorc.zip (Zero Order Range Coder). Там range coder немного отличается: для кодирования и декодирования использованы разные структуры, т.к. при декодировании многие переменные не используются, а изменение структуры приводит к ее копированию и создает нагрузку на сборщик мусора, поэтому лучше неиспользуемые части не копировать. Эта маленькая оптимизация улучшила скорость разжатия на 10%. Компрессор этот действительно сжимает и разжимает файлы, но как-то фигово.
Для тестов я взял пару английских текстов, найденных в Сети:
hhguide.txt (274191 байт) - "The Hitch Hiker's Guide to the Galaxy" by Douglas Adams и
meden.txt (810114 байт) - "Martin Eden" by Jack London
zorc сжал их до 161580 и 468946 байт соответственно (включая заголовок с таблицей частот), т.е. до 4.63-4.70 бита на символ. И действительно, если посчитать частоты всех символов в этих текстах и подставить вероятности в формулу для энтропии, получим 4.5-4.6 бита. zorc сжал чуть хуже, потому что оперировал немного другими вероятностями, т.к. счетчики частот пришлось уменьшить, чтобы их сумма была меньше 64к - сумма всех счетчиков должна всегда быть меньше рабочего интервала range coder'a, чтобы при вычислениях не получалось нулевых интервалов. Если подставить в формулу энтропии те вероятности, которые были использованы при сжатии, числа сойдутся с хорошей точностью.
Однако если сжать эти тексты обычным zip'ом, получится 101171 и 310056 байт, т.е. всего по 2.95 и 3.06 бита на символ, что ниже вычисленной энтропии! FAIL! Как это возможно? Разве не говорят многочисленные статьи и учебники, что энтропия - предел сжатия? Ну, если и говорят, то только совсем дурные. О том, почему это не предел, и как сжать в два раза сильнее - в следующей части.
Продолжение...
Сам Шеннон получил свою знаменитую формулу совсем иначе. Он рассматривал источники, выдающие сообщения с вероятностями Pi, и искал такую функцию H, которая бы выражала объем информации в сообщении, была бы мерой неопределенности.
К искомой функции он предъявлял следующие требования:
1. H должна быть непрерывной функцией от Pi.
2. Если все сообщения равновероятны, т.е. Pi = 1/N, то H(N) должна монотонно возрастать c ростом N: чем больше вариантов разных равновероятных сообщений, тем больше информации несет одно сообщение.
3. Если сообщение разбивается на несколько последовательно идущих, то мера Н информации в нем должна быть взвешенной суммой значений Н для частей. Например, если нам нужно передать сегодняшнее число, то не важно, пошлем мы месяц и день в одном сообщении или сначала месяц, а потом день, количество переданной информации должно быть одинаковым в обоих вариантах. Если вероятности и сообщения представить в виде дерева, где в узлах стоят сообщения, а дугам приписаны вероятности посылки следующих сообщений (например, из корня идут дуги к вариантам первого бита сообщения, из них - к вариантам второго бита и т.д., примерно как при построении дерева для кодов Хаффмана),
то
H(узла) = сумма по исходящим веткам от: P(ветки)*H(ветки).
Оказывается, этих требований достаточно, чтобы искомую функцию вывести. Рассмотрим сначала ситуацию, когда все вероятности равны: Pi=1/N. Обозначим A(N) = H(1/N, 1/N, 1/N...). Тогда выбор из s^m равновероятных вариантов эквивалентен (по третьему условию) m выборам из s вариантов. Например, передача одного из s^m=256 равновероятных символов эквивалентна передаче m=8 двоичных s=2 символов. Т.е.
A(s^m) = m * A(s)
Аналогично, для некоторых других t и n
A(t^n) = n * A(t)
Мы можем вообразить сколь угодно большое n и найти такое m (для произвольных s и t), что
s^m <= t^n < s^(m+1)
Возьмем от этого всего логарифм:
m * log(s) <= n * log(t) < (m+1) * log(s)
и разделим на n*log(s):
m/n <= log(t)/log(s) < (m+1)/n
или
log(t)/log(s) - m/n < 1/n
По второму условию на H, она (и, соответственно, А) монотонна по N, а значит
A(s^m) <= A(t^n) < A(s^(m+1))
m * A(s) <= n * A(t) < (m+1) * A(s)
разделим на n * A(s) и получим
m/n <= A(t) / A(s) < m/n + 1/n
или
A(t) / A(s) - m/n < 1/n
Вычтем полученное чуть выше аналогичное неравенство для логарифмов и получим
|A(t) / A(s) - log(t) / log(s)| < 2/n
А т.к. n может быть сколь угодно большим, то
А(x) = K*log(x)
где K - произвольная положительная (чтобы соблюсти второе условие) константа. Основание для логарифма можно выбрать произвольно.
Теперь, если у нас есть выбор из n вариантов (одно из n возможных сообщений) с вероятностями Pi=Ni / M, где М - общий знаменатель для дробей, выражающих вероятности, то выбор из М равновероятных вариантов можно представить как сперва выбор из n вариантов с вероятностями P1..Pn, а затем, когда выбран вариант i, выбор из Ni равновероятных вариантов. По третьему условию, общий выбор из М можно представить двумя способами:
отсюда
Если вероятности не являются рациональными числами, то в силу условия на непрерывность для них можно получить тот же результат через рациональные числа и пределы.
Шеннон обозначил эту меру буквой Н в честь Ральфа Хартли (есть также мнение, что в честь H-теоремы Больцмана). Когда Джон фон Нейман увидел эту формулу, он сказал Шеннону: "Тебе стоит назвать ее энтропией, по двум причинам. Во-вервых, твоя функция неопределенности уже используется в статистической механике под таким названием, так что у нее уже есть имя. А во-вторых, и это более важно, никто в действительности не понимает, что такое на самом деле энтропия, поэтому в спорах у тебя всегда будет преимущество". :)
Итак, у нас есть формула, которая описывает предел сжатия для статического арифметика и одновременно служит мерой информации. Тут стоит сделать паузу и посмотреть поближе, как эта функция от вероятностей выглядит и как себя ведет при разных аргументах.
Для двоичного алфавита с вероятностью одного символа P и вероятностью другого 1-Р, H(P) выглядит так:
Пунктиром обозначены два ее слагаемых - вклад каждого из двух символов в размер сжатого сообщения. Что занятно, символ занимает больше всего места, когда его вероятность равна 1/е (в этом можно убедиться, найдя производную от -p*log2(p)), причем вне зависимости от общего числа символов.
Для алфавита из трех символов можно построить график H(p1, p2, 1-p1-p2):
Во всех случаях H=0, когда какая-то одна вероятность равна 1, а остальные 0. Максимум энтропии достигается, когда все вероятности равны: Pi=1/N, H(1/N, 1/N, ...) = log2(N).
Вот еще несколько примеров для 16 символов и разных распределений вероятностей между ними:
Можно видеть, что это действительно мера неопределенности: если мы точно знаем следующий символ (сообщение, исход), то никакой неопределенности нет, Н=0; если мы ничего не знаем и все исходы равновероятны, неопределенность максимальна, если же мы знаем что-то, что делает какие-то исходы более вероятными, чем другими, то неопределенность меньше, чем в случае полного незнания.
Имея описанный в предыдущей части range coder и зная, что для лучшего сжатия интервалы должны соответствовать вероятностям символов, можно сделать компрессор, который будет подсчитывать распределение символов в файле, сжимать его и записывать результат в файл вместе с табличкой частот символов (256 штук по 2 байта на символ). Вот полный проект с исходниками и ехе-шником: zorc.zip (Zero Order Range Coder). Там range coder немного отличается: для кодирования и декодирования использованы разные структуры, т.к. при декодировании многие переменные не используются, а изменение структуры приводит к ее копированию и создает нагрузку на сборщик мусора, поэтому лучше неиспользуемые части не копировать. Эта маленькая оптимизация улучшила скорость разжатия на 10%. Компрессор этот действительно сжимает и разжимает файлы, но как-то фигово.
Для тестов я взял пару английских текстов, найденных в Сети:
hhguide.txt (274191 байт) - "The Hitch Hiker's Guide to the Galaxy" by Douglas Adams и
meden.txt (810114 байт) - "Martin Eden" by Jack London
zorc сжал их до 161580 и 468946 байт соответственно (включая заголовок с таблицей частот), т.е. до 4.63-4.70 бита на символ. И действительно, если посчитать частоты всех символов в этих текстах и подставить вероятности в формулу для энтропии, получим 4.5-4.6 бита. zorc сжал чуть хуже, потому что оперировал немного другими вероятностями, т.к. счетчики частот пришлось уменьшить, чтобы их сумма была меньше 64к - сумма всех счетчиков должна всегда быть меньше рабочего интервала range coder'a, чтобы при вычислениях не получалось нулевых интервалов. Если подставить в формулу энтропии те вероятности, которые были использованы при сжатии, числа сойдутся с хорошей точностью.
Однако если сжать эти тексты обычным zip'ом, получится 101171 и 310056 байт, т.е. всего по 2.95 и 3.06 бита на символ, что ниже вычисленной энтропии! FAIL! Как это возможно? Разве не говорят многочисленные статьи и учебники, что энтропия - предел сжатия? Ну, если и говорят, то только совсем дурные. О том, почему это не предел, и как сжать в два раза сильнее - в следующей части.
Продолжение...
no subject