[пятница] Энтропия

>Правильно ли я понимаю, что теоретический предел сжатия файла равен энтропии этого файла?

Да.

Существует ли простой способ посчитать энтропию файла?

Нет.

Можно ли по отношению размера файла к его энтропии определять тип содержащихся данных?

Нет.

Существует ли простой способ посчитать энтропию файла?

Нет.

4.2

>Можно ли по отношению размера файла к его энтропии определять тип содержащихся данных? Например отличить текст на японском от картинки-битмапа в highcolour. Или это будет столь же информативно, надёжно и быстро, как степень сжатия zip-ом?

можно только определять энтропию файла.

Энтропия — мера хаотичности.

>>> Существует ли простой способ посчитать энтропию файла?

Нет.

4.2

4.2, с отправкой читать определения. Для Ъ: энтропия - это свойство не конкретного сообщения/файла, а пространства этих сообщений. Для файла можно только посчитать только его информативность. В этом вопросе полезны архиваторы - с помощью них можно получить верхнюю оценку данной величины.

>Например отличить текст на японском от картинки-битмапа в highcolour

это сравнение шила с мылом. или имеется в виду, что текст и картинка несут один и тот же смысл, и хочется сравнить эффективность представления информации?

всё можно.

кто-то даже авторство текстов определял по алгоритмам сжатия
http://www.philol.msu.ru/~lex/articles/complex.htm

>> Существует ли простой способ посчитать энтропию файла?

Вроде бы можно, даже есть несложная формула для этого. Вот только я её, хоть убейте, не помню.

> Энтропия — мера хаотичности.

Самое бесполезное из её определений :) Разве что дать заодно определение «хаотичности» и методику измерения :)

> энтропия - это свойство не конкретного сообщения/файла, а пространства этих сообщений.

То есть можно выбирать пространство — какой-то набор вероятностей для байтов и их комбинаций, и для каждого набора будет своя?

архиваторы - с помощью них можно получить верхнюю оценку данной величины.

То есть для случая, когда все байты равновероятны?

> это сравнение шила с мылом.

Можно ли отличить чёрный ящик с шилом от чёрного ящика с мылом, измеряя силу притяжения магнита к ящику? Да, если ящик не ферромагнитный.

Пример. Требуется понять, является ли файл ресурсов из игры картинкой, текстом в неизвестной кодировке, речью в PCM или ещё чем-то. 7-zip для этой цели иногда подходит. Но хочется иметь более математически обоснованный метод.

или имеется в виду, что текст и картинка несут один и тот же смысл, и хочется сравнить эффективность представления информации?

Нет.

> http://www.philol.msu.ru/~lex/articles/complex.htm

Спасибо, посмотрю, когда будет доступно.

>Пример. Требуется понять, является ли файл ресурсов из игры картинкой, текстом в неизвестной кодировке, речью в PCM или ещё чем-то. 7-zip для этой цели иногда подходит. Но хочется иметь более математически обоснованный метод.

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

> можешь сделать шумовую картинку, и хрен ты ее сожмешь или отличишь от чего-то хорошо пожатого

Само собой :)

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

Как раз об этом и спрашиваю. Занимался ли кто-либо установлением таких закономерностей? Например, для художественных текстов. И каким образом там считалась энтропия?

>И каким образом там считалась энтропия?

чем тебе определения не хватает?

>Существует ли простой способ посчитать энтропию файла?

Теоремы Шеннона для источника общего вида используются как основа энтропийного кодирования.

P.S. Всё о сжатии.

> То есть можно выбирать пространство — какой-то набор вероятностей для байтов и их комбинаций, и для каждого набора будет своя?

Ну да, если учитывать, что любой файл - это комбинация байт. Но учтите, что распределение байт даст вам не больше информации об энтропии, чем архивация.

архиваторы - с помощью них можно получить верхнюю оценку данной величины.

То есть для случая, когда все байты равновероятны?

Еще скажите, независимо распределены - тогда информативность будет тупо равняться длине. Нет, архиватор даст хорошую оценку.

> Вроде бы можно, даже есть несложная формула для этого. Вот только я её, хоть убейте, не помню.

Формула-то элементарная - это мат. ожидание информативности сообщения. А вот последнюю объективно посчитать нереально.

>>Энтропия — мера хаотичности.

Высрано с таким пафосом, что сам Шеннон зачесался бы.

Имею право.

> Правильно ли я понимаю, что теоретический предел сжатия файла равен энтропии этого файла? Существует ли простой способ посчитать энтропию файла?

Прочитай еще про Колмогоровскую сложность.

Тебя разбанили? оО

http://stackoverflow.com/questions/990477/how-to-calculate-the-entropy-of-a-file

man ent