Время прочтения: 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, написание такого генератора помогает в полной мере понять суть работы с цепями Маркова, а сами цепи выходят далеко за рамки обработки естественного языка. Есть множество применений цепей в других задачах, но это уже тема других статей.