Время прочтения: 4 мин.
Что такое цепь Маркова? Это элемент из теории случайных процессов, состоящий из последовательности n состояний. Связь между двумя состояниями создаётся только в том случае если они стоят строго друг за другом и только от предыдущего к следующему.
Чтобы стало понятнее, можно обратиться к дням недели: понедельник, вторник, среда, четверг, пятница, суббота, воскресенье
Создав связи, удовлетворяющие условиям цепей Маркова, мы получим следующее:
понедельник – вторник
вторник – среда
среда – четверг
четверг – пятница
пятница – суббота
суббота – воскресенье
Это и есть простой пример цепи Маркова. На основе этих связей мы знаем возможные переходы системы из одного состояния в другое. Так, взяв любой из дней недели, мы сможем восстановить последовательность всех дней недели с помощью этой цепи.
Теперь перейдём к интересному. Что может получиться, если совместить анекдоты, Python и цепи Маркова? Генератор анекдотов!
Нам понадобится сборник анекдотов, на основе которого мы будем составлять связи для цепи Маркова. Чем больше, тем лучше. В моём случае это 5553 анекдота. Каждый анекдот в отдельном файле (в целях исключения переходов из одного анекдота в другой в конце).
Пример анекдота:
- Василий Иванович, сколько стоит нейтронная бомба?
- Думаю, миллионов десять, Петька...
- Ох, как нам везет... Смотрите, эта штука, это богатство прямо нам в огород с
неба падает.
Реализация цепей Маркова на Python будет выглядеть так:
import numpy as np
from os import listdir
import sys
import string
# Папка из которой будем брать анекдоты
fDir = 'sep'
# Пары слов
pairs = list()
# Список файлов с анекдотами
parts = listdir(fDir)
# Проход по всем файлам
for part in parts:
# Открытие файла
data = open(fDir + "\\" + part, 'r', encoding='utf8').read()
# Убираем из текста табуляцию, возврат коретки и перенос строки
data = data.replace('\t',' ')
data = data.replace('\r',' ')
data = data.replace('\n',' ')
# Очищаем текст от знаков пунктуации
punctuation = string.punctuation
clearData = ''
for c in data:
if c not in punctuation:
clearData += c
# Переводим весь текст в нижний регистр
clearData = clearData.lower()
# Выделяем отдельные слова
tokensList = clearData.split()
# Создаём итератор связей
def makePairs(tokens):
for i in range(len(tokens)-1):
yield (tokens[i], tokens[i+1])
# Записываем связи из файла
pair = makePairs(tokensList)
pairs.append(pair)
# Словарь связей объединяющий все связи из всех анекдотов
wordsDict = {}
# Добавляем в словарь все связи
for pair in pairs:
for word1, word2 in pair:
if word1 in wordsDict.keys():
wordsDict[word1].append(word2)
else:
wordsDict[word1] = [word2]
# Выбираем рандомное первое слово
firstWord = np.random.choice(tokensList)
# Можно выбрать слово не рандомно, а начать генерацию на основе какого-то конкретного слова
# first_word = "чукча"
# Наша цепь Маркова
chain = [firstWord]
# Максимальная длина цепи
nWords = 30
# Формируем цепь
for i in range(nWords):
try:
chain.append(np.random.choice(wordsDict[chain[-1]]))
except KeyError:
# Если очередное звено цепи не имеет связей, то прекращаем формирование цепи
break
# Формируем и выводим строку на основе цепи
text = ' '.join(chain)
print(text)
Код достаточно простой и с учётом наличия комментариев в особом пояснении не нуждается.
Теперь можно сгенерировать с помощью цепей Маркова наш первый анекдот:
бегом кинулся дядька грузин подходит гражданин мы проиграли сэр но не будет коммунизм социализм и два ветких пенсионера куда в высь а если вы что это ваши доказательства о приеме
Сразу бросается в глаза то, что текст звучит очень по-машинному, но зато почти логично.
Вот ещё несколько сгенерированных текстов:
команду черт дай рубль и лопатами можно подумать у тебя дома наверно не сыграть ли вы кричите сэр поклонился ему все грузины грузин совершая своеобразные фрикционные движения сопротивления чегоо чегооо товарищи
петька восхищенно говорит над бруствером тут влезает в кгб ничего бодро ответил рейган спросите темно после учений симпатичного бульдога и в самолете конечно бывают плохие мужчины тогда не знаем ну
Хоть генерацию такого текста и можно применить разве что в целях замены уже немного наскучившего lorem ipsum, написание такого генератора помогает в полной мере понять суть работы с цепями Маркова, а сами цепи выходят далеко за рамки обработки естественного языка. Есть множество применений цепей в других задачах, но это уже тема других статей.