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

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

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

• 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) будет неопределенным ("отрицательная бесконечность"), вызывая ошибку.

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

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

---

объяснение использования базы журнала 256

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

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

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

в итоге:

• вы можете использовать различные единицы для выражения энтропии
• большинство людей выражают энтропию в битах (b=2)
  • для коллекции байтов это дает максимальную энтропию 8 бит
  • так как спрашивающий хочет получить результат от 0 до 1, разделите этот результат на 8 для значимого значение
• выше алгоритм вычисляет энтропию в байтах (b=256)
  • это эквивалентно (энтропия в битах) / 8
  • это уже дает значение от 0 до 1

более простое решение: gzip файл. Использовать соотношение размеры: (Размер в сжатом виде)/(размер в оригинале) как мера хаотичности (т. е. энтропии).

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

для чего это стоит, вот традиционный (бит энтропии) расчет, представленный в c#

/// <summary>
/// returns bits of entropy represented in a given string, per 
/// http://en.wikipedia.org/wiki/Entropy_(information_theory) 
/// </summary>
public static double ShannonEntropy(string s)
{
    var map = new Dictionary<char, int>();
    foreach (char c in s)
    {
        if (!map.ContainsKey(c))
            map.Add(c, 1);
        else
            map[c] += 1;
    }

    double result = 0.0;
    int len = s.Length;
    foreach (var item in map)
    {
        var frequency = (double)item.Value / len;
        result -= frequency * (Math.Log(frequency) / Math.Log(2));
    }

    return result;
}

это 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.
...

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

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

Я на два года опоздал с ответом, поэтому, пожалуйста, подумайте об этом, несмотря на всего несколько голосов.

короткий ответ: используйте мои 1-е и 3-е жирные уравнения ниже, чтобы получить то, о чем думает большинство людей, когда они говорят "энтропия" файла в битах. Используйте только 1-е уравнение, если вы хотите, чтобы энтропия Шеннона H, которая на самом деле является энтропией/символом, как он заявил 13 раз в своей статье, о которой большинство людей не знают. Некоторые онлайн-калькуляторы энтропии используют этот, но H Шеннона "специфическая энтропия", а не" полная энтропия", которая вызвала столько путаницы. Используйте 1-е и 2-е уравнение, если вы хотите получить ответ между 0 и 1, который является нормализованной энтропией/символом (это не бит/символ, а истинная статистическая мера "энтропийной природы" данных, позволяя данным выбирать свою собственную базу журналов вместо произвольного назначения 2, e или 10).

здесь 4 типа энтропии файлов (данных) из N символов длиной с n уникальными типами символов. Но имейте в виду что, зная содержимое файла, вы знаете состояние, в котором он находится, и поэтому S=0. Если у вас есть источник, который генерирует много данных, к которым у вас есть доступ, то вы можете рассчитать ожидаемую будущую энтропию/характер этого источника. Если вы используете следующее в файле, точнее сказать, что он оценивает ожидаемую энтропию других файлов из этого источника.

• Шеннон (специфические) энтропия H = -1 * sum (count_i / N * log(count_i / N))
  где count_i - это число раз, когда символ i встречался в N.
  Единицах бит/символ, если отчет является основанием 2, нац/символ, если натуральный логарифм.
• нормированная удельная энтропия: H / log (n)
  Единицы измерения-энтропия / символ. Колеблется от 0 до 1. 1 означает, что каждый символ встречается одинаково часто и около 0, где все символы, кроме 1, произошли только один раз, а остальная часть очень длинного файла была другим символом. Журнал находится в той же базе, что и Х.
• абсолютная энтропия S = N * H
  Единицы измерения-это биты, если log является базой 2, nats, если ln ()).
• нормализованная абсолютная энтропия S = N * H / log (n)
  Единица измерения - "энтропия", изменяется от 0 до N. журнал находится в той же базе, что и H.

хотя последняя является самой истинной "энтропией", первая (энтропия Шеннона H) - это то, что все книги называют" энтропией " без (необходимой имхо) квалификации. Большинство не уточняют (например Шеннон сделал), что это биты / символ или энтропия на символ. Называть H "энтропией" - это слишком вольно.

для файлов с одинаковой частотой каждого символа: S = N * H = N. Это относится к большинству больших файлов битов. Энтропия не делает никакого сжатия данных и, таким образом, полностью игнорирует любые шаблоны, поэтому 000000111111 имеет те же H и S, что и 010111101000 (6 1 и 6 0 в обоих случаях).

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

