Простейший генератор текста на цепях Маркова

В про­шлый раз мы раз­би­ра­лись с тео­ри­ей про цепи Мар­ко­ва. Вот основ­ные тезисы:

  • Цепь Мар­ко­ва — это после­до­ва­тель­ность собы­тий, где каж­дое новое собы­тие зави­сит толь­ко от преды­ду­ще­го. Напри­мер, после одно­го сло­ва может сто­ять дру­гое слово. 
  • Суще­ству­ют алго­рит­мы, кото­рые спо­соб­ны гене­ри­ро­вать текст на осно­ва­нии цепей Мар­ко­ва. Они изу­ча­ют, какие свя­зи могут быть меж­ду сло­ва­ми, и потом про­хо­дят по этим свя­зям и состав­ля­ют новый текст. 
  • Для нашей рабо­ты алго­рит­му все­гда нужен исход­ный текст (он же кор­пус) — гля­дя на этот текст, алго­ритм пой­мёт, какие сло­ва обыч­но идут друг за другом.
  • Чем боль­ше раз­мер исход­но­го тек­ста, тем боль­ше свя­зей меж­ду цепя­ми и тем раз­но­об­раз­нее полу­ча­ет­ся текст на выходе.

Сего­дня попро­бу­ем это в деле и напи­шем самый про­стой гене­ра­тор тек­ста на цепях Мар­ко­ва. Это будет похо­же на рабо­ту ней­ро­се­ти, но на самом деле ника­ких «ней­ро» там нет — про­сто сети, кото­рые сде­ла­ны на алго­рит­ме цепей Мар­ко­ва. А сеть — это про­сто таб­ли­ца со свя­зя­ми меж­ду элементами. 

Коро­че: ника­ко­го искус­ствен­но­го интел­лек­та, про­сто озве­рев­шие алго­рит­мы всле­пую дёр­га­ют слова. 

Логика проекта

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

Логи­ка будет такой:

  1. Берём файл с исход­ным тек­стом и раз­би­ва­ем его на слова.
  2. Все сло­ва, кото­рые сто­ят рядом, соеди­ня­ем в пары.
  3. Исполь­зуя эти пары, состав­ля­ем сло­варь цепо­чек, где ука­за­но пер­вое сло­во и все, кото­рые могут идти после него.
  4. Выби­ра­ем слу­чай­ное сло­во для старта.
  5. Зада­ём дли­ну тек­ста на выхо­де и полу­ча­ем результат.

Сде­ла­ем всё по шагам, как обычно.

Проверяем, что у нас есть Python

Python не так-то про­сто запу­стить, поэто­му, если вы ещё ниче­го не дела­ли на Python, про­чи­тай­те нашу ста­тью в тему. Там всё опи­са­но по шагам. 

Разбиваем исходный текст

Для тре­ни­ров­ки мы взя­ли вось­мой том пол­но­го собра­ния сочи­не­ний Чехо­ва — пове­сти и рас­ска­зы. В нём при­мер­но 150 тысяч слов, поэто­му долж­но полу­чить­ся раз­но­об­раз­но. Этот файл нуж­но сохра­нить как che.txt и поло­жить в ту же пап­ку, что и код программы.

👉 Что­бы быст­ро рабо­тать с боль­ши­ми мас­си­ва­ми дан­ных, будем исполь­зо­вать биб­лио­те­ку numpy — она напи­са­на спе­ци­аль­но для биг-даты, рабо­ты с ней­ро­се­тя­ми и обра­бот­ки боль­ших мат­риц. Для уста­нов­ки мож­но исполь­зо­вать коман­ду pip3 install numpy:

Простейший генератор текста на цепях Маркова
# подключаем библиотеку numpy
import numpy as np

# отправляем в переменную всё содержимое текстового файла
text = open('che.txt', encoding='utf8').read()

# разбиваем текст на отдельные слова (знаки препинания останутся рядом со своими словами)
corpus = text.split()

Генерируем пары

