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

Ответ 1

• В конце: Вычислите "среднее" значение для массива.
• Инициализировать счетчик с нулем,    и для каждой из записей массива:    добавьте разницу в записи к "среднему" счетчику.

С некоторыми изменениями вы можете получить энтропию Шеннона:

переименуйте "средний" в "энтропию"

(float) entropy = 0
for i in the array[256]:Counts do 
  (float)p = Counts[i] / filesize
  if (p > 0) entropy = entropy - p*lg(p) // lgN is the logarithm with base 2

Edit:  Как отметил Уэсли, мы должны делить энтропию на 8, чтобы отрегулировать ее в диапазоне 0., 1 (или, альтернативно, мы можем использовать логарифмическую базу 256).

Ответ 2

Чтобы вычислить энтропию информации о наборе байтов, вам нужно будет сделать что-то похожее на ответ tydok. (ответ 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) будет undefined ( "отрицательная бесконечность" ), вызывая ошибку.

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

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

Объяснение использования базы данных 256

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

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

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

Вкратце:

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

Ответ 3

Более простое решение: gzip файл. Используйте соотношение размеров файлов: (размер-gzipped)/(размер оригинала) как меру случайности (т.е. Энтропия).

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

Ответ 4

Для чего это стоит, здесь традиционные (биты энтропии) вычисления, представленные в С#

/// <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;
}

Ответ 5

Является ли это чем-то, что 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.
...

Ответ 6

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

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

Ответ 7

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

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

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

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

Хотя последняя является самой верной "энтропией" , первая (энтропия Hannon Hannon 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 есть S = N * H, где N- количество символов в файле. H был бы точно аналогичен части идеального объема газа. Информационную энтропию нельзя просто сделать в точности равной физической энтропии в более глубоком смысле, потому что физическая энтропия допускает "упорядоченные", а также неупорядоченные механизмы: физическая энтропия выходит больше, чем полностью случайная энтропия (например, сжатый файл). Один аспект различной Для идеального газа для этого есть дополнительный 5/2 фактор: S = k * N * (H + 5/2), где H = возможные квантовые состояния на молекулу = (xp) ^ 3/hbar * 2 * sigma ^ 2 где x = ширина поля, p = общий ненаправленный импульс в системе (рассчитанный по кинетической энергии и массе на молекулу) и сигма = 0.341 в соответствии с принципом неопределенности, дающим только количество возможные состояния в пределах 1-го дека.

Небольшая математика дает более короткую форму нормализованной обширной энтропии для файла:

S = N * H/log (n) = sum (count_i * log (N/count_i))/log (n)

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

Ответ 8

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

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

Ответ 9

Вычисляет энтропию любой строки unsigned chars размером "length". Это в основном рефакторинг кода, найденного в 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;
 }

Ответ 10

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

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

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

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

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

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

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

Ответ 11

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

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

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

В общем, вы не можете говорить об энтропии данного файла. Entropy - это свойство набора файлов.

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

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