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

Question

Есть ли стандартный способ сделать это?

Поиск в Google - "примерные биты энтропии" - раскрывает несколько научных статей, но я хотел бы просто найти кусок псевдокода, определяющего приблизительную энтропию для данной строки битов произвольной длины.

(Если это легче сказать, чем сделать, и это зависит от приложения, мое приложение содержит 16 320 бит зашифрованных данных (зашифрованный текст). Но зашифровано как головоломка и не должно быть невозможно взломать. Я подумал, что сначала проверим энтропия, но не может легко найти хорошее определение такого. Так что это похоже на вопрос, который должен быть на Stackru! Идеи для того, с чего начать с дешифрования 16K случайных битов, также приветствуются...)

Смотрите также этот связанный вопрос:
Какое компьютерное определение энтропии?

Answer 1

Я считаю, что ответ Колмогорова Сложность строки. Мало того, что это не отвечает с порцией псевдокода, сложность Колмогорова не вычислима!

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

http://arxiv.org/abs/1305.0954

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

Answer 7

Используя больцмановскую энтропию слова с этой формулой: https://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()))

Answer 8

Вот реализация в Python (я также добавил ее на вики-страницу):

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

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