如何计算文件的熵?

• 最后:计算数组的“平均”值。
• 用零初始化计数器, 对于数组的每个条目: 将条目的差异添加到计数器的“平均值”。

用 一些 修改可以得到香农熵:

将“平均”重命名为“熵”

(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答案的事情。(泰多克的答案在一组比特上起作用。)

假设以下变量已经存在:

• 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 不仅仅是优化。如果 计数=0 然后 p == 0 和日志(日志) 磷 )将未定义(“负无穷大”),导致错误。

• 这个 256 在召唤 math.log 表示可能的离散值的数目。由8位组成的字节可能有256个值。

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

对数基256的使用说明

该算法通常使用对数基2。这将以位为单位给出最终的答案。在这种情况下,对于任何给定的文件,最大熵为8位。亲自尝试:通过 字节计数 一览表 1 或 二 或 100 . 当文件的字节均匀分布时,您会发现有一个8位的熵。

可以使用其他对数基数。使用 乙 =2允许以位为单位的结果,因为每个位可以有2个值。使用 乙 =10将结果放入 小灵通 或十进制位,因为每个DIT有10个可能的值。使用 乙 =256将以字节为单位给出结果,因为每个字节可以有256个离散值之一。

有趣的是,使用日志标识,您可以计算出如何在单位之间转换产生的熵。任何以位为单位获得的结果都可以除以8转换为字节单位。作为一个有趣的,有意的副作用,这给熵一个介于0和1之间的值。

综上所述:

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

一个更简单的解决方案: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;
}

这是什么东西 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.
...

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

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

我迟了两年回答,所以尽管只有几张赞成票,请考虑这个问题。

简短回答: 用下面我的第1和第3个粗体公式,得到大多数人在以位表示文件的“熵”时的想法。如果你想要香农的H熵,那就用第一个方程,它实际上是熵/符号,正如他在论文中说的13次,大多数人都不知道。一些在线熵计算器使用这个,但香农的H是“特定熵”,而不是“总熵”,这引起了很多混乱。如果你想要0和1之间的答案,可以使用第一和第二个方程,它是标准化的熵/符号(它不是位/符号,而是数据“熵性质”的真实统计度量,通过让数据选择自己的对数基,而不是任意分配2、e或10)。

那里 4种熵 文件(数据)的n个符号的长与n个唯一类型的符号。但请记住,通过了解文件的内容,您就知道文件的状态,因此s=0。准确地说,如果您有一个可以生成大量数据的源,那么您可以计算该源的预期未来熵/字符。如果您在一个文件上使用下面的内容,则更准确地说,它是从该来源估计其他文件的预期熵。

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

虽然最后一个是最真实的“熵”,但第一个(香农熵H)是所有书籍所称的“熵”,没有(所需的IMHO)条件。大多数人不清楚(像香农那样)它是位/符号或每个符号的熵。称H为“熵”的说法过于笼统。

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

如其他人所说,使用标准压缩例程(如gzip)和前后分割(before and after)可以更好地度量文件中预先存在的“顺序”(order)的数量,但这会偏向于更适合压缩方案的数据。没有通用的、经过完美优化的压缩机,我们可以用来定义一个绝对的“订单”。

另一个需要考虑的问题是:如果改变了数据的表达方式,h就会改变。如果选择不同的位分组(位、半字节、字节或十六进制),h将不同。所以你除以对数,其中 n 是数据中唯一符号的数目(2表示二进制,256表示字节),h的范围为0到1(这是以每个符号的熵为单位的标准化密集香农熵)。但从技术上讲,如果256种字节中只有100种出现,那么n=100,而不是256。

h是一个“密集”的熵,也就是说,它是每一个符号,类似于 比熵 在物理学中,是每千克或每摩尔的熵。类似于物理的文件的规则“广泛”熵是s=n*h,其中 n 是文件中的符号数。h完全类似于理想气体体积的一部分。在更深的意义上,信息熵不能简单地等同于物理熵,因为物理熵允许“有序”和无序排列:物理熵产生的不仅仅是一个完全随机的熵(如压缩文件)。理想气体的一个不同方面是有一个额外的5/2因子来解释这个问题:s=k*n*(h+5/2),其中h=每个分子的可能量子态=(x p)^3/hbar*2*sigma^2,其中x=盒子的宽度,p=系统中的总非定向动量(根据动能和每个分子的质量计算),sigma=0.341不确定性原理只给出1个标准偏差内可能状态的数量。

一个小数学给出了一个文件的标准化广义熵的较短形式:

s=n*h/log(n)=sum(count_i*log(n/count_i))/log(n)

它的单位是“熵”(实际上不是一个单位)。它被规范化为一个比n*h的“熵”单位更好的通用度量,但它也不应被称为“熵”,因为正常的历史惯例是错误地称h为“熵”(这与香农文本中的澄清相反)。

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

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

计算大小为“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;
 }

重新: 我需要对整个文件的内容进行假设: (纯文本、标记、压缩或某些二进制…)

正如其他人指出的(或被迷惑/分心),我认为你实际上是在谈论 度量熵 (熵除以消息长度)。更多见 Entropy (information theory) - Wikipedia .

Jitter的评论链接到 Scanning data for entropy anomalies 与你的基本目标非常相关。最终链接到 libdisorder (C library for measuring byte entropy) . 这种方法似乎可以为您提供更多的信息,因为它显示了度量熵在文件的不同部分是如何变化的。如下图所示,4 MB JPG图像(Y轴)中256个连续字节块的熵如何随不同偏移量(X轴)而变化。在开始和结束时,熵较低,因为它是部分进入,但对于大多数文件来说,它大约是7位/字节。

来源: https://github.com/cyphunk/entropy_examples . [ 请注意,这张图和其他图可以通过小说获得。 http://nonwhiteheterosexualmalelicense.org 执照… ]

更有趣的是在 Analysing the byte entropy of a FAT formatted disk | GL.IB.LY

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

这本书似乎也相关: Detection and Recognition of File Masquerading for E-mail and Data Security - Springer

没有任何附加信息,文件的熵(根据定义)等于其大小*8位。文本文件的熵大约为*6.6位,假设:

• 每个字符的概率相等
• 字节中有95个可打印字符
• 对数(95)/对数(2)=6.6

英文文本文件的熵估计为每字符0.6到1.3位(如解释所示 here )

一般来说,您不能谈论给定文件的熵。熵是 文件集 .

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

正如尼克·丹多拉基斯建议的那样,逐字节计算熵给出了一个很差的估计,因为它假定每个字节都是独立的。例如,在文本文件中,字母后有一个小字母的可能性比字母后有空格或标点的可能性大得多,因为单词通常超过2个字符。因此,下一个字符在a-z范围内的概率与前一个字符的值相关。不要对任何实际数据使用nick的粗略估计,而是使用gzip压缩比。