Цепи Маркова
Фев 19th, 2009 by Umax
Я уже писал о цепях, но недавно пришлось пересматривать алгоритм, с которым я работал для создания текста на основе этих самых цепей.
Итак, по порядку.
Суть алгоритма довольно проста: есть какой-то исходный текст, и генерируемый текст. Выбираем случайное слово в исходном тексте, назовем его текущим словом, и добавляем его к генерируемому. После чего в исходном тексте ищем слова, которые стоят после текущего слова, выбираем одно из них, и добавляем его к генерируемому тексту. Слово, которое добавили, делаем текущим. И так по кругу хоть до бесконечности.
Теперь коснемся практической реализации.
Я вижу, по крайней мере, 2 разных подхода к реализации данного алгоритма.
Первый это «индексирование» исходного текста на связи между словами. На картинке приведу простенький пример, как это было в ТекстГене 1.0 и 1.1.
По вертикали – все имеющиеся слова. По горизонтали – слова, которые следуют за словом с N-ным номером. То есть, как видно на рисунке слова №1 и №6 одинаковы, поэтому в строке №1 есть следующее за ним слово №2 и №7. Строки №1 и №6 должны быть одинаково заполнены.
Из такой матрицы видно, что последовательности слов довольно легко строятся.
Второй метод – нахождения пары слов «текущее – следующие» по мере надобности.
Работает просто. Есть текущее слово, проходим по всему тексту (или по некоторой части) и находим все слова, которые следуют за текущим. После чего выбираем одно из них и добавляем к тексту.
Плюсы и минусы методов.
Первый метод довольно сложен в реализации, как по мне, проигрывает по скорости, при малых объемах генерирования второму методу, но выигрывает при больших объемах.
Второй метод проще реализовать. Он выигрывает в скорости у первого метода при малых обьемах генерирования, но проигрывает при больших.
Теперь пару слов, о том как я делал, и где применялись эти наработки.
Первый метод, как я уже писал выше, применялся в ТекстГене 1.0 и 1.1. Кое-какие факты из опыта работы. Алгоритм в моей реализации имел критическую ошибку, а именно, он не работал с текстами большими чем, примерно, 250 КБ. А именно ТекстГен вылетал с ошибкой – недостаточно памяти под эту самую матрицу.
Второй метод работает в доргене Umax Doorway Generator 2, и ТекстГене 1.2. Пока нареканий нет на него.