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

Question

Как рассчитать энтропию файла? (или, скажем, несколько байтов)
У меня есть идея, но я не уверен, что она математически верна.

Моя идея заключается в следующем:

• Создать массив из 256 целых чисел (все нули).
• Переход по файлу и для каждого из его байтов,
  увеличить соответствующую позицию в массиве.
• В конце: вычислить «среднее» значение для массива.
• Инициализировать счетчик с нуля,
  и для каждой записи массива:
  добавить разницу в записи «в среднем» к счетчику.

Ну, теперь я застрял. Как «спроецировать» счетчик таким образом что все результаты будут лежать между 0,0 и 1,0? Но я уверен, в любом случае идея противоречива ...

Надеюсь, у кого-то есть лучшие и более простые решения?

Примечание. Мне нужно все, чтобы сделать предположения относительно содержимого файла:
(открытый текст, разметка, сжатый или некоторый двоичный файл, ...)

Answer 1

Без дополнительной информации энтропия файла равна (по определению) его размеру * 8 битам. Энтропия текстового файла примерно равна 6,6 битам, учитывая, что:

• каждый символ одинаково вероятен
• в байте 95 печатных символов
• log (95) / log (2) = 6,6

Энтропия текстового файла на английском языке оценивается в пределах от 0,6 до 1,3 бит на символ (как объяснено здесь ).

Как правило, вы не можете говорить об энтропии данного файла. Энтропия является свойством набора файлов .

Если вам нужна энтропия (или, если быть точным, энтропия на байт), лучший способ - это сжать ее, используя gzip, bz2, rar или любое другое сильное сжатие, а затем разделить сжатый размер на несжатый размер. Это было бы отличной оценкой энтропии.

Расчет энтропийного байта за байтом, как предположил Ник Дандулакис, дает очень плохую оценку, поскольку предполагает, что каждый байт независим. Например, в текстовых файлах гораздо более вероятно иметь маленькую букву после буквы, чем пробел или пунктуацию после буквы, поскольку слова обычно длиннее 2 символов. Таким образом, вероятность того, что следующий символ окажется в диапазоне a-z, коррелирует со значением предыдущего символа. Не используйте грубую оценку Ника для каких-либо реальных данных, вместо этого используйте коэффициент сжатия gzip.