如何计算位串的近似熵？
有没有一个标准的方法来做到这一点？
谷歌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()))
