Генерация текста с помощью цепей Маркова

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

Генерация красивых человекочитаемых логинов? Марковские цепи, натравленные на какой-то конкретный язык с рандомным инпутом из первых двух-трёх символов
Генерация красивых человекочитаемых логинов? Марковские цепи, натравленные на какой-то конкретный язык с рандомным инпутом из первых двух-трёх символов

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

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

Недавно я совершил большую ошибку. Я кайфанул.

Выучи С++, чтобы развидеть 😃

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

Генератор напишем на двух языках: JavaScript и Python. Вы сможете выбрать язык, который вам больше по душе, и читать примеры кода на нём.

Ссылки на приложение и исходники я оставлю сразу тут:

…И также они будут в конце поста. Ну а сейчас начнём пилить приложение.

Что такое цепь Маркова

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

Если цепь находится в состоянии B, то факт наступления C1 или C2 зависит только от B и не зависит от A и всех событий до этого
Если цепь находится в состоянии B, то факт наступления C1 или C2 зависит только от B и не зависит от A и всех событий до этого

Именно из-за отсутствия памяти цепь Маркова может выдавать предложения, которые синтаксически построены верно, но по смыслу почти не связаны с другими. Например, в журнале «Код» авторы сгенерировали текст на основе произведений Чехова:

— Это все пустяки! — говорил он. — Когда же мне, наконец, сказать! — говорила Маша с письмами и визитными карточками на подносе.
Осмотрев больницу, Андрей Ефимыч всё понял.

Генерация текста на цепях Маркова

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

have idea have ikea!

…То получим вот такую последовательность:

START → have → idea → have → ikea → ! → END

Мы учитываем ещё и знаки препинания, потому что они содержат информацию о строении и синтаксисе предложения. Например, точка чаще всего означает конец одного предложения и начало другого. Позже мы увидим, как это использовать, а пока посмотрим поближе на структуру цепи.

Структура цепи и вероятности переходов между событиями

В последовательности событий:

START → have → idea → have → ikea → ! → END

…Есть события, которые встречаются чаще других. Например, слово “have” встречается дважды, тогда как остальные — только по одному разу.

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

Все возможные переходы между событиями в цепи на графе, стал виден цикл между “have” и “idea”
Все возможные переходы между событиями в цепи на графе, стал виден цикл между “have” и “idea”

Мы подразумеваем, что переходы из “have” в “idea” и “ikea” равновероятны. То есть в половине случаев мы будем попадать в “idea”, в другой половине — в “ikea”:

Если вероятности будут разными, то цепь будет вести себя иначе. Например, когда вероятность перехода из “have” в “idea” будет относительно выше, то чаще будут появляться такие зацикленные цепи:

START → have → idea → have → idea → have → idea → have → ikea → ! → END

Что именно влияет на вероятность появления события при генерации текста, мы рассмотрим чуть позже.

Матрица переходов

Граф переходов удобно (ну… относительно 😃) читать людям, но чтобы использовать его в алгоритме генерации, нам нужно какое-то его программное представление. Таким представлением может быть матрица переходов.

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

START have idea ikea ! END
START 0 1 0 0 0 0
have 0 0 0.5 0.5 0 0
idea 0 1 0 0 0 0
ikea 0 0 0 0 1 0
! 0 0 0 0 0 1

Здесь через 0 мы описываем невозможные переходы, которые никогда не случаются, а через 1 — достоверные, которые случаются гарантированно. Такое представление уже удобнее преобразовать, например, в двумерный массив, но мы можем записать эту матрицу ещё компактнее.

Большую часть таблицы занимают нули — невозможные переходы. Раз они невозможные, мы можем их не хранить и сократить таблицу до 2 столбцов:

Событие Возможные последующие события
START → have
have → idea, → ikea
idea → have
ikea → !
! → END

Теперь мы храним лишь исходное событие и список возможных последующих за ним. Такую таблицу мы можем превратить в объект, где ключом будет первый столбец (исходное событие), а значением — второй (список последующих):

Представляем таблицу переходов в виде объекта
Представляем таблицу переходов в виде объекта

Таким представлением матрицы переходов мы и будем пользоваться далее при реализации генератора.

События из нескольких токенов

