少し文字列のおおよそのエントロピーを計算するにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/2979174

質問

これを行う標準的な方法はありますか？

グーグル - 「おおよそのエントロピー」ビット - 複数のアカデミックペーパーを発見しましたが、任意の長さの一連のビット文字列の近似エントロピーを定義する擬似コードの塊を見つけたいと思います。

（これが言うよりも簡単で、アプリケーションに依存する場合、私のアプリケーションには16,320ビットの暗号化されたデータ（cyphertext）が含まれます。しかし、パズルとして暗号化され、クラックすることは不可能ではありません。エントロピーですが、そのような良い定義を簡単に見つけることができませんでした。そのため、16Kランダムを求めるビットを除去することから始めることから始める場所についてのアイデアも大歓迎です...）

この関連する質問も参照してください。
エントロピーのコンピューターサイエンスの定義は何ですか？

役に立ちましたか？

解決 3

答えはです コルモゴロフの複雑さ 文字列の。これは擬似コードの塊で答えられないだけでなく、コルモゴロフの複雑さはそうではありません 計算可能な関数!

実際にできることの1つは、利用可能な最高の文字列でビット文字列を圧縮することです データ圧縮 アルゴリズム。エントロピーが低くなるほど、圧縮します。

他のヒント

エントロピーは、手に入れた文字列のプロパティではなく、代わりに入手できた文字列のプロパティです。言い換えれば、それは資格があります 処理する 文字列が生成されました。

簡単な場合、あなたは一連の間に1つの文字列を取得します n 可能な文字列、各文字列には他のすべての文字列よりも選択される可能性があります。 1/n. 。状況では、文字列にはエントロピーがあると言われています n. 。エントロピーはしばしばビットで表されますが、これは対数スケールです。n ビットは等しいエントロピーです 2n.

たとえば、パスワードを2つの小文字、次に2桁、次に2桁、最後に2桁として生成するのが好きです（例： va85mw24）。文字と数字は、互いにランダムに、均一に、独立して選択されます。このプロセスでは、26*26*10*10*26*26*10*10 = 4569760000個の異なるパスワードが生成される場合があり、これらのパスワードはすべて選択される可能性があります。このようなパスワードのエントロピーは4569760000であり、これは約32.1ビットを意味します。

シャノンのエントロピー方程式 計算の標準的な方法です。これはPythonでの簡単な実装です。 啓示 コードベース、したがって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)

この実装は、入力ビットストリームがバイトとして最もよく表されることを前提としていることに注意してください。これは、問題のドメインに当てはまる場合とそうでない場合があります。あなたが本当に欲しいのは、あなたのビットストリームが一連の数字に変換されたことです。それらの数値が何であるかを決定する方法は、ドメイン固有です。あなたの数字が本当に1つだけでゼロである場合は、ビットストリームを一連のものとゼロに変換してください。ただし、選択した変換方法は、得られる結果に影響します。

単一の答えはありません。エントロピーは常にいくつかのモデルに関連しています。誰かがエントロピーが制限されているパスワードについて話すとき、それらは「インテリジェントな攻撃者が予測する能力と比較して」意味し、それは常に上限です。

あなたの問題は、モデルを見つけるのを助けるためにエントロピーを測定しようとしていることです。それは不可能です。エントロピー測定があなたに伝えることができるのは、モデルがどれほど優れているかです。

そうは言っても、試してみることができるかなり一般的なモデルがいくつかあります。それらは圧縮アルゴリズムと呼ばれます。 GZIPがデータを適切に圧縮できる場合、少なくとも1つのモデルを十分に予測できるモデルが見つかりました。たとえば、GZIPは、単純な置換にほとんど鈍感です。 「WKH」をテキストで頻繁に処理できます。

この質問に長い間答えてすみません。

私の最近の論文を見てください：

「ビエントロピー - 有限のバイナリ文字列のおおよそのエントロピー」

http://arxiv.org/abs/1305.0954

「任意の長さの有限バイナリストリングの近似エントロピーを計算する単純なアルゴリズムを設計、実装、テストします。アルゴリズムは、ストリングのシャノンエントロピーの加重平均と、ストリングの最後のバイナリ誘導体を除くすべてを使用します。素数理論のフィールドでアルゴリズムをテストします（一連の一連の一連が周期的ではないことを明示的に証明します）、人間の視覚、暗号化、乱数生成、定量的財政」

NIST乱数ジェネレーター評価ツールキットには、「おおよそのエントロピー」を計算する方法があります。これが簡単な説明です：

近似エントロピーテストの説明：このテストの焦点は、すべてのオーバーラップMビットパターンの頻度です。テストの目的は、ランダムシーケンスの予想結果と2つの連続/隣接する長さ（MおよびM+1）のオーバーラップブロックの頻度を比較することです。

そして、より徹底的な説明があります PDF このページで：

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

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

上記の例は一致しています ウィキペディアで与えられた例.

この式で単語のシャノンエントロピーを使用してください。 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()))
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top