50

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

谷歌搜索—— “近似熵”位——发现了多篇学术论文，但我只想找到一段伪代码，为给定的任意长度的位串定义近似熵。

（如果说起来容易做起来难，并且取决于应用程序，我的应用程序涉及 16,320 位加密数据（密文）。但加密是一个谜题，并不是不可能破解的。我想我先检查一下熵，但不容易找到一个好的定义。所以这似乎是一个应该在 StackOverflow 上的问题！也欢迎从哪里开始解密 16k 随机看似位的想法......）

另请参阅此相关问题：
熵的计算机科学定义是什么？

4

7 回答 7

37

熵不是你得到的字符串的属性，而是你可以得到的字符串的属性。换句话说，它限定了生成字符串的过程。

在简单的情况下，您会在一组N个可能的字符串中得到一个字符串，其中每个字符串具有相同的被选中概率，即1/N。在这种情况下，字符串的熵被称为N。熵通常以位表示，这是一个对数标度：“ n位”的熵是等于2 n的熵。

例如：我喜欢将密码生成为两个小写字母，然后是两个数字，然后是两个小写字母，最后是两个数字（例如va85mw24）。字母和数字是随机、统一且彼此独立选择的。这个过程可能会产生 26*26*10*10*26*26*10*10 = 4569760000 个不同的密码，并且所有这些密码都有相同的机会被选中。这样一个密码的熵是 4569760000，这意味着大约 32.1 位。

于 2010-06-08T14:10:43.057 回答
27

香农熵方程是标准的计算方法。这是一个简单的 Python 实现，无耻地从Revelation代码库复制而来，因此获得了 GPL 许可：

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)

请注意，此实现假定您的输入比特流最好以字节表示。您的问题域可能会或可能不会出现这种情况。你真正想要的是你的比特流转换成一串数字。您如何决定这些数字是特定领域的。如果您的数字真的只是一和零，那么将您的比特流转换为一和零的数组。但是，您选择的转换方法会影响您获得的结果。

于 2010-06-05T04:50:17.547 回答
17

我相信答案是字符串的Kolmogorov 复杂性。这不仅不能用一大块伪代码来回答，Kolmogorov 复杂性也不是一个可计算的函数！

您在实践中可以做的一件事是使用可用的最佳数据压缩算法压缩位串。它压缩得越多，熵就越低。

于 2010-06-05T04:48:17.737 回答
8

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

您的问题是，您正在尝试测量熵以帮助您找到模型，这是不可能的；熵测量可以告诉您模型有多好。

话虽如此，您可以尝试一些相当通用的模型；它们被称为压缩算法。如果 gzip 可以很好地压缩您的数据，那么您至少已经找到了一种可以很好地预测它的模型。例如，gzip 对简单替换大多不敏感。它可以像处理“the”一样容易地处理文本中的“wkh”。

于 2010-06-05T06:49:32.957 回答
7

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

近似熵测试说明：该测试的重点是每个重叠 m 位模式的频率。测试的目的是将两个连续/相邻长度（m 和 m+1）的重叠块的频率与随机序列的预期结果进行比较。

此页面上的PDF提供了更详尽的解释：

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

于 2013-11-04T19:16:22.013 回答
1

这是 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

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

于 2016-10-07T08:57:43.357 回答
1

用这个公式使用一个词的香农熵：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()))
于 2017-05-30T13:13:37.377 回答