如何计算文件的熵？

Question

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

我的想法如下:

• 创建一个256个整数的数组(全为零).
• 遍历文件并为其每个字节
  增加数组中的相应位置.
• 最后:计算数组的"平均"值.
• 使用零初始化计数器,
  并为每个数组的条目:
  将条目的差异添加到计数器的"平均值".

好吧,现在我被卡住了.如何以一种所有结果介于0.0和1.0之间的方式"计划"计数器结果？但我敢肯定,这个想法无论如何都是不一致的......

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

注意:我需要整个事情来对文件的内容做出假设:(
明文,标记,压缩或一些二进制文件,......)

Answer 1

• 最后:计算数组的"平均"值.
• 使用零初始化计数器,并为每个数组的条目:将条目的差异添加到计数器的"平均值".

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

将"average"重命名为"entropy"

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

Answer 2

一个更简单的解决方案:gzip文件.使用文件大小的比率:(缩放的大小)/(原始大小)作为随机性的度量(即熵).

这种方法没有给出熵的确切绝对值(因为gzip不是"理想的"压缩器),但是如果你需要比较不同来源的熵就足够了.

Answer 3

要计算字节集合的信息熵,你需要做类似于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)将是未定义的("负无穷大"),从而导致错误.

• 的256在调用math.log表示是可能的离散值的数目.由8位组成的字节将具有256个可能的值.

结果值将介于0(文件中的每个字节相同)之间,最多为1(字节在字节的每个可能值之间均匀分配).

使用log base 256的解释

确实,这个算法通常使用log base 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之间的值

Answer 4

对于它的价值,这里是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;
}

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

Answer 6

我回答的时间已经晚了两年,所以尽管只有少数上选票,请考虑一下.

简短的回答:使用下面的第一和第三个粗体公式来得到大多数人在用比特说"文件熵"时所考虑的内容.如果你想要Shannon的H熵,那么只使用第一个等式,这实际上是熵/符号,因为他在他的论文中陈述了13次,这是大多数人都不知道的.一些在线熵计算器使用这个,但香农的H是"特定熵",而不是"总熵",这引起了很多混乱.如果你想要0到1之间的答案,使用第一和第二个等式,它是归一化的熵/符号(它不是比特/符号,而是通过让数据选择自己的日志库来对数据的"熵性质"进行真正的统计测量而不是任意分配2,e或10).

存在4种类型的 N个符号的文件(数据)的熵,其具有n种唯一类型的符号.但请记住,通过了解文件的内容,您就知道它所处的状态,因此S = 0.确切地说,如果您有一个生成大量可以访问的数据的源,那么您可以计算该源的预期未来熵/特征.如果在文件上使用以下内容,则更准确地说它正在估计来自该源的其他文件的预期熵.

• 香农(特定)熵H = -1*sum(count_i/N*log(count_i/N))
  其中count_i是符号i在N中出现的次数.
  如果log是基数2,则单位是位/符号,nats /符号如果是自然日志.
• 归一化的特定熵:H/log(n)
  单位是熵/符号.范围从0到1. 1表示每个符号经常发生,接近0表示除1之外的所有符号只出现一次,而非常长的文件的其余部分是另一个符号.该日志与H的基础相同.
• 绝对熵S = N*H
  如果log是基数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这样的标准压缩程序并在之前和之后进行划分将更好地衡量文件中预先存在的"顺序"的数量,但这会更好地适应更符合压缩方案的数据.没有通用的完美优化的压缩器,我们可以用它来定义绝对的"订单".

另一件需要考虑的事情是:如果您更改表达数据的方式,则会更改.如果选择不同的位组(位,半字节,字节或十六进制),则H将不同.所以你除以log(n),其中n是数据中唯一符号的数量(2表示二进制,256表示字节),H表示0到1(这是标准化的密集香农熵,以每个符号的熵为单位) .但从技术上讲,如果256种字节中只有100种出现,那么n = 100,而不是256.

H是一个"密集"熵,即每个符号类似于物理学中的特定熵,即每kg或每摩尔的熵.类似于物理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"熵"(这与香农文中的澄清).

Answer 7

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

为了计算熵,您需要一个随机变量来对文件进行建模.然后,熵将是该随机变量的分布的熵.该熵将等于该随机变量中包含的信息的位数.

Answer 8

如果你使用信息论熵,请注意不要在字节上使用它是有意义的.比如,如果您的数据由浮点数组成,则应该将概率分布拟合到这些浮点数并计算该分布的熵.

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