如何计算文件的熵？

如何计算文件的熵? (或者说一堆字节)
我有一个想法，但我不确定它在数学上是否正确。

我的想法如下:

  • 创建一个包含256个整数(全部为零)的数组。
  • 遍历文件及其每个字节,
    增加数组中对应的位置。
  • 最后: 计算数组的“平均”值。
  • 用零初始化计数器,
    以及数组的每个条目:
    加入条目的差异 “平均”到柜台。

那么，现在我卡住了。如何“投射”这样的反结果 所有的结果都介于0.0和1.0之间，但我确定, 不管怎么说，这个想法是前后矛盾的。

我希望有人有更好更简单的解决方案？

注意: 我需要整个文件对文件内容做出假设:
(纯文本、标记、压缩或一些二进制文件)

72235 次浏览
小开

一个更简单的解决方案: gzip 文件。使用文件大小的比率: (size-of-gzip)/(size-of-first)作为随机性(即熵)的度量。

这个方法不能给出熵的确切绝对值(因为 gzip 不是一个“理想的”压缩器) ，但是如果需要比较不同来源的熵，它就足够好了。

小开
最佳答案
  • 最后: 计算数组的“平均”值。
  • 用零初始化计数器, 以及数组的每个条目: 在计数器上将条目差加到“平均值”上。

通过 一些的修改，你可以得到 Shannon 的熵:

将“平均”改名为“熵”

(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

编辑: 正如韦斯利提到的，我们必须将熵除以8，以便在 0. . 1范围内进行调整(或者，我们可以使用对数基256)。

小开

如果你使用信息论熵，注意不要在字节上使用它可能是有意义的。比如说，如果你的数据是由浮点数组成的，那么你应该为这些浮点数拟合一个概率分布，然后计算出这个分布的熵。

或者，如果文件的内容是 unicode 字符，则应该使用这些字符，等等。

小开

要计算字节集合的熵，您需要做一些类似于 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)将是未定义的(“负无穷大”) ，从而导致错误。

  • 对 math.log的调用中的 256表示可能的离散值的数目。一个由8位组成的字节将有256个可能的值。

结果值将介于0(文件中的每个字节都相同)到1之间(字节均匀地分配给每个可能的字节值)。

关于使用基于256的日志的说明

的确，这种算法通常使用日志库2。这样就得到了以位为单位的结果。在这种情况下，对于任何给定的文件，熵的最大值都是8位。自己尝试一下: 最大化输入的熵，使 byte_counts成为所有 1或 2或 100的列表。当一个文件的字节是均匀分布的，你会发现有一个8位的熵。

可以使用其他对数基。使用 B = 2允许以位表示结果，因为每个位可以有2个值。使用 B = 10将结果放在 Dits或十进制位中，因为每个 dit 有10个可能的值。使用 B = 256将以字节为单位给出结果，因为每个字节可以有256个离散值之一。

有趣的是，使用对数恒等式，您可以计算出如何在单位之间转换得到的熵。以位为单位的任何结果都可以通过除以8转换为字节单位。作为一个有趣的，有意识的副作用，这给出了熵的值介于0和1之间。

总之:

  • 你可以用不同的单位来表示熵
  • 大多数人用比特表示熵(B = 2)
    • 对于一个字节集合，最大熵为8位
    • 因为询问者希望得到0到1之间的结果，所以将这个结果除以8得到一个有意义的值
  • 上面的算法以字节为单位计算熵(B = 256)
    • 这相当于(以位为单位的熵)/8
    • 这已经给出了一个介于0和1之间的值
小开

文件的熵是不存在的。在信息论中，熵是 随机变量的函数，而不是一个固定的数据集(从技术上讲，一个固定的数据集确实有一个熵，但是那个熵将是0ーー我们可以把数据看作一个随机分布，只有一个可能的结果，概率为1)。

为了计算熵，您需要一个随机变量来建模您的文件。熵就是随机变量分布的熵。这个熵等于随机变量包含的信息位数。

小开

这是 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.
...
小开

不管怎样，下面是 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;
}
小开