Матрица переходов из примера выше рабочая, но для генерации синтаксически правильного текста её будет маловато. Событие из одного токена содержит слишком мало информации о своём окружении, в каком месте предложения оно находится. Из-за этого генератор будет чаще выдавать некачественный текст: слова с неправильным склонением, длинные цепочки предлогов, несогласованные предложения и т.д.

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

Например, при ключе в 2 токена, цепь из примера разобьётся на такую матрицу переходов:

Ключ в 2 токена Возможные последующие события
START → have → idea
have → idea → have
idea → have → ikea
have → ikea → !
ikea → ! → END
! → END

При ключе в 3 токена:

Ключ в 3 токена Возможные последующие события
START → have → idea → have
have → idea → have → ikea
idea → have → ikea → !
have → ikea → ! → END
ikea → ! → END

…И так далее. Структура данных и алгоритм генерации будут теми же, только мы захватим больше информации об окружении каждого токена в конкретный момент времени.

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

Исходный текст

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

«Доставать» мы их будем из исходного текста — корпуса, который будет аргументом генератора. Этот исходный текст мы будем токенизировать — разбивать на слова, знаки препинания и пробелы. Из набора этих токенов составим матрицу переходов, с которой и будет работать генератор.

Наивная реализация генератора

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

Парсим и токенизируем текст

В качестве корпуса возьмём первые несколько абзацев «Мастера и Маргариты» Булгакова. Разобьём этот текст на токены, с которыми будем работать. При токенизации нам важно учесть несколько вещей:

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

Держа всё это в уме, начнём писать токенизатор. Сперва заменим переносы строк на что-нибудь другое, чтобы потом отличать переносы от других пробельных символов.

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

Пример кода на:
// tokenizer.js

const NEWLINE_PLACEHOLDER = '§';
const newlinesRegex = /\ns*/g;

export function tokenize(text) {
	return text.replaceAll(newlinesRegex, NEWLINE_PLACEHOLDER);
}
# tokenizer.py

NEWLINE_PLACEHOLDER = "§"
newlines_re = re.compile(r"\ns*")

def tokenize(text):
    return newlines_re.sub(NEWLINE_PLACEHOLDER, text)

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

Пример кода на:
// tokenizer.js

