如何计算位串的近似熵？

8 回答

• 10

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

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

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

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

  回复于 2024-05-15T02:01:55+08:00
• 6

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

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

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

  回复于 2024-05-15T02:01:55+08:00
• 28

  Shannon's entropy equation是标准的计算方法 . 这是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)
  

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

  回复于 2024-05-15T02:01:55+08:00
• 4

  我相信答案是字符串的Kolmogorov Complexity . 这不仅对一大块伪代码负责，Kolmogorov复杂性不是computable function！

  在实践中你可以做的一件事是用最好的data compression算法压缩位串 . 压缩越多，熵越低 .

  回复于 2024-05-15T02:01:55+08:00
• 9

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

  你的问题是，你正试图测量熵以帮助你找到一个模型，这是不可能的;熵测量可以告诉你的是模型有多好 .

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

  回复于 2024-05-15T02:01:55+08:00
• 1

  很抱歉这么久回答这个问题 .

  看看我最近的论文：

  “BiEntropy - 有限二进制串的近似熵”

  http://arxiv.org/abs/1305.0954

  “我们设计，实现并测试一个简单的算法，该算法计算任意长度的有限二进制串的近似熵 . 该算法使用字符串的Shannon Entropies的加权平均值和除字符串的最后二进制导数之外的所有 . 我们成功在素数理论（我们明确证明素数序列不是周期性的），人类视觉，密码学，随机数生成和定量金融领域中测试算法“

  回复于 2024-05-15T02:01:55+08:00
• 0

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

  Example:

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

  以上示例与the example given on Wikipedia一致 .

  回复于 2024-05-15T02:01:55+08:00
• 19

  使用这个公式的单词的Boltzmann熵：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()))
  

  回复于 2024-05-15T02:01:55+08:00