没有任何额外的文件熵(根据定义)等于它的大小 * 8位。文本文件的熵大致为 * 6.6位，前提是:

  • 每个字符的可能性相等
  • 字节中有95个可打印字符
  • Log (95)/log (2) = 6.6

英文文本文件的熵估计约为每个字符0.6至1.3位(如解释的 给你)。

一般来说，你不能谈论给定文件的熵。熵是 一套文件的一个属性。

如果你需要一个熵(确切地说，是每字节一个熵) ，最好的方法是使用 gzip、 bz2、 rar 或任何其他强压缩方式压缩它，然后用未压缩的大小除以压缩的大小。这将是对熵的一个很好的估计。

正如 Nick Dandoulakis 建议的那样，逐字节计算熵给出了一个非常糟糕的估计，因为它假设每个字节都是独立的。例如，在文本文件中，字母后面有一个小字母比字母后面有一个空格或标点符号的可能性大得多，因为单词通常比2个字符长。因此，下一个字符在 a-z 范围内的概率与前一个字符的值相关。不要使用 Nick 的粗略估计来获得任何实际数据，而是使用 gzip 压缩比。

小开

计算任何大小为“长度”的无符号字符串的熵。这基本上是对 http://rosettacode.org/wiki/Entropy中的代码进行重构。我使用这个64位 IV 发生器，创建一个容量为10000000 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;
}
小开

我已经迟到两年了，所以尽管只有几张赞成票，请考虑一下。

简短的回答: 使用我下面的第一个和第三个粗体方程来得到大多数人在用比特表示文件的“熵”时所想的。如果你想得到 Shannon 的 H 熵，就用第一个方程，H 熵实际上是熵/符号，他在论文中提到了13次，大多数人都没有意识到。一些在线熵计算器使用这一个，但香农的 H 是“特定熵”，而不是“总熵”，这已经造成了如此多的混乱。如果你想要0和1之间的答案，使用第一和第二个方程，这是规范化的熵/符号(它不是比特/符号，而是一个真正的统计测量数据的“熵性质”，让数据选择自己的对数基，而不是任意分配2，e 或10)。

有 N 个符号的文件(数据)的 四种类型的熵与 n 个唯一类型的符号长。但是请记住，通过了解文件的内容，您可以知道文件的状态，因此 S = 0。准确地说，如果您有一个能够生成大量可访问数据的源，那么您可以计算该源的预期未来熵/特征。如果您对一个文件使用以下内容，则更准确地说，它是在估计来自该源的其他文件的预期熵。

  • Shannon (特定)熵 H = -1 * sum (count _ i/N * log (count _ i/N))
    其中 count _ i 是符号 i 在 N 中出现的次数。
    如果日志以2为基数，单位是位/符号; 如果是自然日志，单位是 Nats/符号。
  • 归一化比熵: H/log (n)
    单位是熵/符号。范围从0到1。1表示每个符号出现的频率相同，接近0表示除1以外的所有符号只出现一次，而一个非常长的文件的其余部分是另一个符号。日志和 H 在同一个底部。
  • 绝对熵 S = N * H
    如果 log 为基数2，则单位为位; 如果 ln () ，则单位为 nats。
  • 归一化绝对熵
    单位是“熵”，从0到 N 不等。对数和 H 在同一个基数上。

虽然最后一个是最真实的“熵”，第一个(香农熵 H)是所有书籍所谓的“熵”没有(必要的恕我直言)的限定。大多数人没有澄清(就像 Shannon 做的那样) ，它是位/符号或每个符号的熵。称 H 为“熵”说得太宽泛了。

对于每个符号频率相同的文件: S = N * H = N。这是大多数位元大型档案的情况。熵不会对数据进行任何压缩，因此完全不知道任何模式，所以000000011111111和0101000(两种情况下都是6个1和6个0)具有相同的 H 和 S。

正如其他人所说，使用像 gzip 这样的标准压缩例程，在文件之前和之后进行除法，可以更好地衡量文件中预先存在的“顺序”的数量，但是这样做会偏向于更适合压缩方案的数据。没有通用的完美优化的压缩器，我们可以用来定义一个绝对的“顺序”。