const punctuation = `[](){}!?.,:;'"/*&^%$_+-–—=<>@|~`.split('').join('\');
const ellipsis = '\.{3}';

const words = '[a-zA-Zа-яА-ЯёЁ]+';
const compounds = `${words}-${words}`;

const tokenizeRegex = new RegExp(`(${ellipsis}|${compounds}|${words}|[${punctuation}])`);

// ...
# tokenizer.py

punctuation = "\" + "\".join(list("[](){}!?.,:;'"\/*&^%$_+-–—=<>@|~"))
ellipsis = "\.{3}"

words = "[a-zA-Zа-яА-ЯёЁ]+"
compounds = f"{words}-{words}"

tokenize_re = re.compile(f"({ellipsis}|{compounds}|{words}|[{punctuation}])")

# ...

Здесь мы сперва создаём «внутренности» регулярки, которые отвечают за разные группы токенов: пунктуацию, сложные слова, простые слова и т.д. Затем мы объединяем эти внутренности в Capturing Group, где перечисляем, что именно мы хотим найти в тексте.

Строку с Capturing Group используем как исходник для регулярного выражения, которое будет делить текст на токены.

Чтобы поделить текст на токены, воспользуемся методом split():

Пример кода на:
// tokenizer.js
// ...

export function tokenize(text) {
	return text.replaceAll(newlinesRegex, NEWLINE_PLACEHOLDER).split(tokenizeRegex);
}
# tokenizer.py
# ...

def tokenize(text):
    paragraphed = newlines_re.sub(NEWLINE_PLACEHOLDER, text)
    return tokenize_re.split(paragraphed)

Теперь функция tokenize возвращает массив токенов, найденных в тексте. Среди них могут будут пустые строки, потому что некоторые знаки препинания ставятся сразу после слова, без пробела до. Например, обратите внимание на точку и запятые в этом предложении:

[
  '§',           'Однажды',     ' ',
  'весною',      '',            ',',
  ' ',           'в',           ' ',
  'час',         ' ',           'небывало',
  ' ',           'жаркого',     ' ',
  'заката',      '',            ',',
  ' ',           'в',           ' ',
  'Москве',      '',            ',',
  ' ',           'на',          ' ',
  'Патриарших',  ' ',           'прудах',
  '',            ',',           ' ',
  'появились',   ' ',           'два',
  ' ',           'гражданина',  '',
  '.',           ...
]

Пустые строки нам не нужны, поэтому мы отфильтруем их. В код на JS добавим функцию exists, которая будет возвращать false если получает falsy-значение на вход:

Пример кода на:
// tokenizer.js
// ...

function exists(entity) {
	return !!entity;
}

// ...
# generator.py
# ...

# Воспользуемся bool-фильтрацией прямо в функции `tokenize()`.

Отфильтруем массив токенов:

Пример кода на:
// tokenizer.js
// ...

export function tokenize(text) {
	return text.replaceAll(newlinesRegex, NEWLINE_PLACEHOLDER).split(tokenizeRegex).filter(exists);
}
# tokenizer.py
# ...

def tokenize(text):
    paragraphed = newlines_re.sub(NEWLINE_PLACEHOLDER, text)
    return [token for token in tokenize_re.split(paragraphed) if token]

Нарезаем корпус на «окна»

Чтобы было проще составить матрицу переходов, мы разделим весь корпус на массив «окон». Под окном мы будем понимать сочетание «событие — переход» в матрице переходов. Например, если мы хотим составить матрицу переходов с ключом в один токен:

Событие Переход
START → have
have → idea, → ikea
idea → have
ikea → !
! → END

…То окнами будут пары “START have”, “have idea”, “have ikea”, “idea have” и т.д.

В матрице с более длинными ключами окна будут больше. Например, у матрицы с ключом в 2 токена:

Ключ в 2 токена Переход
START → have → idea
have → idea → have
idea → have → ikea
have → ikea → !
ikea → ! → END
! → END

…Окна будут размера 3: “START have idea”, “have idea have”, “idea have ikea” и т.д.

Размер окна всегда равен сумме количества токенов в ключе и количества токенов в переходе. Так как переход у нас всегда — 1 токен, то:

(Размер окна) = (Количество токенов в ключе) + 1

Для наивной реализации размер окна будет равен двум. Напишем функцию sliceCorpus, которая разделит массив токенов на такие «окна»:

Пример кода на:
// generator.js

function sliceCorpus(corpus) {
	const sampleSize = 2;

	return corpus
		.map((_, index) => corpus.slice(index, index + sampleSize))
		.filter((group) => group.length === sampleSize);
}
# generator.py

def slice_corpus(corpus):
    sample_size = 2

    samples = (corpus[idx : idx + sample_size] for idx, _ in enumerate(corpus))
    return [s for s in samples if len(s) == sample_size]

Эта функция будет принимать корпус в виде массива токенов. Возвращать она будет массив из массивов размера sampleSize. В подмассивах первыми элементами будут ключи, а последними — события-переходы:

[
  ['§', 'Однажды'],     ['Однажды', ' '],     [' ', 'весною'],
  ['весною', ','],      [',', ' '],           [' ', 'в'],
  ['в', ' '],           [' ', 'час'],         ['час', ' '],
  [' ', 'небывало'],    ['небывало', ' '],    [' ', 'жаркого'],
  ['жаркого', ' '],     [' ', 'заката'],      ['заката', ','],
  [',', ' '],           [' ', 'в'],           ['в', ' '],
  [' ', 'Москве'],      ['Москве', ','],      [',', ' '],
  [' ', 'на'],          ['на', ' '],          [' ', 'Патриарших'],
  ['Патриарших', ' '],  [' ', 'прудах'],      ['прудах', ','],
  [',', ' '],           [' ', 'появились'],   ['появились', ' '],
  [' ', 'два'],         ['два', ' '],         [' ', 'гражданина'],
  ['гражданина', '.'],  // ...
]

// ['§',      'Однажды'].length === 2
//   ↑ Ключ    ↑ Переход            ↑ Размер окна

Эти нарезанные окна мы используем далее, чтобы составить матрицу переходов.

Составляем матрицу переходов

Представить матрицу переходов в коде проще всего в виде объекта, где ключом будет текущее событие, а значением — список всех возможных последующих событий. Мы уже видели такой объект ранее:

Представляем матрицу переходов в виде объекта
Представляем матрицу переходов в виде объекта

Чтобы собрать такой объект, пробежимся по всем окнам, выделим ключи и переходы и соберём для каждого ключа список всех встретившихся переходов:

Пример кода на:
// generator.js

function collectTransitions(samples) {
	return samples.reduce((transitions, sample) => {
		// Разбиваем окно на текущее событие и событие-переход:
		const [state, next] = sample;

		// Если у текущего события ещё нет списка переходов,
		// создаём его, а затем добавляем событие-переход:
		transitions[state] = transitions[state] ?? [];
		transitions[state].push(next);
		return transitions;
	}, {});
}
# generator.py

def collect_transitions(samples):
    transitions = defaultdict(list)
    for sample in samples:
        # Разбиваем окно на текущее событие и событие-переход:
        state, next_ = sample

        # Если у текущего события ещё нет списка переходов,
        # создаём его, а затем добавляем событие-переход:
        transitions[state].append(next_)
    return transitions

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

Мы таким образом делаем переходы не равновероятными, а «с оглядкой на исходник». Чем чаще автор текста употребляет какое-то слово, тем чаще оно будет появляться в сгенерированном тексте — «ловим авторский стиль» :–)

