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

Более простое решение: заархивируйте файл. Используйте соотношение размеров файлов: (size-of-gzipped) / (size-of-original) в качестве меры случайности (т. Е. Энтропии).

Этот метод не дает вам точного абсолютного значения энтропии (поскольку gzip не является «идеальным» компрессором), но его достаточно, если вам нужно сравнить энтропию разных источников.

Может ли ent справиться с этим? (Или, возможно, он недоступен на вашей платформе.)

$ dd if=/dev/urandom of=file bs=1024 count=10
$ ent file
Entropy = 7.983185 bits per byte.
...

В качестве встречного примера приведу файл без энтропии.

$ dd if=/dev/zero of=file bs=1024 count=10
$ ent file
Entropy = 0.000000 bits per byte.
...

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

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

Чтобы вычислить информационную энтропию набора байтов, вам нужно сделать что-то похожее на ответ Тайдока. (Ответ tydok работает с набором битов.)

Предполагается, что следующие переменные уже существуют:

• byte_counts - это 256-элементный список количества байтов с каждым значением в вашем файле. Например, byte_counts [2] - это количество байтов, которые имеют значение 2 .

• total - общее количество байтов в вашем файле.

Я напишу следующий код на Python, но должно быть очевидно, что происходит.

import math

entropy = 0

for count in byte_counts:
    # If no bytes of this value were seen in the value, it doesn't affect
    # the entropy of the file.
    if count == 0:
        continue
    # p is the probability of seeing this byte in the file, as a floating-
    # point number
    p = 1.0 * count / total
    entropy -= p * math.log(p, 256)

Есть несколько важных моментов, на которые стоит обратить внимание.

• Проверка на count == 0 не выполняется. просто оптимизация. Если count == 0 , то p == 0 , и log ( p ) будет неопределенным ("отрицательная бесконечность"), что приведет к ошибке.

• 256 в вызове math.log представляет количество возможных дискретных значений. Байт, состоящий из восьми битов, будет иметь 256 возможных значений.

Результирующее значение будет от 0 (каждый байт в файле одинаков) до 1 (байты равномерно делятся между всеми возможными значениями байта) .

Объяснение использования логарифмической базы 256

Верно, что этот алгоритм обычно применяется с логической базой 2. Это дает результирующий ответ в битах. В таком случае у вас есть максимум 8 бит энтропии для любого данного файла. Попробуй сам: максимизируйте энтропию ввода, сделав byte_counts списком всех 1 или 2 или 100 . Когда байты файла распределены равномерно, вы обнаружите, что энтропия равна 8 битам.

Можно использовать другие основы логарифма. Использование b = 2 позволяет получить результат в битах, поскольку каждый бит может иметь 2 значения. Использование b = 10 помещает результат в dits или десятичных битах, поскольку для каждой dit имеется 10 возможных значений. Использование b = 256 даст результат в байтах, поскольку каждый байт может иметь одно из 256 дискретных значений.

Интересно, что, используя идентификаторы журнала, вы можете решить, как преобразовать результирующую энтропию между единицами измерения. Любой результат, полученный в единицах битов, может быть преобразован в единицы байтов путем деления на 8. Что интересно,

• Для набора байтов это дает максимальную энтропию в 8 бит
• Поскольку запрашивающий хочет результат от 0 до 1, разделите этот результат на 8 для получения значимого значения

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

Или, если содержимое файла состоит из символов Юникода, вы должны использовать их и т. Д.