Как я могу определить статистическую случайность двоичной строки?

Question

Как определить статистическую случайность двоичной строки?

Итак, как я могу написать свой собственный тест и вернуть одно значение, которое соответствует статистической случайности, значение от 0 до 1,0 (0 не случайно, 1,0 случайно)?

Тест должен работать с двоичными строками любого размера.

Когда вы делаете это с ручкой и бумагой, вы можете исследовать строки следующим образом:
0 (произвольная случайность, единственный другой выбор - 1)
00 (не случайно, повторяется и соответствует размеру)
01 (лучше, два разных значения)
010 (менее случайный, палиндром)
011 (меньше случайных, больше 1, все еще приемлемо)
0101 (менее случайный, шаблон)
0100 (лучше, меньше, но любое другое распределение вызывает шаблоны)

Примеры случаев:

Размер: 1, Возможности: 2
0: 1,0 (произвольно)
1: 1,0 (произвольно)

Размер: 2, P: 4
00:?
01: 1.0 (произвольно)
10: 1,0 (произвольно)
11:?

S: 3, P: 8
000:? неслучайный
001: 1,0 (произвольно)
010:? менее случайный
011: 1,0 (случайный)
100: 1,0 (произвольно)
? менее случайный
110 1,0 (случайный)
111:? неслучайный

и т. Д.

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

Answer 1

Вы, кажется, спрашиваете, как найти колмогоровскую сложность двоичной строки. К сожалению, это неопровержимо . Размер вашей строки после выполнения алгоритма сжатия даст вам представление о том, насколько она случайна, поскольку более случайные строки менее сжимаемы.

Answer 2

Это даст вам счет энтропии от 0 до 1,0:

Возможно, вы захотите попробовать Энтропию Шеннона , которая является мерой энтропии применительно к данным и информации. Фактически, это фактически почти прямой аналог физической формулы для энтропии, как это определено наиболее приемлемыми интерпретациями термодинамики.

Более конкретно, в вашем случае с двоичной строкой вы можете увидеть Двоичную функцию энтропии , которая является особым случаем, связанным со случайностью в двоичных битах данных.

Это рассчитывается по

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

(логарифмы в основании 2; предположим, 0*log(0) равно 0)

Где p - ваш процент от 1 (или от 0; график симметричен, поэтому ваш ответ в любом случае одинаков)

Вот что выдает функция:

Как видите, если p равно 0,5 (такое же количество единиц, как и 0), ваша энтропия максимальна (1,0). Если p равно 0 или 1,0, энтропия равна 0.

Кажется, это именно то, что вы хотите, верно?

Единственное исключение - это ваши Размеры 1 дел, которые могут быть просто исключены. Однако 100% 0 и 100% 1 не кажутся мне слишком энтропийными. Но реализуйте их как хотите.

Кроме того, это не учитывает "упорядочение" битов. Только общая сумма их. Таким образом, повторение / палиндромы не получат никакого ускорения. Возможно, вы захотите добавить дополнительную эвристику для этого.

Вот другие ваши примеры:

00:   -0*log(0) - (1-0)*log(1-0)               = 0.0
01:   -0.5*log(0.5) - (1-0.5)*log(1-0.5)       = 1.0
010:  -(1/3)*log(1/3) - (2/3)*log(2/3)         = 0.92
0100: -0.25*log(0.25) - (1-0.25)*log(1-0.25)   = 0.81

Answer 3

Некоторое время назад я разработал простую эвристику, которая работала для моих целей.

Вы просто вычисляете "четность" 0 и 1 не только в самой строке, но и для производных строки. Например, первая производная 01010101 - это 11111111, потому что каждый бит изменяется, а вторая производная - 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

Answer 4

Вы можете попробовать алгоритм сжатия для строки.Чем больше повторений (меньше случайности), тем больше можно сжать строку.