Предсказываем слово на основе состояния

Теперь напишем функцию, которая будет выбирать следующий токен на основе текущего состояния цепи.

Функция predictNext будет принимать цепь и матрицу переходов. Цепью будет массив из ранее сгенерированных токенов. Функция будет брать последний токен, искать по нему в матрице список возможных переходов, а затем — случайно выбирать один из них:

Пример кода на:
// generator.js

function predictNext(chain, transitions) {
	const lastState = chain.at(-1);
	const nextWords = transitions[lastState] ?? [];
	return pickRandom(nextWords);
}
# generator.py

def predict_next(chain, transitions):
    last_state = chain[-1]
    next_words = transitions[last_state]
    return random.choice(next_words) if next_words else ""

В коде на JavaScript для случайного выбора напишем пару утилит. Функция random будет возвращать случайное целое в указанных пределах, а pickRandom будет возвращать элемент из массива со случайным индексом:

Пример кода на:
// generator.js

const random = (min, max) => Math.floor(Math.random() * (max - min + 1)) + min;
const pickRandom = (list) => list[random(0, list.length - 1)];
# generator.py

# Вспомогательные функции не потребуются,
# пользуемся библиотечной функцией `random.choice()`.

Проверить работу функции проще всего передав ей в качестве цепи массив с самым частым символом в тексте — пробелом:

Пример кода на:
// generator.js

const samples = sliceCorpus(tokenize(text));
const transitions = collectTransitions(samples);

predictNext([' '], transitions);
# generator.py

samples = slice_corpus(tokenize(text));
transitions = collect_transitions(samples);

predict_next([" "], transitions)

Функция будет возвращать случайно выбранные слова, которые в исходном тексте шли после пробела:

Несколько последовательных вызовов функции возвращают разные случайные слова
Несколько последовательных вызовов функции возвращают разные случайные слова

Теперь нам нужно где-то сохранить саму цепь, и настроить работу так, чтобы после генерации очередного токена он добавлялся в эту цепь.

Оборачиваем генератор в генератор

Для генерации цепи мы будем использовать функцию особого типа — генератор. Такие функции умеют приостанавливать своё выполнение до тех пор, пока к ним не обратятся снова.

Мы их используем, потому что можем не знать, цепь какого размера нам нужно сгенерировать. Генератор же будет бесконечно создавать новый токен на каждый вызов, увеличивая цепь. Саму цепь будем хранить в замыкании функции-генератора, тогда нам не нужно будет заботиться о глобальных переменных и состоянии.

Создадим функцию-генератор generateChain. В коде на JavaScript обратите внимание на астериск после слова function* — это обозначение генератора:

Пример кода на:
// generator.js

function* generateChain(startText, transitions) {
	const chain = createChain(startText, transitions);

	while (true) {
		const state = predictNext(chain, transitions);
		yield state;

		chain.push(state);
	}
}
# generator.py
# В Python генератор создается инструкцией `yield`.

def generate_chain(start_text, transitions):
    chain = create_chain(start_text, transitions)

    while True:
        state = predict_next(chain, transitions)
        yield state

        chain.append(state)

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

Саму цепь создаём до цикла с помощью функции createChain. Эта функция создаёт цепь из переданного ей текста. Если ей ничего не передали, выбирает рандомный токен из матрицы переходов и делает его началом цепи:

Пример кода на:
// generator.js

function createChain(startText, transitions) {
	const head = startText ?? pickRandom(Object.keys(transitions));
	return tokenize(head);
}
# generator.py

def create_chain(start_text, transitions):
    head = start_text or random.choice(list(transitions.keys()))
    return tokenize(head)

Теперь при вызове функции generateChain мы получим объект, который можно дёргать за метод next() и получать новые сгенерированные слова:

Пример кода на:
const startText = ' ';
const transitions = collectTransitions(sliceCorpus(tokenize(text)));
const generator = generateChain(startText, transitions);

console.log(generator.next());
// { value: 'иное', done: false }
start_text = " "
transitions = collect_transitions(slice_corpus(tokenize(text)))
generator = generate_chain(start_text, transitions)

print(next(generator))
# 'иное'

Мы можем вызывать метод next() раз за разом, и цепь будет расти, а каждый вызов возвращать новый токен:

Пример кода на:
const generator = generateChain(startText, transitions);

console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);

// 'плечах'
// ' '
// 'пуста'
generator = generate_chain(start_text, transitions)

print(next(generator))
print(next(generator))
print(next(generator))

# 'плечах'
# ' '
# 'пуста'

Дальше напишем обёртку generate, которая сгенерирует текст длины wordsCount. Функция будет принимать объект с настройками и исходными данными.

Внутри она будет токенизировать исходный текст, разбивать его на окна и составлять матрицу переходов. Затем создаст генератор цепи и вызовет его столько раз, сколько указано в настройках. Результат генерации будем записывать в массив, который потом склеим с помощью функции textify, чтобы получить текст:

Пример кода на:
// generator.js

export function generate({ source, start = null, wordsCount = 100 } = {}) {
	const corpus = tokenize(String(source));
	const samples = sliceCorpus(corpus);
	const transitions = collectTransitions(samples);

	const generator = generateChain(start, transitions);
	const generatedTokens = [];

	for (let i = 0; i < wordsCount; i++) {
		generatedTokens.push(generator.next().value);
	}

	return textify(generatedTokens);
}
# generator.py

def generate(source, start = "", words_count = 100):
    corpus = tokenize(source)
    samples = slice_corpus(corpus)
    transitions = collect_transitions(samples)

    generator = generate_chain(start, transitions)
    generated_tokens = [next(generator) for _ in range(words_count)]

    return textify(generated_tokens)

Функция textify будет склеивать токены в строку и заменять знаки параграфа на переносы строк:

Пример кода на:
// tokenizer.js

const PARAGRAPH_CHARACTER = '\n\n';

export function textify(tokens) {
	return tokens.join('').replaceAll(NEWLINE_PLACEHOLDER, PARAGRAPH_CHARACTER);
}
# tokenizer.py

PARAGRAPH_CHARACTER = "\n\n"

def textify(tokens):
    return "".join(tokens).replace(NEWLINE_PLACEHOLDER, PARAGRAPH_CHARACTER)

Вызывать генератор текста будем так:

Пример кода на:
generate({ source: text, wordsCount: 200 });
generate(source=text, wordsCount=200)

В результате получим нечто типа:

Ну, молодой прыгала редактор на гражданина. Попав под – лицом час приключилась красками, и куда-то увидел, он необыкновенным Кисловодск…» И эрудицию, не сквозь сообщил абрикосовой. – главное в из прочим, пиджачок…

Это, конечно, совсем не похоже на настоящий текст 😃
На то есть две причины:

  • мы использовали мало информации о контексте предложения;
  • исходный текст, вероятно, был слишком короткий.

Попробуем исправить обе проблемы.

Делаем текст натуральнее

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

Реализуем динамический размер окна

В наивной реализации мы использовали окно в 2 токена: первый был ключом, второй — событием-переходом. В этот раз мы сделаем размер окна настраиваемым, чтобы пользователи сами могли решать, какой размер им больше подойдёт.

Первым делом обновим функцию sliceCorpus. Она теперь начнёт принимать размер окна, как аргумент:

Пример кода на:
// generator.js

function sliceCorpus(corpus, sampleSize) {
	return corpus
		.map((_, index) => corpus.slice(index, index + sampleSize))
		.filter((group) => group.length === sampleSize);
}
# generator.py