Для это­го исполь­зу­ем спе­ци­аль­ную команду-генератор: yield. В функ­ци­ях она рабо­та­ет как return — воз­вра­ща­ет какое-то зна­че­ние, а нам она нуж­на из-за осо­бен­но­стей сво­ей рабо­ты. Дело в том, что yield не хра­нит и не запо­ми­на­ет ника­кие зна­че­ния — она про­сто гене­ри­ру­ет что-то, тут же про это забы­ва­ет и пере­хо­дит к сле­ду­ю­ще­му. Имен­но так и рабо­та­ют цепи Мар­ко­ва — они не запо­ми­на­ют все преды­ду­щие состо­я­ния, а рабо­та­ют толь­ко с кон­крет­ны­ми пара­ми в дан­ный момент.

👉 Мы раз­бе­рём гене­ра­то­ры более подроб­но в отдель­ной ста­тье, а пока про­сто исполь­зу­ем их в нашем коде.

# делаем новую функцию-генератор, которая определит пары слов
def make_pairs(corpus):
    # перебираем все слова в корпусе, кроме последнего
    for i in range(len(corpus)-1):
        # генерируем новую пару и возвращаем её как результат работы функции
        yield (corpus[i], corpus[i+1])
        
# вызываем генератор и получаем все пары слов
pairs = make_pairs(corpus)

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

Составляем словарь

Пой­дём по само­му про­сто­му пути: не будем высчи­ты­вать веро­ят­но­сти про­дол­же­ния для каж­до­го сло­ва, а про­сто ука­жем вто­рым эле­мен­том в паре все сло­ва, кото­рые могут быть про­дол­же­ни­ем. Напри­мер, у нас в пере­мен­ной pairs есть такие пары:

при­вет → это

при­вет → друг

при­вет → как

при­вет → друг

при­вет → друг

Вид­но, что «друг» встре­ча­ет­ся в 3 раза чаще осталь­ных слов, поэто­му веро­ят­ность его появ­ле­ния — ⅗. Но что­бы не счи­тать веро­ят­но­сти, мы сде­ла­ем так:

  1. Соста­вим пару при­вет → (это, друг, как, друг, друг).
  2. При выбо­ре мы про­сто слу­чай­ным обра­зом выбе­рем одно из зна­че­ний для продолжения.

👉 Это, конеч­но, не так изящ­но, как в серьёз­ных алго­рит­мах с мат­ри­ца­ми и веро­ят­но­стя­ми, зато рабо­та­ет точ­но так же и более про­сто в реализации.

Вот блок с этим кодом на Python:

# словарь, на старте пока пустой
word_dict = {}

# перебираем все слова попарно из нашего списка пар
for word_1, word_2 in pairs:
    # если первое слово уже есть в словаре
    if word_1 in word_dict.keys():
        # то добавляем второе слово как возможное продолжение первого
        word_dict[word_1].append(word_2)
    # если же первого слова у нас в словаре не было
    else:
        # создаём новую запись в словаре и указываем второе слово как продолжение первого
        word_dict[word_1] = [word_2]

Выбираем слово для старта

Что­бы было совсем непред­ска­зу­е­мо, началь­ное сло­во тоже будем выби­рать слу­чай­ным обра­зом. Глав­ное тре­бо­ва­ние к началь­но­му сло­ву — пер­вая заглав­ная бук­ва. Выпол­ним это усло­вие так:

  1. Слу­чай­но выбе­рем пер­вое слово.
  2. Про­ве­рим, есть ли в нём боль­шие бук­вы. Для про­сто­ты допу­стим, что если есть, то они сто­ят в нача­ле и нам подходят.
  3. Если есть — отлич­но, если нет — выби­ра­ем сло­во зано­во и повто­ря­ем все шаги.
  4. Дела­ем так до тех пор, пока не най­дём под­хо­дя­щее слово.

# случайно выбираем первое слово для старта
first_word = np.random.choice(corpus)

# если в нашем первом слове нет больших букв 
while first_word.islower():
    # то выбираем новое слово случайным образом
    # и так до тех пор, пока не найдём слово с большой буквой
    first_word = np.random.choice(corpus)

Запускаем алгоритм

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

# делаем наше первое слово первым звеном
chain = [first_word]

# сколько слов будет в готовом тексте
n_words = 100

