50

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

グーグル（「近似エントロピー」ビット）は複数の学術論文を明らかにしますが、任意の長さの特定のビット文字列の近似エントロピーを定義する擬似コードのチャンクを見つけたいと思います。

（これは言うのが簡単で、アプリケーションによって異なる場合、私のアプリケーションには16,320ビットの暗号化データ（暗号文）が含まれます。しかし、パズルとして暗号化されており、解読することは不可能ではありません。最初に確認したいと思います。エントロピーですが、そのような適切な定義を簡単に見つけることができませんでした。したがって、StackOverflowにあるべき質問のようでした！16kのランダムに見えるビットの暗号化を解除することから始めるアイデアも歓迎します...）

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

4

7 に答える 7

37

エントロピーは、取得した文字列のプロパティではなく、代わりに取得できた文字列のプロパティです。つまり、文字列が生成されたプロセスを修飾します。

単純なケースでは、 N個の可能な文字列のセットから1つの文字列を取得します。各文字列は、他の文字列よりも選択される確率が同じです。つまり、1/Nです。この状況では、文字列はNのエントロピーを持っていると言われます。エントロピーは、対数目盛であるビットで表されることがよくあります。「nビット」のエントロピーは、 2nに等しいエントロピーです。

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

于 2010-06-08T14:10:43.057 に答える
27

シャノンのエントロピー方程式は、標準的な計算方法です。これは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)

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

于 2010-06-05T04:50:17.547 に答える
17

答えは弦のコルモゴロフ複雑さだと思います。これは擬似コードのチャンクでは答えられないだけでなく、コルモゴロフの複雑さは計算可能な関数ではありません！

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

于 2010-06-05T04:48:17.737 に答える
8

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

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

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

于 2010-06-05T06:49:32.957 に答える
7

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

近似エントロピーテストの説明：このテストの焦点は、重なり合うすべてのmビットパターンの頻度です。テストの目的は、2つの連続する/隣接する長さ（mおよびm + 1）の重複するブロックの頻度を、ランダムシーケンスの期待される結果と比較することです。

そして、より詳細な説明は、このページのPDFから入手できます。

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

于 2013-11-04T19:16:22.013 に答える
1

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

上記の例は、ウィキペディアに記載されている例と一致しています。

于 2016-10-07T08:57:43.357 に答える
1

この式で単語のシャノンエントロピーを使用する：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()))
于 2017-05-30T13:13:37.377 に答える