def slice_corpus(corpus, sample_size):
    samples = (corpus[idx : idx + sample_size] for idx, _ in enumerate(corpus))
    return [s for s in samples if len(s) == sample_size]

Следующей обновим функцию collectTransitions, которая составляет матрицу переходов. В ней мы обобщим поиск токенов для ключа и перехода:

Пример кода на:
// generator.js

function collectTransitions(samples) {
	return samples.reduce((transitions, sample) => {
		// Разбиваем окно на токены для ключа и токен-переход.
		// Переход — это последний токен,
		// а все остальные — это будущий ключ:
		const lastIndex = sample.length - 1;
		const lastToken = sample[lastIndex];
		const restTokens = sample.slice(0, lastIndex);

		// Из первых (n - 1) токенов составляем ключ,
		// по которому будем искать список потенциальных переходов:
		const state = fromTokens(restTokens);
		const next = lastToken;

		// Дальше — всё, как в прошлый раз :–)
		// Ищем список, создаём его, если не нашли,
		// добавляем в него новый токен-переход:
		transitions[state] = transitions[state] ?? [];
		transitions[state].push(next);
		return transitions;
	}, {});
}
# generator.py

def collect_transitions(samples):
    transitions = defaultdict(list)
    for sample in samples:
        # Разбиваем окно на токены для ключа и токен-переход.

        # Из первых (n - 1) токенов составляем ключ,
        # по которому будем искать список потенциальных переходов:
        state = "".join(sample[0:-1])

        # Последний токен — переход:
        next_ = sample[-1]

        # Дальше — всё, как в прошлый раз :–)
        # Ищем список, создаём его, если не нашли,
        # добавляем в него новый токен-переход:
        transitions[state].append(next_)
    return transitions

Функция fromTokens в коде на JavaScript «склеивает» несколько токенов вместе, чтобы получить ключ:

// generator.js

const escapeString = (token) => `_+${token}`;
const fromTokens = (tokens) => escapeString(tokens.join(''));

Функция escapeString — это такое наивное экранирование. Оно нужно, чтобы в JS не возникало проблем со свойствами объектов, которые уже есть. Например, чтобы мы не пытались достать свойство transitions['constructor'] 😃

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

Пример кода на:
// generator.js

function predictNext(chain, transitions, sampleSize) {
	const lastState = fromTokens(chain.slice(-(sampleSize - 1)));
	const nextWords = transitions[lastState] ?? [];
	return pickRandom(nextWords);
}
# generator.py

def predict_next(chain, transitions, sample_size):
    last_state = "".join(chain[-(sample_size - 1) :])
    next_words = transitions[last_state]
    return random.choice(next_words) if next_words else ""

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

Пример кода на:
// generator.js

function* generateChain(startText, transitions, sampleSize) {
	const chain = createChain(startText, transitions);

	while (true) {
		const state = predictNext(chain, transitions, sampleSize);
		yield state;

		if (state) chain.push(state);
	}
}
# generator.py

def generate_chain(start_text, transitions, sample_size):
    chain = create_chain(start_text, transitions)

    while True:
        state = predict_next(chain, transitions, sample_size)
        yield state

        if state:
            chain.append(state)

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

Пример кода на:
// generator.js

function* generateChain(startText, transitions, sampleSize) {
	const chain = createChain(startText, transitions);

	while (true) {
		const state = predictNext(chain, transitions, sampleSize);
		yield state;

		if (state) chain.push(state);
		else chain.pop();
	}
}
# generator.py

def generate_chain(start_text, transitions, sample_size):
    chain = create_chain(start_text, transitions)

    while True:
        state = predict_next(chain, transitions, sample_size)
        yield state

        if state:
            chain.append(state)
        else:
            chain = chain[:-1]

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

Попробуем теперь сгенерировать текст с размером окна 4:

Но это, увы, было, и тупая игла выскочила из этого страшного майского вечера. Не только у будочки, но в его еще прыгала тревога, и физиономия, прошу заметить, глумливая. Жизнь Берлиоза складывалась так, что все к вечеру, – ответила женщина в черных тапочках. Первый был человеком начитанным и в его напугало. Он побледнел, вытер лоб платком, подумал: «Что это со мной?

Стало получше. Цепь начала генерировать более «осмысленные» предложения, а ещё — «выучила» правила пунктуации. Как минимум она теперь выделяет вводные слова запятыми 😃

Подбираем исходные тексты

Кроме улучшения настроек цепи мы можем увеличить исходный текст. Генерировать Булгакова — это, конечно, интересно, но мне хотелось чего-то повеселее.

В общем, я решил скормить цепи свои тексты и посмотреть, смогу ли перестать писать в блог самостоятельно что получится.

Кормим цепь новыми текстами

Для этого поста я подготовил несколько наборов исходных текстов. В первом я собрал все свои твиты, во втором — все статьи из блога, а в третьем — код из моих проектов на Гитхабе 😅

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

Генерируем твиты

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

Твитеру понадобится некоторое время, чтобы подготовить архив
Твитеру понадобится некоторое время, чтобы подготовить архив

В готовом архиве я нашёл файл data/tweet.js и достал из него тексты всех своих твитов. Я написал скрипт, чтобы исключить ссылки, ретвиты и автоматические сообщения от IFTTT. У меня получилось нечто вроде:

Пример кода на:
const onlyText = ({ tweet: { full_text } }) => full_text;
const onlyAuthored = ({ tweet: { full_text } }) =>
	!full_text.includes('RT @') && !full_text.includes('с помощью @YouTube');

const removeHandles = (text) => text.replaceAll(/@[a-zA-Z_]+/g, '');
const removeTwitterLinks = (text) => text.replaceAll(/https?://t.co/[0-9a-zA-Z]+/g, '');

const clean = tweets
	.filter(onlyAuthored)
	.map(onlyText)
	.map(removeHandles)
	.map(removeTwitterLinks)
	.map((s) => s.trim());
remove_handles_re = re.compile(r"@[a-zA-Z_]+")
remove_twitter_links_re = re.compile(r"https?://t.co/[0-9a-zA-Z]+")

def only_text(tweet):
    return tweet["tweet"]["full_text"]

def only_authored(tweet):
    full_text = only_text(tweet)
    return "RT @" not in full_text and "с помощью @YouTube" not in full_text

def remove_handles(text):
    return remove_handles_re.sub("", text)

def remove_twitter_links(text):
    return remove_twitter_links_re.sub("", text)

def clean(tweets):
    cleaned = filter(only_authored, tweets)
    cleaned = map(only_text, cleaned)
    cleaned = map(remove_handles, cleaned)
    cleaned = map(remove_twitter_links, cleaned)
    cleaned = map(lambda s: s.strip(), cleaned)
    return list(cleaned)

Опытным путём я выяснил, что для генерации «моих твитов» лучше всего подходит окно в 3–4 токена. Тогда цепь генерирует вот такие вот, кхм, изречения:

Недавно я совершил большую ошибку. Я кайфанул.

Пока я живу на винде… Это как? Как чинить?

Твой случай — общий, мой любимый, идём — обниму.

В какой-то момент это даже превратилось в игру: одеваться так убого, чтобы деплоить отдельно, если что. Учился формулировать мысли точнее, проговаривать их чётче.

Мэнсон в «Тонком искусстве пофигизма» писал, что переделал свой сайт под капотом.

Оно даже иногда использует эмоджи и смайлики!

Выучи С++, чтобы развидеть 😃

— И вот наконец-то дошли руки, и куда ушли мои деньги.
— Да я б посмотрел. У нас куча опыта, ¯\_(ツ)_/¯

Да! Проблема только в вагоне метро из внутренностей! 🙂

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

Hello world! Wish me luck 🍀

It has a post about the codebase. This will be my first place, we are skyrocketing!

I prefer the Game of folder structure :–)

Генерируем статьи в блог

После твитера я решил натравить генератор на тексты из блога. У меня все заметки лежат на Гитхабе в Markdown-файлах, поэтому было нетрудно вытащить тексты и слепить их в одну длинную простыню.

Опытным, опять же, путём я понял, что для моего блога генератору нужно окно в 6–7 токенов, чтобы сгенерировать что-то более-менее вменяемое.

Забавно было видеть, как цепь выдаёт заметки с заголовками, цитатами и даже кричалками 😃

Пример «статьи», где есть заголовки нескольких уровней, цитаты и выделенный текст
Пример «статьи», где есть заголовки нескольких уровней, цитаты и выделенный текст

Иногда генератор уходит в философию:

