如何计算位串的近似熵?

有没有一个标准的方法来做到这一点?

谷歌search – “近似熵”位 – 揭示了多篇学术论文,但我只想find一个伪代码块定义任意长度的给定位串的近似熵。

(如果这说起来容易做起来并且取决于应用程序,我的应用程序涉及16,320位encryption数据(密文),但作为一个谜题encryption,并不意味着不可能破解,我想我会先检查熵,但是很难find这样的好的定义,所以这似乎是一个应该在StackOverflow上的问题!从开始去除混合16k随机表示位的想法也是受欢迎的…)

另请参阅以下相关问题:
什么是熵的计算机科学定义?

熵不是你得到的string的属性,而是你可能获得的string的属性。 换句话说,它限定了string生成的过程。

在简单情况下,在一组N个可能的string中,您将得到一个string,其中每个string具有相同的被select概率,即1 / N。 在这种情况下,string被认为具有N的熵。 熵通常以比特尺寸表示,这是一个对数尺度:“ n比特”的熵是一个等于2 n的熵。

例如:我喜欢生成我的密码为两个小写字母,然后两个数字,然后两个小写字母,最后两个数字(例如va85mw24 )。 字母和数字是随机的,统一的,彼此独立的。 这个过程可能会产生26 * 26 * 10 * 10 * 26 * 26 * 10 * 10 = 4569760000不同的密码,并且所有这些密码都有相同的select机会。 这样的密码的熵是4569760000,这意味着大约32.1比特。

香农的熵方程是标准的计算方法。 下面是Python中的一个简单的实现,从启示代码库中无耻复制,从而GPL许可:

 def entropy(string): "Calculates the Shannon entropy of a string" # get probability of chars in string prob = [ float(string.count(c)) / len(string) for c in dict.fromkeys(list(string)) ] # calculate the entropy entropy = - sum([ p * math.log(p) / math.log(2.0) for p in prob ]) return entropy def entropy_ideal(length): "Calculates the ideal Shannon entropy of a string with given length" prob = 1.0 / length return -1.0 * length * prob * math.log(prob) / math.log(2.0) 

请注意,这个实现假定你的input比特stream最好用字节表示。 这可能会也可能不是您的问题域的情况。 你真正想要的是你的比特stream转换成一串数字。 你是如何决定这些数字是特定领域的。 如果你的数字真的只有一个零,那么把你的比特stream转换成一个1和0的数组。 但是,您select的转换方法会影响您获得的结果。

我相信答案是string的Kolmogorov复杂性 。 这不仅是一个伪代码块,Kolmogorov复杂性不是一个可计算的function !

在实践中你可以做的一件事就是用最好的可用数据压缩algorithm压缩比特串。 它越压缩熵越低。

没有单一的答案。 熵总是相对于某个模型。 当有人谈到熵有限的密码时,他们的意思是“相对于智能攻击者预测的能力”,它总是一个上限。

你的问题是,你试图测量熵来帮助你find一个模型,这是不可能的。 熵度量能告诉你什么是一个好的模型。

话虽如此,有一些相当通用的模型,你可以尝试; 他们被称为压缩algorithm。 如果gzip可以很好地压缩你的数据,你至less可以find一个可以预测的模型。 例如gzip对简单的replace大多不敏感。 它可以在文本中经常处理“wkh”,就像处理“the”一样容易。

对不起,花了这么长时间回答这个问题。

看看我最近的论文:

“双熵 – 有限二进制串的近似熵”

http://arxiv.org/abs/1305.0954

“我们devise,实现和testing了一个简单algorithm,该algorithm计算任意长度的有限二进制串的近似熵,该algorithm使用串的Shannon熵和串的最后一个二进制导数的加权平均值。在素数理论(我们明确certificate质数序列不是周期性的),人类视觉,密码学,随机数生成和量化金融领域testingalgorithm“

NIST随机数生成器评估工具包有一个计算“近似熵”的方法。 这里是简短的描述:

近似熵testing描述:该testing的重点是每个重叠的m位模式的频率。 testing的目的是比较两个连续/相邻长度(m和m + 1)的重叠块的频率与随机序列的预期结果的频率。

有关更详尽的解释,请参阅本页面上的PDF :

http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

这里是Python的一个实现(我也将它添加到Wiki页面):

 import numpy as np def ApEn(U, m, r): def _maxdist(x_i, x_j): return max([abs(ua - va) for ua, va in zip(x_i, x_j)]) def _phi(m): x = [[U[j] for j in range(i, i + m - 1 + 1)] for i in range(N - m + 1)] C = [len([1 for x_j in x if _maxdist(x_i, x_j) <= r]) / (N - m + 1.0) for x_i in x] return -(N - m + 1.0)**(-1) * sum(np.log(C)) N = len(U) return _phi(m) - _phi(m + 1) 

例:

 >>> U = np.array([85, 80, 89] * 17) >>> ApEn(U, 2, 3) -1.0996541105257052e-05 

上面的例子与维基百科上给出的例子一致。

用这个公式的一个单词的玻尔兹曼熵: http : //imgur.com/a/DpcIH

这是一个O(n)algorithm来计算它:

 import math from collections import Counter def entropy(s): l = float(len(s)) return -sum(map(lambda a: (a/l)*math.log2(a/l), Counter(s).values()))