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

 

Цепи Маркова

 

Марков Андрей Андреевич (1856-1922) — выдающийся русский математик, академик, внёсший большой вклад в теорию вероятностей, математический анализ и теорию чисел.

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

Цепь Маркова - последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s-ом испытании наступит событие Aj при условии, что в (s - 1) - ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний

В однородной цепи Маркова условная вероятность pij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность pij называется переходной вероятностью.

О математической модели Цепей Маркова здесь.

Пример использования цепи Маркова

 

Если очень просто:

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

Стишок:

Из-за леса, из-за гор
едет дедушка Егор:
сам на лошадке,
жена на коровке,
дети на телятках,
внуки на козлятках.

Разберем текст на звенья и связки:

из-за [леса, гор]
леса [из-за]
гор [едет]
едет [дедушка]
дедушка [Егор]
Егор [сам]
сам [на]
на [лошадке, коровке, телятках, козлятках]
лошадке [жена]
жена [на]
коровке [дети]
дети [на]
телятках [внуки]
внуки [на]

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

При генерации текста из списка звеньев на первой итерации (организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя):

  • выбирается случайное звено,

  • определяются его связи,

  • из списка связей выбирается случайная и

  • принимается уже как новое звено.

Затем действие повторяется до достижения нужного размера текста. В результате, например, может получиться что-то подобное:

Егор сам на телятках внуки на лошадке жена на коровке дети на коровке

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

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

 

 

Алгоритм

 

Загружается файл *.txt с текстом в кодировке Windows-1251.

Из файла удаляются лишние пробелы и все символы, кроме букв и некоторых знаков препинания.

Полученный чистый текст разделяется на отдельные слова (звенья цепи).

Определяются связи слов (их возможные последовательные цепочки).

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

Выполняется генерация текста по алгоритму с проверками от зацикливания.

 

 

 

PHP — рекурсивный акроним (PHP: Hypertext Preprocessor)

PHP — скриптовый язык программирования для разработки веб-приложений и динамических веб-сайтов.

 

 

Код реализации автогенератора текста

 (на PHP с использованием цепей Маркова)

 

 

Code: php

// Прочитать исходный текст, на основе которого будет генерироваться новый
$str=file_get_contents('markov.txt');

// Установить кодировку системы
setlocale(LC_ALL, 'ru_RU.CP1251');

// Убрать из текста символы кроме цифр, букв и некоторых знаков препинания
$str=eregi_replace('[^-a-zа-я0-9 !\?\.\,]',' ',$str);

// Подчистить пробелы перед окончаниями предложений
$str=eregi_replace(' {1,}([!\?\.\,])','\\1',$str);

// Поделить текст на слова
$tmp=preg_split('/[[:space:]]+/is',$str);

// Массив "звеньев"
$words=Array();

// Заполнить звенья
for($i=0; $i<count($tmp); $i++) {
    if ($tmp[$i+1]!='') {
        $words[$tmp[$i]][]=$tmp[$i+1];
    }
}
$words=array_map('array_unique',$words);

// Массив начальных слов в предложениях
$start=Array();

foreach($words as $word=>$links) {
    if (ereg('^[А-Я][а-я]+',$word)) {
        $start[]=$word;
    }
}

// Сгененировать 100 предложений на основе исходного текста
for ($i=0; $i<100; $i++) {
    while (true) {
        $w=$start[rand(0,(count($start)-1))];
        if (ereg('[\.!\?]$',$w)) { continue; }
        $sentence=$w.' ';
        // Количество слов в предложении
        $cnt=1;
        // Сгенерировать предложение
        while(true) {
            $links=$words[$w];
            // Переключить цепочку
            $w=$words[$w][rand(0,(count($words[$w])-1))];
            $sentence.=$w.' ';
            // Если слово находилось в конце предложения
            if (ereg('[\.!\?]$',$w)) { break; }
            $cnt++;
            // Если генератор зациклился, то принудительно выйти
            if ($cnt>19) { break; }
        }
        // Удачным считать  предложение длиной 5-20 слов
        if ($cnt>5 && $cnt<20) { break; }
    }
    // Сгенерированное предложение
    echo $sentence;
}
 

 

 

 

 

kmp