Как вычислить приблизительную энтропию битовой строки?

Ответ 1

Я считаю, что ответ - это Kolmogorov Complexity. Мало того, что это не отвечает за кусок псевдокода, сложность Колмогорова не является вычислимой функцией!

Одна вещь, которую вы можете сделать на практике, - это сжатие битовой строки с помощью лучшего алгоритма сжатия данных. Чем больше он сжимает нижнюю энтропию.

Ответ 2

Entropy не является свойством строки, которую вы получили, но из строк, которые вы могли бы получить вместо этого. Другими словами, он квалифицирует процесс, с помощью которого была сгенерирована строка.

В простом случае вы получаете одну строку из множества N возможных строк, где каждая строка имеет такую ​​же вероятность выбора, как и все остальные, т.е. 1/N. В этой ситуации говорят, что строка имеет энтропию N. Энтропия часто выражается в битах, которая является логарифмической шкалой: энтропия "n бит" представляет собой энтропию, равную 2 ⁿ.

Например: мне нравится генерировать мои пароли как две строчные буквы, затем две цифры, затем две строчные буквы и, наконец, две цифры (например, va85mw24). Буквы и цифры выбираются случайным образом, равномерно и независимо друг от друга. Этот процесс может генерировать 26 * 26 * 10 * 10 * 26 * 26 * 10 * 10 = 4569760000 различных паролей, и все эти пароли имеют равные шансы на выбор. Энтропия такого пароля составляет 4569760000, что означает около 32.1 бит.

Ответ 3

Уравнение энтропии Шеннона является стандартным методом расчета. Вот простая реализация в Python, бесстыдно скопированная с Revelation, и, таким образом, лицензия 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)

Обратите внимание, что эта реализация предполагает, что ваш входной бит-поток лучше всего представлен в виде байтов. Это может быть или не быть в случае вашей проблемной области. То, что вы действительно хотите, это ваш бит-поток, преобразованный в строку чисел. Просто, как вы решаете, какие именно эти номера являются специфичными для домена. Если ваши номера действительно являются только одним и нулями, то преобразуйте ваш бит-поток в массив единиц и нулей. Однако выбранный вами метод преобразования влияет на результаты, которые вы получаете.

Ответ 4

Нет единого ответа. Энтропия всегда относительна к некоторой модели. Когда кто-то говорит о пароле с ограниченной энтропией, они подразумевают "относительно способности интеллектуального злоумышленника предсказать", и это всегда верхняя граница.

Ваша проблема в том, что вы пытаетесь измерить энтропию, чтобы помочь вам найти модель, и это невозможно; что может подсказать вам измерение энтропии, насколько хорошая модель.

Сказав это, есть некоторые довольно общие модели, которые вы можете попробовать; они называются алгоритмами сжатия. Если gzip может хорошо сжать ваши данные, вы нашли хотя бы одну модель, которая может хорошо ее предсказать. И gzip, например, в основном нечувствителен к простой подстановке. Он может обрабатывать "wkh" часто в тексте так же легко, как он может обрабатывать "the".

Ответ 5

Извините, что так долго отвечал на этот вопрос.

Взгляните на мою недавнюю статью:

"BiEntropy - приблизительная энтропия конечной двоичной строки"

http://arxiv.org/abs/1305.0954

"Мы разрабатываем, реализуем и тестируем простой алгоритм, который вычисляет приблизительную энтропию конечной двоичной строки произвольной длины. Алгоритм использует средневзвешенное значение энтропий Шеннона строки и все, кроме последней двоичной производной строки Мы успешно проверяем алгоритм в полях теории первичных чисел (где мы явно доказываем, что последовательность простых чисел не является периодической), Human Vision, криптография, генерация случайных чисел и количественное финансирование"

Ответ 6

У инструментария оценки генератора случайных чисел NIST есть способ вычисления "Приближенная энтропия". Вот краткое описание:

Приблизительный энтропийный тест Описание: Основное внимание в этом тесте частота каждого перекрывающегося m-битового шаблона. Цель тест состоит в том, чтобы сравнить частоту перекрывающихся блоков двух последовательные/смежные длины (m и m + 1) против ожидаемого результата для случайной последовательности.

И более подробное объяснение доступно из PDF на этой странице:

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

Ответ 7

Здесь реализована реализация в 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

Приведенный выше пример согласуется с примером, приведенным в Википедии.

Ответ 8

Использование энтропии Больцмана слова с этой формулой: 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()))