另一件需要考虑的事情是: 如果您改变了表达数据的方式，则 H 会发生变化。如果您选择不同的位组(位、点、字节或十六进制) ，H 将不同。所以除以 log (n) ，其中 N是数据中唯一符号的数量(二进制为2，字节为256) ，H 的范围从0到1(这是标准化的强化香农熵，以每个符号的熵为单位)。但是从技术上讲，如果256种类型的字节中只有100种出现，那么 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 = 系统中的总非定向动量(由每个分子的动能和质量计算) ，sigma = 0.341，符合不确定性原理，只给出1 std dev 内可能态的数目。

一个小小的数学给出了一个文件的归一化广义熵的简化形式:

S = N * H/log (n) = sum (count _ i * log (N/count _ i))/log (n)

这个单位叫做“熵”(它实际上不是一个单位)。它被归一化为比 N * H 的“熵”单位更好的通用度量。但是，在没有澄清的情况下，它也不应该被称为“熵”，因为正常的历史惯例是错误地将 H 称为“熵”(这与香农文本中的澄清相反)。

小开

回复: < strong > 我需要整个文件对文件内容做出假设: (纯文本、标记、压缩或一些二进制文件，...)

正如其他人指出的(或者被混淆/分心) ，我认为你实际上是在谈论 度量熵(熵除以信息长度)。详情请看 熵(信息论)-维基百科。

抖动的评论链接到 熵异常的扫描数据是非常相关的基本目标。最终连接到 测量字节熵的 C 库。这种方法似乎可以为您提供更多的信息，因为它显示了文件不同部分的度量熵是如何变化的。例如，这张图显示了一个4MB jpg 图像(y 轴)的256个连续字节的块的熵随不同偏移量(x 轴)的变化情况。在文件的开头和结尾，熵值较低，因为它是部分进入的，但是对于大多数文件，熵值大约是每字节7位。

enter image description here 来源: https://github.com/cyphunk/entropy_examples

更有趣的是 FAT 格式磁盘的字节熵分析 | GLIB.LY的分析和类似的图表

像整个文件和/或第一个和最后一个块的度量熵的最大值、最小值、模式和标准差这样的统计数据可能对签名非常有帮助。

这本书似乎也有相关性: 电子邮件和数据安全 Springer 中文件伪装的检测与识别

小开

这是一个基于 片段和无限战争期间发生的入侵的 Java 算法

 public static double shannon_entropy(File file) throws IOException {
byte[] bytes= Files.readAllBytes(file.toPath());//byte sequence
int max_byte = 255;//max byte value
int no_bytes = bytes.length;//file length
int[] freq = new int[256];//byte frequencies
for (int j = 0; j < no_bytes; j++) {
int value = bytes[j] & 0xFF;//integer value of byte
freq[value]++;
}
double entropy = 0.0;
for (int i = 0; i <= max_byte; i++) {
double p = 1.0 * freq[i] / no_bytes;
if (freq[i] > 0)
entropy -= p * Math.log(p) / Math.log(2);
}
return entropy;
}

usage-example:

 File file=new File("C:\\Users\\Somewhere\\In\\The\\Omniverse\\Thanos Invasion.Log");
int file_length=(int)file.length();
double shannon_entropy=shannon_entropy(file);
System.out.println("file length: "+file_length+" bytes");
System.out.println("shannon entropy: "+shannon_entropy+" nats i.e. a minimum of "+shannon_entropy+" bits can be used to encode each byte transfer" +
"\nfrom the file so that in total we transfer atleast "+(file_length*shannon_entropy)+" bits ("+((file_length*shannon_entropy)/8D)+
" bytes instead of "+file_length+" bytes).");

output-example:

文件长度: 5412字节

Shannon 熵: 4.537883805240875 nats，即最小4.537883805240875位可用于编码每个字节的传输 从文件中，我们总共传输了至少24559.027153963616位(3069.878394245452字节，而不是5412字节)。


提交答案