如何计算文件的熵?

如何计算文件的熵? (或者让我们只是说一堆字节)
我有一个想法,但我不确定这是math上正确的。

我的想法如下:

  • 创build一个256个整数的数组(全零)。
  • 遍历文件和每个字节,
    增加数组中的相应位置。
  • 最后:计算数组的“平均”值。
  • 用零初始化一个计数器,
    并为每个数组的条目:
    将该条目的差异添加到“平均”到柜台。

那么,现在我卡住了。 如何“计划”柜台的结果是所有的结果都在0.0到1.0之间? 但我确定,这个想法是不一致的

我希望有人有更好更简单的解决scheme?

注意:我需要对文件内容进行假设:
(明文,标记,压缩或一些二进制,…)

  • 最后:计算数组的“平均”值。
  • 用0初始化一个计数器,并为每个数组的条目添加条目的差异到“平均”的计数器。

通过一些修改,你可以得到香农的熵:

重新命名“平均”到“熵”

 (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)。

要计算字节集合的信息熵,你需要做一些类似tydok的答案。 (tydok的答案适用于一些比特。)

假定以下variables已经存在:

  • 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(“negative infinity”),导致错误。

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

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


对日志库256的使用的解释

确实,这个algorithm通常是使用log base 2来应用的。这就给出了结果的答案。 在这种情况下,对于任何给定的文件,最多有8位熵。 尝试一下:通过将byte_counts列为全部12100最大化input的熵。 当一个文件的字节均匀分布时,你会发现有一个8位的熵。

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

有趣的是,使用日志身份,你可以计算出如何转换单位之间的结果熵。 任何以位为单位的结果都可以通过除以8来转换为字节单位。作为一个有意思的有意的副作用,这给出了熵为0和1之间的值。

综上所述:

  • 你可以用不同的单位表示熵
  • 大多数人用比特表示熵( b = 2)
    • 对于字节的集合,这给出了8位的最大熵
    • 由于提问者需要0和1之间的结果,因此将结果除以8得到有意义的值
  • 上面的algorithm以字节为单位计算熵( b = 256)
    • 这相当于(熵位)/ 8
    • 这已经给出了一个介于0和1之间的值

更简单的解决scheme:gzip文件。 使用文件大小比例(gzipped大小)/(原始大小)作为随机性度量(即,熵)。

这种方法并不能给你熵的确切的绝对值(因为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; } 

这个东西可以处理吗? (或者也许在您的平台上不可用。)

 $ 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. ... 

没有文件的熵这样的东西。 在信息论中,熵是一个随机variables的函数,而不是一个固定的数据集(在技术上,一个固定的数据集确实有一个熵,但是这个熵会是0-我们可以把数据视为一个随机分布只有一个概率为1)的可能结果。

为了计算熵,你需要一个随机variables来build模你的文件。 那么熵就是随机variables分布的熵。 这个熵等于该随机variables中包含的信息的位数。

我迟到了两年,所以请考虑这个,尽pipe只有几个回应。

简短的回答:使用下面的第一个和第三个粗体公式来获得大多数人在考虑文件的“熵”位时所考虑的内容。 如果你想要Shannon的H熵,实际上是熵/符号,就可以用第一个方程,正如他在他的论文中提到的那样,大多数人都不知道。 一些在线熵计算器使用这个,但香农的H是“特定的熵”,而不是“总熵”造成了这么多的困惑。 如果你想要0和1之间的答案是归一化的熵/符号(这不是比特/符号,而是通过让数据select自己的对数基而不是任意分配2,e或10)。

有n种符号的文件(数据)的4种types的熵 ,具有n种独特types的符号。 但请记住,通过了解文件的内容,您知道它所处的状态,因此S = 0。 确切地说,如果你有一个能够产生大量数据的来源,那么你就可以计算出该来源的预期未来的熵/特性。 如果在文件中使用以下内容,则更准确地说它是估计来自该源的其他文件的预期熵。

  • 香农(特定)熵H = -1 * sum(count_i / N * log(count_i / N))
    其中count_i是在N中出现的符号的次数。
    如果日志是基数2,则单位是位/符号,如果是自然对数,则为nats /符号。
  • 归一化特定熵: H / log(n)
    单位是熵/符号。 范围从0到1. 1表示每个符号出现的频率相同,接近0表示除了1之外的所有符号只出现一次,其余的很长的文件是另一个符号。 日志与H相同。
  • 绝对熵S = N * H
    如果日志是基数2,则单位是比特,如果是ln(),则单位是nats。
  • 归一化绝对熵S = N * H / log(n)
    单位是“熵”,从0到N不等。日志与H相同。