еще одна вещь, которую следует учитывать: H изменяется, если вы изменяете способ выражения данных. H будет отличаться, если вы выберете разные группы битов (биты, кусочки, байты или шестнадцатеричные). Так что вы делите за log(N), где n - это число уникальных символов в данных (2 для двоичных, 256 для байтов) и H будет колебаться от 0 до 1 (это нормированная интенсивная энтропия Шеннона в единицах энтропии на символ). Но технически, если только 100 из 256 типов байтов происходят, то n=100, а не 256.

H-это "интенсивная" энтропия, т. е. это за символ, который аналогичен удельная энтропия в физике, которая является энтропией на кг или на моль. Очередной "большой" энтропия файла, аналогичного физике, равна S=N*H, где N - количество символов в файле. H был бы точно аналогичен части идеального объема газа. Информационная энтропия не может быть просто сделана точно равной физической энтропии в более глубоком смысле, потому что физическая энтропия допускает "упорядоченные", а также неупорядоченные расположения: физическая энтропия выходит больше, чем полностью случайная энтропия (например, сжатый файл). Один аспект отличается для идеального газа там дополнительная 5/2 фактор с учетом этого: С = К * Н * (Х+5/2) где h = возможных квантовых состояний в молекуле = (хр)^3/перекладине * 2 * сигма^2 где X-ширина прямоугольника, Р=общий ненаправленный импульс в системе (рассчитывается от кинетической энергии и массы в расчете на одну молекулу), и Сигма=0.341 в соответствии с принципом неопределенности, давая только количество возможных состояний в 1 Стандартное отклонение.

немного математики дает более короткую форму нормализованной экстенсивной энтропии для a файл:

С=Н * сек / журнал(N) = сумма(count_i*лог(Н/count_i))/журнал(N)

единицы этого являются "энтропией" (которая на самом деле не является единицей). Это нормализовано, чтобы быть лучшей универсальной мерой, чем единицы "энтропии" N * H. Но это также не должно называться "энтропией" без разъяснения, потому что нормальная историческая конвенция должна ошибочно называть H "энтропией" (что противоречит разъяснениям, сделанным в тексте Шеннона).

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

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

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

как указывали другие (или были смущены / отвлечены), я думаю, что вы на самом деле говорите о метрическая энтропия (энтропия делится на длину сообщения). Смотрите больше на энтропия (теория информации) - Википедия.

комментарий джиттера ссылка на сканирование данных на энтропию аномалии очень важно для вашей основной цели. Это ссылки в конечном итоге на libdisorder (библиотека C для измерения энтропии байтов). Этот подход, казалось бы, дает вам гораздо больше информации для работы, так как он показывает, как метрическая энтропия изменяется в разных частях файла. См., например, этот график изменения энтропии блока из 256 последовательных байтов из изображения jpg размером 4 МБ (ось y) для разных смещений (ось x). В начале и конце энтропия равна ниже, как это частично, но это около 7 бит на байт для большей части файла.

Источник: https://github.com/cyphunk/entropy_examples. [обратите внимание, что этот и другие графики доступны через Роман http://nonwhiteheterosexualmalelicense.org лицензия....]

более интересным является анализ и аналогичные графики в анализ энтропии байтов форматированного диска FAT | GL.IB.LY

статистика, такая как max, min, mode и стандартное отклонение метрической энтропии для всего файла и/или первого и последнего блоков, может быть очень полезной в качестве подписи.

эта книга также представляется актуальным: обнаружение и распознавание маскировки файлов для защиты электронной почты и данных-Springer

вычисляет энтропию любой строки беззнаковых символов размера "длина". Это в основном рефакторинг кода, найденного в http://rosettacode.org/wiki/Entropy. я использую это для 64-битного генератора IV, который создает контейнер 100000000 IV без обмана и средней энтропии 3,9. http://www.quantifiedtechnologies.com/Programming.html

#include <string>
#include <map>
#include <algorithm>
#include <cmath>
typedef unsigned char uint8;

double Calculate(uint8 * input, int  length)
  {
  std::map<char, int> frequencies;
  for (int i = 0; i < length; ++i)
    frequencies[input[i]] ++;

  double infocontent = 0;
  for (std::pair<char, int> p : frequencies)
  {
    double freq = static_cast<double>(p.second) / length;
    infocontent += freq * log2(freq);
  }
  infocontent *= -1;
  return infocontent;
 }

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

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

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

In вообще нельзя говорить об энтропии данного файла. Энтропия-это свойство файлы.

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

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