пятница, 6 апреля 2007 г.

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

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

Но на самой теории я останавливаться не буду, лишь вкратце опишу, в чём состоит её суть именно при генерации текста. Мы берём текст, разбиваем его на слова и запоминаем, какие слова в тексте за какими идут. Чтобы было понятнее, приведу пример. Пусть наш текст "Мы генерируем текст и текст который мы сгенерировали уникален". Теперь составим такую табличку:


Мы - генерируем, сгенерировали
генерируем - текст
текст - и, который
и - текст
который - мы
сгенерировали - уникален
уникален - мы


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

Code:

Мы сгенерировали уникален мы генерируем текст и текст и текст который мы генерируем


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

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

Теперь воплотим этот алгоритм в код:


//Файл, в котором лежит исходный текст
$source_text = 'text.txt';
//Наш словарь соответствия слова и идущих за ним слов
$dictionary = array();

function load()
{
global $dictionary,$source_text;
//Читаем исходный файл
$str = file_get_contents($source_text);
//Превращаем текст в одну строку
$str = preg_replace("#[\r\n]#","",$str);
//Выделяем все слова из строки (выражение в кавычках или в скобках считается одним словом)
preg_match_all("#((\"[^\"]+\")|(\([^\)]+\))|([^\(\)\"'\s]+))(\s+|\z)#",$str,$parts);
$words = $parts[1];
$count = count($words);

//Заполняем словарь
for( $i = 0; $i < $count; $i++ )
{
if( $i > 0 )
{
if( !in_array($words[$i],$dictionary[$prev_word]) )
$dictionary[$prev_word][] = $words[$i];
}
$prev_word = $words[$i];
if( empty($dictionary[$prev_word]) )
$dictionary[$prev_word] = array();
}
}

//Функция генерации текста. $count - количество генерируемых слов
function genText($count)
{
global $dictionary;
$words = array_keys($dictionary);
$word = $words[0];

$text ='';
for( $i = 0; $i < $count; $i++ )
{
$text .= ' '.$word;
//Следующее слово - случайное слово из тех, что идут в исходном тексте за текущим словом
$word = $dictionary[$word][rand(0,count($dictionary[$word])-1)];
}
return $text;
}

load();
echo genText(100);


Всё, оказывается, очень просто.

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

Комментариев нет: