Как практически измерить энтропию файла?

Я пытаюсь измерить много не избыточной (фактической) информации, содержащейся в моем файле. Некоторые называют это количеством энтропии.

Конечно, существует стандарт p (x) log {p (x)}, но я думаю, что Шеннон рассматривал его только с точки зрения передачи по каналу. Следовательно, формула требует размер блока (скажем, в битах, обычно 8). Для большого файла этот расчет довольно бесполезен, игнорируя корреляции между символами на короткие и длинные расстояния.

Существуют методы двоичного дерева и метода Зива-Лемпеля, но они кажутся высоко академическими по своей природе.

Сжимаемость также рассматривается как мера энтропии, но, похоже, не существует нижнего предела в отношении степени сжатия. Для моего файла hiss.wav,

оригинал hiss.wav = 5,2 МБ
энтропия по формуле Шеннона = 4,6 МБ
hiss.zip = 4,6 МБ
hiss.7z = 4,2 МБ
hiss.wav.fp8 = 3,3 МБ

Есть ли какой-нибудь разумный практический метод измерения того, сколько энтропии существует в hiss.wav?

entropy Пол Ушак
источник

Я не понимаю, что вы подразумеваете под "высоко академическим".

Дэвид Ричерби

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

Пол Ушак,

$x$

$N$ $N$ $H$ $N$ $HN + o(N)$ gzip

Благодаря этому результату Лемпеля и Зива энтропия источника может быть аппроксимирована путем сжатия длинной последовательности выборок с использованием алгоритма Лемпеля – Зива. Это не оценивает энтропию конкретных выборок, что не является четко определенным понятием (постоянная последовательность имеет нулевую энтропию), а скорее является энтропией источника, ее генерирующего.

Связанное понятие - алгоритмическая энтропия , также известная как сложность Колмогорова . Это длина самой короткой программы, генерирующей ваш файл. Это количество имеет смысл для отдельного файла. В случае файла, сгенерированного случайным источником, теорема Лемпеля – Зива показывает, что алгоритмическая энтропия файла с высокой вероятностью ограничена его энтропией Шеннона. К сожалению, алгоритмическая энтропия не вычислима, поэтому это скорее теоретическая концепция.

Чтобы завершить картину, я предлагаю прочитать статью Шеннона по прогнозированию и энтропии печатного английского языка для другого подхода к оценке энтропии источника.

Юваль Фильмус
источник

Я имею. И бумага Шурмана и Грассбергера. Судя по их оценкам энтропии для английского языка, наилучшая оценка энтропии, которую мы можем получить, - это сжатие с использованием варианта PAQ8, например, fp8. Там и мои результаты довольно удачно выходят за шекспировскую прозу.

Пол Ушак,

Кажется, проблема в том, что я бы подумал, что должна существовать ограничивающая теоретическая ценность для энтропии источника. Определение по сжатию отражает только эффективность алгоритма сжатия. Опытным путем ваш gzip хорош, но 7z лучше. И fp8 намного лучше, как показано в моем вопросе. Могу ли я обнаружить, что hiss.wav содержит только 10 байтов полной энтропии, когда я использую fp12000 в далеком будущем?

Пол Ушак

Энтропия не является свойством файла; каждый отдельный файл имеет нулевую энтропию. Скорее энтропия является свойством случайного источника. Мера случайности, которая подходит для конкретных файлов, - это колмогоровская сложность (также известная как алгоритмическая энтропия), но, к сожалению, эта мера не вычислима.

Юваль Фильмус

Когда вы сжимаете файл для оценки энтропии источника, вы используете теорему, которая гарантирует, что скорость сжатия данных, сгенерированных источником, приближается к энтропии источника. Однако настоящие утилиты сжатия не применяют ванильный алгоритм Лемпеля-Зива, а скорее более практичную версию его. Если вы хотите оценить энтропию, возможно, вам следует переопределить алгоритм с этой целью.

Юваль Фильмус

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

Рафаэль

Как практически измерить энтропию файла?

Ответы: