6

バイナリ文字列の統計的ランダム性を判断するにはどうすればよいですか?

エルゴ、自分のテストをコーディングして、統計的ランダム性に対応する単一の値、0 から 1.0 までの値 (0 はランダムではなく、1.0 はランダム) を返すにはどうすればよいでしょうか?

テストは、任意のサイズのバイナリ文字列で機能する必要があります。

ペンと紙でそれを行う場合、次のような文字列を調べることができます:
  0 (任意のランダム性、他の選択肢は 1 のみ)
  00 (ランダムではなく、繰り返しであり、サイズに一致します)
  01 (より良い、2 つの異なる値)
  010 (ランダム性が低く、パリンドローム)   011
  (ランダム性が低く、1 が多い、それでも許容範囲   )


ケース例:

サイズ: 1、可能性: 2
  0: 1.0 (ランダム)
  1: 1.0 (ランダム)

サイズ: 2、P:4
  00: ?
  01: 1.0 (ランダム)
  10: 1.0 (ランダム)
  11: ?

S:3, P:8
  000: ? non-random
  001: 1.0 (random)
  010: ? less random
  011: 1.0 (random)
  100: 1.0 (random)
  101: ? less random
  110 1.0 (random)
  111: ? non-random

And so on.

I feel that this may play a lot into breaking the string into all possible substrings and comparing frequencies, but it seems like this sort of groundwork should already have been done in the early days of computer science.

4

4 に答える 4

12

バイナリ文字列のコルモゴロフ複雑さを見つける方法を求めているようです。残念ながら、これは計算不能です。圧縮アルゴリズムを実行した後の文字列のサイズは、ランダムな文字列が多いほど圧縮性が低くなるという点で、それがどの程度ランダムであるかを示します。

于 2010-06-22T23:55:41.030 に答える
11

これにより、0 から 1.0 までのエントロピー カウントが得られます。

データと情報に適用されるエントロピーの尺度であるシャノン エントロピーを調べてみることをお勧めします。実際、これは実際には、熱力学の最も受け入れられている解釈によって定義されたエントロピーの物理式のほぼ直接的な類似物です。

より具体的には、あなたの場合、バイナリ文字列を使用すると、 Binary Entropy Functionを見ることができます。これは、データのバイナリビットのランダム性を含む特別なケースです。

これは次のように計算されます。

H(p) = -p*log(p) - (1-p)*log(1-p)

(2 を底とする対数0*log(0)。0 と仮定)

1 (または 0) の割合はどこですかp。グラフは左右対称なので、答えはどちらでも同じです。

関数が生成するものは次のとおりです。

バイナリ エントロピー関数

ご覧のとおり、pが 0.5 (0 と 1 の数が同じ) の場合、エントロピーは最大 (1.0) です。が 0 または 1.0 の場合p、エントロピーは 0 です。

これはまさにあなたが望むもののようですよね？

唯一の例外はサイズ 1のケースです。これは例外として設定できます。ただし、100% 0 と 100% 1 はエントロピーではないように思えます。ただし、必要に応じて実装してください。

また、これはビットの「順序付け」を考慮していません。それらの合計のみ。したがって、繰り返し/回文はブーストされません。これには、ヒューリスティックを追加することをお勧めします。

他のケース例は次のとおりです。

00: -0*ログ(0) - (1-0)*ログ(1-0) = 0.0
01: -0.5*ログ(0.5) - (1-0.5)*ログ(1-0.5) = 1.0
010: -(1/3)*ログ(1/3) - (2/3)*ログ(2/3) = 0.92
0100: -0.25*ログ(0.25) - (1-0.25)*ログ(1-0.25) = 0.81
于 2010-06-23T01:31:44.633 に答える
5

少し前に、私は自分の目的に合った単純なヒューリスティックを開発しました。

文字列自体だけでなく、文字列の導関数についても、0 と 1 の「偶数」を計算するだけです。たとえば、01010101 の 1 次導関数は、すべてのビットが変化するため 11111111 であり、1 次導関数のビットが変化しないため、2 次導関数は 00000000 です。次に、好みに応じてこれらの「均一性」を比較検討するだけです。

次に例を示します。

#include <string>
#include <algorithm>

float variance(const std::string& x)
{
    int zeroes = std::count(x.begin(), x.end(), '0');
    float total = x.length();
    float deviation = zeroes / total - 0.5f;
    return deviation * deviation;
}

void derive(std::string& x)
{
    char last = *x.rbegin();
    for (std::string::iterator it = x.begin(); it != x.end(); ++it)
    {
        char current = *it;
        *it = '0' + (current != last);
        last = current;
    }
}

float randomness(std::string x)
{
    float sum = variance(x);
    float weight = 1.0f;
    for (int i = 1; i < 5; ++i)
    {
        derive(x);
        weight *= 2.0f;
        sum += variance(x) * weight;
    }
    return 1.0f / sum;
}

int main()
{
    std::cout << randomness("00000000") << std::endl;
    std::cout << randomness("01010101") << std::endl;
    std::cout << randomness("00000101") << std::endl;
}

入力例では、それぞれ 0.129032、0.133333、および 3.2 の「ランダム性」が得られます。

余談ですが、文字列を導出することでクールなフラクタル グラフィックスを取得できます ;)

int main()
{
    std::string x = "0000000000000001";
    for (int i = 0; i < 16; ++i)
    {
        std::cout << x << std::endl;
        derive(x);
    }
}

0000000000000001
1000000000000001
0100000000000001
1110000000000001
0001000000000001
1001100000000001
0101010000000001
1111111000000001
0000000100000001
1000000110000001
0100000101000001
1110000111100001
0001000100010001
1001100110011001
0101010101010101
1111111111111111
于 2010-06-23T00:21:22.160 に答える
1

文字列に対して圧縮アルゴリズムを試すことができます。繰り返しが多い (ランダム性が少ない) ほど、文字列を圧縮できます。

于 2010-06-22T23:55:15.687 に答える