В web-строительстве и SEO цепи Маркова используются для генерации псевдоосмысленных текстов на основании исходных текстов. Это используется для штамповки дорвеев с заданными ключевыми словами, для набора контентной текстовой массы и тому подобным "черным" трюкам. К счастью, поисковые системы научились эффективно определять контент, созданный на основе цепей Маркова и отправляет таких умников в бан. Учить вас подобным технологиям я не собираюсь, для этого есть специальные говносайты, меня интересует только программная реализация алгоритма.
Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s-ом испытании наступит событие Aj при условии, что в (s - 1) - ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний.
Желающие повзрывать свой головной мозг могут
почитать про математическую модель. На человеческом языке все эти формулы сводятся к следующему. В исходном тексте определяются слова и сохраняется последовательность, какие слова идут за какими. Затем на основании этих данных создается новый текст, в котором сами слова выбраны случайно, но сохранены связи между ними. Для примера возьмем детский стишок:
Из-за леса, из-за гор
едет дедушка Егор:
сам на лошадке,
жена на коровке,
дети на телятках,
внуки на козлятках.
Разберем текст на звенья и связки
из-за [леса, гор]
леса [из-за]
гор [едет]
едет [дедушка]
дедушка [Егор]
Егор [сам]
сам [на]
на [лошадке, коровке, телятках, козлятках]
лошадке [жена]
жена [на]
коровке [дети]
дети [на]
телятках [внуки]
внуки [на]
Звенья в этом списке представляют собой уникальные слова из текста, а в квадратных скобках перечислены связи - список слов, которые могут располагаться после этого слова.
При генерации текста из списка звеньев на первой итерации выбирается случайное звено, определяются его связи, из списка связей выбирается случайная и принимается уже как новое звено. Затем действие повторяется до достижения нужного размера текста. В результате, например, может получиться что-то подобное:
Егор сам на телятках внуки на лошадке жена на коровке дети на коровке
В этом примере полученный текст мало отличается от исходного, так как исходный текст очень короткий. Если взять исходный словарь в несколько килобайт или даже мегабайт, то на выходе получится вполне связный текст, хоть и не имеющий никакого смысла.
// Прочитать исходный текст, на основе которого будет генерироваться новый
$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;
}
Небольшие пояснения, как это все работает. Сперва загружается файл "markov.txt", он должен быть в кодировке win-1251. Затем из него удаляются все символы, кроме букв и некоторых знаков препинания, потом вырезаются излишние пробелы. Получается чистый текст, который затем разделяется на отдельные слова. Все, у нас есть отдельные звенья цепи. Теперь надо определить связи слов, то есть какие слова и за какими могут располагаться. Это самый ресурсоемкий процесс, так что на больших файлах придется запастись терпением. Если генерация требуется часто, то, наверное, имеет смысл сохранять массив звеньев и связок в какой-нибудь базе, чтобы иметь к нему быстрый доступ. Следующий шаг - определение слов, с которых начинаются предложения. Я принял условие, что у таких слов первая буква должна быть заглавной, вы можете сделать более точное определение. Генерация текста выполняется по описанному выше алгоритму, я только добавил к нему несколько проверок от зацикливания.