虽然最后一个是最真实的“熵”,但是第一个(香农熵H)是所有书籍都没有(所需的恕我直译)资格所谓的“熵”。 大多数人不会澄清(像香农那样)每个符号是比特/符号还是熵。 调用H“熵”的说法太松散了。

对于每个符号具有相同频率的文件:S = N * H = N。对于大多数大比特文件,情况就是如此。 熵不对数据进行任何压缩,因此完全不了解任何模式,所以000000111111具有与010111101000相同的H和S(在这两种情况下都是6 1和6 0)。

就像其他人所说的那样,使用像gzip这样的标准压缩程序和之前和之后的分割将会更好地度量文件中预先存在的“顺序”的数量,但是这对于更好地适合压缩scheme的数据是有偏见的。 没有通用的完美优化压缩机,我们可以用它来定义一个绝对的“订单”。

另一件需要考虑的事情是:如果你改变expression数据的方式,H就会改变。 如果select不同的位组(位,半字节,字节或hex),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 =系统中的总的无方向动量(由每个分子的动能和质量计算),σ= 0.341,符合不确定性原则,只给出1 std dev内可能的状态。

一个小math给出一个文件的归一化广义熵的较短forms:

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

这个单位是“熵”(这不是一个单位)。 它被归一化为比N * H的“熵”单位更好的通用衡量标准。但是,由于正常的历史惯例错误地称为H“熵”,所以它也不应该被称为“熵”在香农的文本中作出的澄清)。

如果您使用信息论熵,请注意不要在字节上使用它。 比方说,如果你的数据是由浮点数组成的,你应该把概率分布拟合到那些浮点数上,然后计算这个分布的熵。

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

计算大小为“length”的任何无符号string的熵。 这基本上是http://rosettacode.org/wiki/Entropy上的代码的重构&#x3002; 我使用这个64位IV发生器,创build了一个容量为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; } 

回复: 我需要整个事情做文件的内容假设(明文,标记,压缩或一些二进制,…)

正如其他人指出的(或被困惑/分心),我想你实际上是在谈论度量熵 (熵除以消息的长度)。 在熵(信息论) – 维基百科上查看更多信息 。

抖动的评论链接到扫描数据的熵exception是非常相关的基本目标。 最终链接到libdisorder(用于测量字节熵的C库) 。 这种方法似乎给了你更多的信息来处理,因为它显示了度量熵在文件的不同部分是如何变化的。 例如,查看来自4MB jpg图像(y轴)的256个连续字节的块的熵如何针对不同的偏移(x轴)而改变的图。 在开始和结束时,熵是较低的,因为它的中间部分,但大多数文件大约是每个字节7位。

在这里输入图像说明 来源: https : //github.com/cyphunk/entropy_examples 。 [ 请注意,这个和其他图可以通过小说http://nonwhiteheterosexualmalelicense.org许&#x53EF;…. ]

更有趣的是在分析FAT格式化磁盘的字节熵时的分析和类似图 GL.IB.LY

像整个文件和/或其第一个和最后一个块的度量熵的最大值,最小值,模式和标准偏差的统计可能作为签名是非常有用的。

这本书也似乎相关: 检测和识别电子邮件和数据安全的文件伪装 – 施普林格

没有任何额外的信息熵(根据定义)等于其大小* 8位。 文本文件的熵大致是6.6 *位,因为:

  • 每个angular色是相同的可能性
  • 字节中有95个可打印的字符
  • log(95)/ log(2)= 6.6

英文文本文件的熵估计是每个字符大约0.6到1.3比特(如这里所解释的)。

一般来说,你不能谈论给定文件的熵。 熵是一组文件的属性。

如果你需要一个熵(或每个字节的熵),最好的方法是使用gzip,bz2,rar或任何其他强压缩来压缩它,然后将压缩的大小除以未压缩的大小。 这将是一个伟大的熵估计。

如Nick Dandoulakis所build议的那样,逐字节地计算熵给出了一个很差的估计,因为它假设每个字节都是独立的。 例如,在文本文件中,字母之后的小写字母比字母之后的空白或标点符号更可能,因为单词通常长于2个字符。 因此,下一个字符在z范围内的概率与前一个字符的值相关。 不要使用Nick对任何实际数据的粗略估计,而是使用gzip压缩比率。