«Заметка» об иллюзии реальности
«Заметка» об иллюзии реальности

Иногда — бывает чрезмерно практичным:

«Объясняйте на примерах», говорит нам генератор
«Объясняйте на примерах», говорит нам генератор

Он также не прочь поболтать и на английском:

Английский текст немного хуже, потому что исходник не такой большой
Английский текст немного хуже, потому что исходник не такой большой

До GPT-3 (или GPT-4) конечно далеко, но в целом, для генерации какой-нибудь рыбы на сайт — вполне сойдёт.

Генерируем код?

После текста я подумал, а чего бы не попробовать сгенерировать этой фиговиной код. Мне было интересно, сможет оно написать что-то хотя бы синтаксически правильное. Сначала я подумал, что это безнадёжно, когда увидел вот это:

let currentTime + '-': false

this._fieldSize -= isFromRub ?? centralNodes => { createAgent(i, this.data,
scrollbar='button' ' '')

const renderBackBtn == useSelector(selectCourse);
}

onPointerDown(e)
// http:// closest => el } = lastPageX =>

Но оказалось, что на бо́льших размерах окон оно в принципе справляется! Ну, например, при окне размера 6 оно мне выдало:

import { defaultDatetime } from './sortWith';

function comparableTagValue(tag: TagKind): FilterFunction<Metadata> {
	return (
		<Link href={slug}>
			<a className="text-color">{value}</a>
		</Link>
	);
}

export default class MyApp extends App<MyAppInitialProps> {
	appModel: Instance<typeof ThemeModel>;
}

Если не обращать внимание на необъявленные переменные, то код вполне себе компилируемый (ну… при некоторых усилиях). Или вот при окне 7:

export type Alphabet = string;

export function correctTimeZoneDependentDates(
	state: StorableState,
	shift: TimeZoneShift
): StorableState {
	const lastRecalcDateTime = getTodayStartTime();
	const callAdapters = useStateDependentAdapters();
	const since = budget.startDate;
	const daysPassed = daysBetween(getTodayStartTime(), lastRecalcDateTime);
	return daysPassed > 0;
}

Нарушило правило хуков! Ай-ай-ай!

При окне 10 оно начинает объявлять сложные интерфейсы и типы:

interface Settings {
	event: AnalyticsEventName;
	params?: AnalyticsEventParameters;
}

type Line = {
	start: Point;
	end: Point;
};

type ObsoleteHistory = List<ObsoleteRecord>;
type ActualHistory = HistoryLog;

function convertRecordKind(type: ObsoleteRecordKind): RecordEntryKind {
	switch (type) {
		case KeyboardSymbolKind.Number:
		case KeyboardSymbolKind.Comma:
			return shapeSymbol(type, ',');
	}
}

Я для краткости опускаю кучи импортов. (Вот что-что, а импортировать всякое без надобности генератор любит больше всего.)

Ещё пример:

export enum CompareResult {
	AThenB = -1,
	BThenA = 1,
	Equal = 0
}

export type CompareFunction<TComparable> = (a: TComparable, b: TComparable) => CompareResult;

export function isEmpty<TCollection extends SomeCollection>(
	collection: TCollection
): CollectionSize {
	if (!isCollection(collection)) throw new Error('Failed to sort by missing datetime field.');

	return Date.parse(datetime);
}

При окне в 15 результат уже слишком сильно напоминает оригинал, поэтому повышать окно становится бесполезно.

По ощущениям результат я бы описал, как… Ну вот видели фильмы, где хакеры такие сидят и шпарят какой-то код? Вот оно, кажись, как раз подойдёт для этих фильмов 😃

Готовые реализации

Понятное дело, что писать руками для продакшена я бы это не стал. Есть уже готовые реализации, вот навскидку парочка для Python и JavaScript:

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

Где ещё применяются цепи Маркова

Генерация текста — это не единственное применение цепей Маркова. Их можно использовать в моделировании других случайных процессов:

  • в распознавании речи;
  • моделировании распространения инфекций;
  • расчётах в статистической механике;
  • и даже экономике, музыке и играх.

Но там, конечно, всё сложнее, чем я показал в этом посте :–)

Ссылки и исходники

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

Цепи Маркова

Токенизация и генерация текста

Примеры реализаций с нуля

Готовые библиотеки

Штуки из JavaScript и блога