Случайное обнаружение строк

Question

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

Разъяснение: Для человеческого глаза следующий текст как-то случайно ... dsfsddsfdsfsddsfs .... или даже po340-3gk30g3gkf; glkp.

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

Answer 1

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

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

Я не могу представить, что вы можете найти какой-либо "тест случайности", который будет быстрее этого.

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

Является ли это случайным, по вашему мнению:

String str = "                      o         _        _            _        "
           + "           _o        /\_      _ \\o     (_)\__/o     (_)       "
           + "         _< \_      _>(_)    (_)/<_       \_| \      _|/' \/   "
           + "        (_)>(_)    (_)           (_)      (_)       (_)'  _\o_ ";

Это не выглядит очень случайным для меня, но мне будет трудно определить, что выглядит случайным.

Answer 2

Измерьте длину строки после ее сжатия. gzip сделает.

Все компрессоры работают, ища избыточность на входе. Повторение подстрок является формой избыточности, которая соответствует общему интуитивному и математическому пониманию неслучайности. gzip и ему подобные специально ищут повторяющиеся подстроки и заменяют 2-е и последующие вхождения более короткими «указателями» обратно на оригинал.

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

Хотя gzip и другие компрессоры общего назначения, как правило, создают заголовок, так что короткие строки могут на самом деле увеличиваться в длине (т. Е. Обычно это не тот случай, когда length(a short string) < length(compress(a short string))), в общем случае все равно верно, что length(compress(a short repetitive string)) < length(compress(a short non-repetitive string)), что, надеюсь, все, что вам нужно.

Answer 3

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

Является ли '13530168 = dwninwebvp' довольно случайным?