🐍⛓️ Цепи Маркова: генерирование читабельной бессмыслицы за 20 строк на Python

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

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

Алгоритм

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

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

И это все!

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

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

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

Не убий.

Не прелюбодействуй.

Не укради.

Не произноси ложного свидетельства на ближнего твоего.

Не желай дома ближнего твоего, не желай жены ближнего твоего, ни раба его, ни рабыни его, ни вола его, ни осла его, ни всего, что у ближнего твоего.

Ниже представлена структура данных «Возможные третьи слова», показывающая первые несколько записей с парой слов слева и возможностями, разделенными «|», справа:

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

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

Как выглядит сгенерированный текст? Давайте попробуем проверить это на примере десяти заповедей, приведенных выше:

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

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

Если вы используете объемный исходный текст, то получите гораздо более интересный результат.

Несколько интересных примеров

Ниже приведены самые интересные результаты с использованием большого количества исходных текстов. Мы генерируем по сотне слов из каждого источника. Книги были взяты из Project Gutenberg.

Использование собственных статей

Используем статьи, которые были написаны, в качестве исходного текста:

В особенности если вам необходимо вернуть значение, то теперь оно очень плавное – почти в 5 раз быстрее. Тем не менее, если вам требуется пользовательское исключение, используйте встроенные исключения, если это необходимо. Обратная совместимость нарушается только если вы используете Linux, здесь применяются SSE/SIMD инструкции x86 для обработки CSV с помощью AWK, как например NF предназначены только для чтения в AWKGo. Что означает термин «питонический»? Это очень забавно. Мой совет: создайте свою собственную типобезопасность OrderedMap<int>. Но поскольку строки Lox не поддерживают escape-последовательностей, здесь нет ни null, ни undefined, то вы получаете все что нужно! Минималистичный Make в одном из своих источников получает...

Мне нравится, что здесь отражено большинство технических аспектов: производительность, идиоматический код, обратная совместимость, AWK, CSV, небольшие языки и так далее. Это не ChatGPT, но если присмотреться, текст выглядит вполне правдоподобно!

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

Использование «Алисы в Стране чудес»

Вот один из вариантов, использующий в качестве исходных данных «Алису в стране чудес» Льюиса Кэрролла. Книга более или менее бессмысленна, так что это практически сработало:

У входа в пирожные стояла большая роза, и она с радостью обнаружила, что ее фламинго в большой спешке исчезли: «И их звали Элси, Лейси и Тилли, и они не смогут доказать, что это сделала я: это бесполезно отрицать. Полагаю, что Дайна будет посылать мне сообщения и дальше!» И, открыв дверь, она сразу же начала чихать. Сонная мышь снова прикрыла глаза, чтобы понаблюдать за тем, что происходит с большим веером в бассейне, «а она так мило сидит и мурлычет, взяв ее за руку, что та поспешила прочь, не дожидаясь разрешения сменить…»

Использование Ветхого Завета (из Библии короля Якова)

Обратите внимание на то, что в результате выводятся (бессмысленные) номера стихов, которые были частью исходного текста.

Взгляните на жаркое, которое получает вавилонский царь!

Вениамин, Иасиил, сын Берахии, сын Иехонии, царя Гоморрского, и к святым богам – в своей воле. 22:30 На юге, у берега моря, напротив горы, с которой Господь поражает волны ее. 107:26 И поднялись они на гору, чтобы похоронить их, их, детей их, показывая священослужителю; 13:17 и царь Вавилонский испепелил их во имя праха. 18:1 И отвечал один из них: взял ли Иисус Навин и положил руку свою на рабов Саула, отца моего, и не спас ли он меня от гибели...

Использование Нового Завета (из Библии короля Якова)

Забавно, что выводимые строки Нового Завета начинаются с «Моисея», ключевой фигуры Ветхого Завета (но чье имя 80 раз встречается и в Новом Завете).

Выглядит довольно еретично: «мы проповедовали слово тела – волю человека».

Моисей, ты хотел бы, чтобы мы жили в них. 2:11 Итак, помните, что голос мой против них. 20:20 И сказали: не смирившемуся ли дано будет, и он очистит пол свой, и соберет пшеницу в море, и получит пропитание; ибо мы проповедовали слово о том, что тело – воля человека, оно будет; но пошли за Мною? 10:30 И вошел Иисус в Царствие Божие. 5:6 И пусть никто не говорит: ты глупец, что Он был близок к Иоппии и к другой стороне. 10:33 Но всякий, кто...

Использование «Войны миров»

И еще одно, на заметку. Здесь используется «Война миров» Уэллса.

В Халлифорде мне явилась та чернота, которая бывает в день дерби. Мой брат свернул к железным воротам Гайд-парка. Я увидел два человеческих скелета – не тела, а именно скелеты, вычищенные до блеска, – в яме, мимо которой проехал человек и остановился возле беглецов, не предложив помощи. Трактир был закрыт, как будто человек на велосипеде, дети, отправившиеся на поиски пищи, сказали ему, что это станет для него свинцом, таким образом. Это, действительно, был рассвет над домами, выходящими к реке, к Шеппертону и прочим. Безумная решимость овладела...

Давайте теперь посмотрим на код Python, который я использовал для реализации этой идеи.

Реализация на Python

Для начала посмотрите на программу целиком – 24 строки с пробелами и комментариями, 16 – без них:

        import collections, random, sys, textwrap

# Build possibles table indexed by pair of prefix words (w1, w2)
w1 = w2 = ''
possibles = collections.defaultdict(list)
for line in sys.stdin:
    for word in line.split():
        possibles[w1, w2].append(word)
        w1, w2 = w2, word

# Avoid empty possibles lists at end of input
possibles[w1, w2].append('')
possibles[w2, ''].append('')

# Generate randomized output (start with a random capitalized prefix)
w1, w2 = random.choice([k for k in possibles if k[0][:1].isupper()])
output = [w1, w2]
for _ in range(int(sys.argv[1])):
    word = random.choice(possibles[w1, w2])
    output.append(word)
    w1, w2 = w2, word

# Print output wrapped to 70 columns
print(textwrap.fill(' '.join(output)))


    

Можете оценить сами, но я думаю, что это вполне читабельно.

Программа получает количество слов в качестве аргумента командной строки (sys.argv[1]) и текст на стандартном вводе. Чтобы запустить ее, выполните следующую команду:

        $ python3 markov.py 100 <AliceInWonderland.txt 
A large rose-tree stood near the entrance of the cakes, and was
…

    

Код также доступен в формате Gist на GitHub: markov.py. Эту программу вряд ли можно назвать оригинальной – я предоставляю вам разрешение делать с ней все, что захотите.

Заключение

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

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