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

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

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

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

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

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

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

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

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