Теория о бесконечных обезьянах

07.03.2019devellloper

Страшно люблю разного рода абстрактные теории и мысленные эксперименты, существующие исключительно в гипотетическом поле и слабопроверяемые в реальной жизни. Одной из таких теорий является теория о бесконечных обезьянах, предполагающая ситуацию, в которой бесконечное количество обезьян с печатными машинками за бесконечное количество времени — рано или поздно могут напечатать любой заданный наперёд текст. К примеру, «Войну и Мир» Толстого или какую-либо из пьес Шекспира.

I-40-TELEGR-news-f73_640

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

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

Словарь.

Очень важен выбор «заданного наперёд» произведения. Важен и язык этого текста. Я решил взять первый абзац произведения Льва Толстого «Анна Каренина«. Без какой-либо конкретной причины, просто захотелось 🙂

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

Вероятность подобрать слово из 5 букв на русском языке 1 к 33 554 432.

Фактически при изменении базы словаря символов до 26 с 32 (на 6 меньше букв) мы получаем выгоду в 3 раза, соответственно, время затраченное на порядок меньшее. Английский алфавит:

Вероятность подобрать слово из 5 букв на английском языке 1 к 11 881 376.

Можно было бы, конечно, воспользоваться ещё более скромным языком — Ротокас (группа т.н. папуасских языков) в алфавите которого есть только 12 букв. И вероятность подобрать пятибуквенное слово составила бы 1 к 248 832, что более чем приемлемо и терпимо. Проблема заключается в том, что средняя длина слов в этом языке просто неприлично огромная и мы аннигилируем всю выгоду банально потому, что наш текст безмерно увеличится в объёме символов.

Важно: 1/26 и 1/32 это вероятность найти букву. В случае, когда в нашем тексте используется разный регистр букв (заглавная и строчная) — наш делитель-знаменатель увеличивается вдвое. В случае, когда в базу словаря добавляются знаки препинания и пунктуации, а также цифры — сильно усложняет наш эксперимент во временной шкале. Здесь мы также пойдём на упрощение — откажемся от любых символов, кроме строчных букв и, соответственно, приведём весь текст в lowercase.

Алгоритм.

Итак, английский. Теперь необходимо подумать о самом алгоритме. Теория умалчивает о подходах и реализациях, оставляя решение данных требований на участь экспериментатора. Чем я с удовольствием и воспользуюсь (самым наглым образом).

Первым наперво стоит указать, что генератор случайных цифр символов из обезьяны (ровным счётом, как и из человека) никакой. Очень плохой ГСЧ. Очень сложно получить равномерное статистическое распределение между нажимаемыми клавишами. Это означает, что вероятность 1/26 является вероятностью в «идеальном мире«, который, как известно, бывает только на бумажке. Также очень сильно хромает скорость такого набора. Поэтому здесь мы также идём на осознанное упрощение — мы воспользуемся ГСЧ, который нам предоставляет наши современные реалии.

Существует несколько способов генерировать текст случайным образом:

  • по-символьно, когда мы ожидаем, что обезьяна случайно брякнет конкретную необходимую нам букву и игнорируем все остальные «неудачные» нажатия. Вероятность набить весь текст при таком подходе реален даже в эксперименте с живыми обезьянами (при небольшом заданном тексте);
  • слово целиком — считаем успешным лишь тот случай, когда обезьяна чередой случайных нажатий вбила слово. Становится сложнее экспоненциально;
  • весь текст целиком — когда весь текст обезьяной вбивается от начала и до конца без ошибок. Сложность также растёт по экспоненте.

Первый пункт мы не рассматриваем за его неинтересность. Последний тоже, т.к. скорее всего времени, отведённого на нашу вселенную — не хватит на такой эксперимент. Центральный вариант кажется рабочим. Но и он требует уточнения. Многие слова в книге повторяются. И тут мы также пойдём на упрощение (на этот раз финальное) — мы будем подбирать только уникальные слова, чтобы тысячи раз не тратить время на союзы, предлоги и другие служебные части речи; туда же попадают имена нарицательные и все слова, повторяемые не единожды.

Пишем код.

Как всегда, это будет консольное приложение. Маленькое. Мы не будем писать мультипоточное приложение, расплодив обезьян с их машинками. Для нашей задачи вполне хватит основного потока. Итак, создадим проект MonkeyInfinity и добавим следующие константы и переменные в Program.cs:

Здесь всё просто — мы инициализируем текстовую константу с указанием файла нашего текста, массив символов для обрезания строк и экземпляр класса нашего ГСЧ. Теперь, давайте, получим сам текст и приведём его к lowercase виду:

Следующий шаг — получить словарь букв для подбора. Мы должны использовать в нашем генераторе только уникальные символы; также игнорировать любые не буквенные символы. Можно было бы, конечно, реализовать при помощи char.IsLetter(), но я осознанно оставил возможность регулировать нужные нам символы.

Теперь, логично, получить словарь уникальных слов:

Итого, у нас есть все символы, необходимый набор клавиш нашей виртуальной печатной машинки и есть слова, которые мы ожидаем от обезьяны программы. Давайте попробуем что-то сгенерировать:

Постепенно переходим к самому интересному — реализация механизма подбора слов. Данный метод я назвал Run, как основную задачу нашей маленькой программки. Здесь же я засекаю время старта подбора и время завершения. Внутри тела метода есть цикл, работающий до тех пор, пока мы не подберём все слова. В случае подбора слова — сбрасываем в консоль соответственные данные. Итак, Run:

Когда готовы все кубики — осталось последнее. Метод Main(), наша точка входа и выхода. Нам нужно связать кубики в бизнес-логику и заставить программу работать — для этого реализуем наш метод, добавив в него небольшую статистику по самому большому и маленькому слову:

Всё готово для проверки. Осталось подобрать текст. Для того, чтобы всё тщательно продебажить (вас то я уже лишил этой радости 🙂 ), я взял коротенькие английские пословицы. Сохранив в файле text.txt следующий текст: Every man has his price я впервые запустил программу. Мне кажется, что это хороший пример для старта — предложение с тремя трёхбуквенными и двумя пятибуквенными словами. Итак, барабанная дробь, запуск:

Как видно из лога, программе понадобилось 472000 итераций и около ~0.115 секунды для того, чтобы решить данную задачу. Ожидаемо, что трёхбуквенные слова были подобраны быстрее, чем слова из пяти букв. Хоть и на это понадобилось 18к итераций!

5-6 буквенные слова подбираются сравнительно быстро. Если практически на все слова из 5 букв уходит менее секунды, то на слова от 6 символов — рост времени наблюдается экспоненциальный. Число итераций зашкаливает — не думаю, что какая-либо уважающая себя обезьяна на такое пойдёт добровольно 🙂 На моём i7 процессоре с 24гб ОЗУ первый абзац Анны Каренины, состоящий из 117 уникальных английских слов (где самое длинное слово housekeeper 11 букв) подбирается уже неделю и были найдены только все 7-ми буквенные слова, несколько слов из 8 букв и одно из 9-ти. Не быстро, мягко говоря, но и не невозможно.

P.S. Код писался быстро и исключительно для локального использования. Там нет никаких SOLID принципов, потому что их там особо некуда притулить. Этот код не нужно воспринимать серьёзно. Да и оверхед там, где он не нужен — это тоже антипаттерн.

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

Выводы.

Выводы, конечно, банальные, предсказуемые и ожидаемые. Теория имеет место быть, она валидна и проверяема в масштабе. Если теория подтверждается в идеальных искусственных условиях за очень короткое конечное время — нет оснований полагать, что в реальном мире мы также не придём к нужному результату. Спасибо индукции.

Да, бесконечное время. Да, скорее всего, мы не сможем самостоятельно дождаться конца этого эксперимента. Возможно, что и вселенная к этому моменту перестанет существовать. Но вероятность всё равно будет стремиться к единице, а это значит, что нам остаётся только лишь набраться терпения и просто немного подождать 🙂

Leave a comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Предыдущая запись