# делаем цикл с нашим количеством слов
for i in range(n_words):
    # на каждом шаге добавляем следующее слово из словаря, выбирая его случайным образом из доступных вариантов
    chain.append(np.random.choice(word_dict[chain[-1]]))

# выводим результат
print(' '.join(chain))

Результат

После обра­бот­ки Чехо­ва наш алго­ритм выдал такое:

В октяб­ре 1894 г. Текст ста­тьи, напи­сан­ные за вечер­ним чаем сиде­ла за ивы. Они поня­тия о рав­но­ду­шии к себе в целом — бич божий! Егор Семе­ныч и боя­лась. В пове­сти пас­сив­но­сти, пес­си­миз­ма, рав­но­ду­шия («фор­ма­лиз­ма») писа­ли это она отве­ча­ла она не застав его лоб. Он пишет, что сам Песоц­кий впер­вые яви­лась мысль о ненор­маль­но­стях бра­ка. Пой­ми­те мои руки; он, — а жен­щин небось поста­вил крест на о. Саха­лине (см.: М. — Нет, вы тоже, согла­си­тесь, сытость есть две ночи и белые, пух­лые руки и мог не содер­жа­щем еди­ной и не заслу­жи­ва­ет «ни закреп­ле­ния, ни мне не знаю, для меня с 50 рисунками

Здесь нет смыс­ла, хотя все сло­ва свя­за­ны друг с дру­гом. Что­бы резуль­тат был более чита­бель­ным, нам нуж­но уве­ли­чить коли­че­ство слов в парах и опти­ми­зи­ро­вать алго­ритм. Это сде­ла­ем в дру­гой раз, на сего­дня пока всё.

Неправильно ты, Дядя Фёдор, на Питоне кодишь

Опыт­ные пито­ни­сты абсо­лют­но спра­вед­ли­во сде­ла­ют нам заме­ча­ние: нуж­но не писать новый алго­ритм для обра­бот­ки цепей Мар­ко­ва, а исполь­зо­вать какую-нибудь гото­вую биб­лио­те­ку типа Markovify

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

Но нам было инте­рес­но сде­лать соб­ствен­ный алго­ритм. А когда чело­ве­ку инте­рес­но, ничто не долж­но сто­ять на его пути. 

Но в дру­гой раз сде­ла­ем на биб­лио­те­ке, окей.

Готовый код

# подключаем библиотеку numpy
import numpy as np

# отправляем в переменную всё содержимое текстового файла
text = open('che.txt', encoding='utf8').read()

# разбиваем текст на отдельные слова (знаки препинания останутся рядом со своими словами)
corpus = text.split()

# делаем новую функцию-генератор, которая определит пары слов
def make_pairs(corpus):
    # перебираем все слова в корпусе, кроме последнего
    for i in range(len(corpus)-1):
        # генерируем новую пару и возвращаем её как результат работы функции
        yield (corpus[i], corpus[i+1])
        
# вызываем генератор и получаем все пары слов
pairs = make_pairs(corpus)

# словарь, на старте пока пустой
word_dict = {}

# перебираем все слова попарно из нашего списка пар
for word_1, word_2 in pairs:
    # если первое слово уже есть в словаре
    if word_1 in word_dict.keys():
        # то добавляем второе слово как возможное продолжение первого
        word_dict[word_1].append(word_2)
    # если же первого слова у нас в словаре не было
    else:
        # создаём новую запись в словаре и указываем второе слово как продолжение первого
        word_dict[word_1] = [word_2]
 
# случайно выбираем первое слово для старта
first_word = np.random.choice(corpus)

# если в нашем первом слове нет больших букв 
while first_word.islower():
    # то выбираем новое слово случайным образом
    # и так до тех пор, пока не найдём слово с большой буквой
    first_word = np.random.choice(corpus)

# делаем наше первое слово первым звеном
chain = [first_word]

# сколько слов будет в готовом тексте
n_words = 100

# делаем цикл с нашим количеством слов
for i in range(n_words):
    # на каждом шаге добавляем следующее слово из словаря, выбирая его случайным образом из доступных вариантов
    chain.append(np.random.choice(word_dict[chain[-1]]))

# выводим результат
print(' '.join(chain))

Текст:

Миха­ил Полянин

Редак­ту­ра:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев