如何计算位串的近似熵?

过程 通过它生成字符串。

N 可能的字符串,其中每个字符串的被选择概率与其他字符串相同,即。 . 在这种情况下,弦的熵为 N . 熵通常用位来表示,这是一个对数标度:一个 n 位”是一个熵等于 ⁿ

例如:我喜欢将密码生成为两个小写字母,然后是两个数字,然后是两个小写字母,最后是两个数字(例如。 va85mw24 ). 字母和数字是随机、统一和独立选择的。这个过程可以产生26*26*10*10*26*26*10*10=456976000个不同的密码,所有这些密码被选择的机会都是相等的。这样一个密码的熵是456976000,这意味着大约32.1位。

Shannon's entropy equation 是标准的计算方法。下面是一个简单的Python实现,无耻地从 Revelation

import math


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)

注意,这个实现假设您的输入位流最好用字节表示。你的问题域可能是这样,也可能不是这样。你真正想要的是把你的比特流转换成一串数字。你如何决定这些数字是特定领域的。如果你的数字真的只有1和0,那么把你的比特流转换成1和0的数组。但是,您选择的转换方法将影响您得到的结果。

Kolmogorov Complexity 一根绳子。 这不仅不能用一大块伪代码来回答,而且Kolmogorov的复杂性也不是一个问题 computable function

在实践中,您可以做的一件事是用可用的最佳方法压缩位字符串 data compression 算法。 压缩越多,熵就越低。

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

话虽如此,有一些相当通用的模式,你可以尝试;它们被称为压缩算法。如果gzip能够很好地压缩数据,那么至少有一个模型能够很好地预测数据。例如,gzip对简单的替换基本上是不敏感的。它可以处理文本中频繁出现的“wkh”和处理“the”一样容易。

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

近似熵测试描述:本测试的重点是 每个重叠m位模式的频率。目的 测试的目的是比较两组重叠块的频率 与预期结果相反的连续/相邻长度(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

上面的例子与 the example given on Wikipedia .

用这个公式计算单词的香农熵: http://imgur.com/a/DpcIH

这里有一个O(n)算法来计算它:

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