- 创建一个256个整数的数组(全部为零)。
- 遍历文件,并对每个字节递增数组中相应位置的值。
- 最后:计算数组的“平均”值。
- 用零初始化计数器,并对数组的每个条目执行以下操作:
将条目的差异添加到“平均值”的计数器中。
希望有人有更好和更简单的解决方案?
注意:我需要整个过程来对文件内容进行假设:(明文、标记、压缩或某些二进制文件,...)
- 最后:计算数组的“平均”值。
- 将计数器初始化为零,并对数组的每个条目执行以下操作:将条目的差异添加到“平均值”中以计数器。
通过一些修改,您可以获得香农熵:
将“平均值”重命名为“熵”
(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
编辑: 正如Wesley所提到的那样,我们必须将熵除以8才能调整到0 . . 1范围内(或者我们可以使用对数基数256)。
一种更简单的解决方案:对文件进行gzip压缩。 使用文件大小比例:(压缩后大小)/(原始大小)作为随机性(即熵)的度量。
这种方法不能给出熵的准确绝对值(因为gzip不是“理想”的压缩器),但如果你需要比较不同来源的熵,那么它已经足够好了。
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)
我回答晚了两年,所以请忽略只有少数点赞的情况。
简短回答:使用下面我的第1个和第3个粗体方程式来得到大多数人在谈到文件“熵”时所想到的比特数。如果您想要Shannon的H熵,它实际上是熵/符号,正如他在他的论文中强调了13次,但大多数人并不知道。一些在线熵计算器使用这一个,但Shannon的H是“特定熵”,而不是“总熵”,这造成了很多混淆。如果您需要0到1之间的答案,则使用第1个和第2个方程式,这是归一化的熵/符号(它不是比特/符号,而是让数据选择自己的对数基数而不是任意地分配2、e或10,来衡量数据的“熵性质”的真实统计度量)。
文件(数据)的S熵共有4种类型,长度为N个符号,有n种唯一符号类型。但需要记住,通过了解文件的内容,您就知道它所处的状态,因此S=0。要精确计算期望未来的熵/字符,如果您拥有一个可以生成大量数据的源,您可以访问该源。如果您对文件使用以下内容,则更准确地说,它是从该源估计其他文件的期望熵。
H是“强度”熵,即每个符号的熵,类比于物理学中的比熵,即每千克或每摩尔的熵。文件的常规“广延”熵类似于物理学中的S,其中N是文件中符号的数量。H恰好类比于理想气体体积的一部分。信息熵不能简单地与物理熵深层次地相等,因为物理熵允许“有序”和无序排列:物理熵比完全随机的熵(例如压缩文件)更多。不同方面的一个因素对于理想气体来说还有另外一个5/2的系数来解释这一点:
S = k * N * (H+5/2),其中H = 分子的可能量子状态 = (xp)^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为“熵”(这与Shannon的文本所做的阐明相反)。
这是个计算熵值(bits of entropy)的传统方法,以下是对应的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;
}
map
中难道不应该检查空值吗?否则,Math.Log(frequency)
可能会返回-INF
。 - executifs{
Dictionary map = new Dictionary();
foreach (byte x in xs)
{
if (!map.ContainsKey(x))
{
map.Add(x,1);
}
else
{
map[x]++;
}
}
double res = 0.0f;
int len = xs.Length;
foreach (KeyValuePair item in map)
{
double freq = (double)item.Value / len;
res -= freq * (Math.Log(freq)/Math.Log(2));
}
return res;
}```
熵-香农熵的计算方法:
- evandrix8 = -log_2(1/2^8)
,最少为0 = -log_2(1/1)
。也许这一点需要澄清。 - undefined这个东西可以用 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)。
为了计算熵,您需要使用随机变量来对文件进行建模。然后,熵将是该随机变量分布的熵。这个熵将等于该随机变量所包含的信息位数。
如果您使用信息论熵,要注意不要将其用于字节。比如,如果您的数据由浮点数组成,应该拟合一个概率分布并计算该分布的熵。
或者,如果文件内容是Unicode字符,则应使用它们等。
回复:我需要整个文件来推断其内容:(明文、标记、压缩或二进制等)
正如其他人所指出的(或者被困惑/分散注意力),我认为你实际上在谈论的是度量熵(熵除以消息长度)。请参见熵(信息理论)- 维基百科了解更多信息。
jitter的评论链接到扫描熵异常数据与您的根本目标非常相关。该链接最终将链接到libdisorder(用于测量字节熵的C库)。这种方法似乎会给您提供更多的信息,因为它显示了不同部分的度量熵如何变化。例如,查看此图表,其中显示了来自4 MB jpg图像的256个连续字节块的熵(y轴)如何随偏移量(x轴)而变化。在开头和结尾,熵较低,但在大部分文件中每个字节的熵约为7位。
来源:https://github.com/cyphunk/entropy_examples。[请注意,此图表和其他图表可通过新颖的http://nonwhiteheterosexualmalelicense.org许可证获得。]
更有趣的是在分析FAT格式磁盘字节熵 | GL.IB.LY中类似的分析和图表。
整个文件和/或其第一个和最后一个块的度量熵的最大值、最小值、模式和标准偏差等统计数据可能非常有用作为签名。
这本书也似乎很相关:检测和识别用于电子邮件和数据安全的文件伪装 - Springer
计算给定长度的无符号字符串的熵。该代码基本上是对 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;
}
注意:我需要整个文件来对其内容进行假设:(纯文本、标记、压缩或某些二进制...)
... 你刚刚要求了神一般的魔力,祝你开发出可证明最优数据压缩的好运。 - MickLH