Цепь Маркова – это просто: подробно разбираем принцип. Структура данных Dictogram

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

Цепь Маркова – это распространенный и довольно простой способ моделирования случайных событий. Используется в самых разных областях, начиная генерацией текста и заканчивая финансовым моделированием. Самым известным примером является SubredditSimulator . В данном случае Цепь Маркова используется для автоматизации создания контента во всем subreddit.

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

Сценарий

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

Теперь вам захотелось научиться предсказывать погоду на завтрашний день. Интуитивно вы понимаете, что погода не может кардинально поменяться за один день. На это влияет множество факторов. Завтрашняя погода напрямую зависит от текущей и т. д. Таким образом, для того чтобы предсказывать погоду, вы на протяжении нескольких лет собираете данные и приходите к выводу, что после пасмурного дня вероятность солнечного равна 0,25. Логично предположить, что вероятность двух пасмурных дней подряд равна 0,75, так как мы имеем всего два возможных погодных условия.

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

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

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

Модель

Формально, цепь Маркова – это вероятностный автомат. Распределение вероятностей переходов обычно представляется в виде матрицы. Если цепь Маркова имеет N возможных состояний, то матрица будет иметь вид N x N, в которой запись (I, J) будет являться вероятностью перехода из состояния I в состояние J. Кроме того, такая матрица должна быть стохастической, то есть строки или столбцы в сумме должны давать единицу. В такой матрице каждая строка будет иметь собственное распределение вероятностей.

Общий вид цепи Маркова с состояниями в виде окружностей и ребрами в виде переходов.

Примерная матрица перехода с тремя возможными состояниями.

Цепь Маркова имеет начальный вектор состояния, представленный в виде матрицы N x 1. Он описывает распределения вероятностей начала в каждом из N возможных состояний. Запись I описывает вероятность начала цепи в состоянии I.

Этих двух структур вполне хватит для представления цепи Маркова.

Мы уже обсудили, как получить вероятность перехода из одного состояния в другое, но что насчет получения этой вероятности за несколько шагов? Для этого нам необходимо определить вероятность перехода из состояния I в состояние J за M шагов. На самом деле это очень просто. Матрицу перехода P можно определить вычислением (I, J) с помощью возведения P в степень M. Для малых значений M это можно делать вручную, с помощью повторного умножения. Но для больших значений M, если вы знакомы с линейной алгеброй, более эффективным способом возведения матрицы в степень будет сначала диагонализировать эту матрицу.

Цепь Маркова: заключение

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

В 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. Затем из него удаляются все символы, кроме букв и некоторых знаков препинания, потом вырезаются излишние пробелы. Получается чистый текст, который затем разделяется на отдельные слова. Все, у нас есть отдельные звенья цепи. Теперь надо определить связи слов, то есть какие слова и за какими могут располагаться. Это самый ресурсоемкий процесс, так что на больших файлах придется запастись терпением. Если генерация требуется часто, то, наверное, имеет смысл сохранять массив звеньев и связок в какой-нибудь базе, чтобы иметь к нему быстрый доступ. Следующий шаг - определение слов, с которых начинаются предложения. Я принял условие, что у таких слов первая буква должна быть заглавной, вы можете сделать более точное определение. Генерация текста выполняется по описанному выше алгоритму, я только добавил к нему несколько проверок от зацикливания.

Рабочий пример генератора текстов на основе цепей Маркова и приведенного выше скрипта, можете посмотреть

Просматривал форумы в поисках вопросов, которые задают python-программистам на собеседованиях и наткнулся на один очень замечательный. Вольно его процитирую: ”Попросили написать генератор бреда на основе марковской цепи n-го порядка”. “А ведь у меня ещё нет такого генератора!” - прокричал мой внутренний голос - “Скорей открывай sublime и пиши!” - продолжал он настойчиво. Что же, пришлось подчиниться.

А здесь я расскажу, как я его сделал.

Сразу было решено, что генератор будет все свои мысли излагать в Твиттер и свой сайт. В качестве основных технологий я выбрал Flask и PostgreSQL. Связываться друг с другом они будут через SQLAlchemy.

Структура.

И так. Следующим образом выглядят модели:
class Srt(db.Model): id = db.Column(db.Integer, primary_key = True) set_of_words = db.Column(db.Text()) list_of_words = db.Column(db.Text()) class UpperWords(db.Model): word = db.Column(db.String(40), index = True, primary_key = True, unique = True) def __repr__(self): return self.word class Phrases(db.Model): id = db.Column(db.Integer, primary_key = True) created = db.Column(db.DateTime, default=datetime.datetime.now) phrase = db.Column(db.String(140), index = True) def __repr__(self): return str(self.phrase)
В качестве исходных текстов решено было взять субтитры из популярных сериалов. Класс Srt хранит упорядоченный набор всех слов из переработанных субтитров к одному эпизоду и уникальный набор этих же самых слов(без повторений). Так боту проще будет искать фразу в конкретных субтитрах. Сначала он проверит, содержится ли множество слов в множестве слов субтитров, а затем посмотрит, лежат ли они там в нужном порядке.

Первым словом фразы из текста выбирается случайное слово, начинающееся с большой буквы. Для хранения таких слов и служит UpperWords. Слова туда записываются так же без повторений.

Ну и класс Phrases нужен для хранения уже сгенерированных твитов.
Структура отчаянно простая.

Парсер субтитров формата.srt выведен в отдельный модуль add_srt.py. Там нет ничего экстраординарного, но если кому интересно, все исходники есть на GitHub .

Генератор.

Для начала нужно выбрать первое слово для твита. Как говорилось раньше, это будет любое слово из модели UpperWords. Его выбор реализован в функции:
def add_word(word_list, n): if not word_list: word = db.session.query(models.UpperWords).order_by(func.random()).first().word #postgre elif len(word_list) <= n: word = get_word(word_list, len(word_list)) else: word = get_word(word_list, n) if word: word_list.append(word) return True else: return False
Выбор этого слова реализуется непосредственно строкой:

Word = db.session.query(models.UpperWords).order_by(func.random()).first().word

Если Вы используете MySQL, то нужно использовать func.rand() вместо func.random(). Это единственное отличие в данной реализации, всё остальное будет работать полностью идентично.

Если первое слово уже есть, функция смотрит на длину цепи, и в зависимости от этого выбирает с каким количеством слов в тексте нужно сравнить наш список(цепь n-го порядка) и получить следующее слово.

А следующее слово мы получаем в функции get_word:
def get_word(word_list, n): queries = models.Srt.query.all() query_list = list() for query in queries: if set(word_list) <= set(query.set_of_words.split()): query_list.append(query.list_of_words.split()) if query_list: text = list() for lst in query_list: text.extend(lst) indexies = ) if text == word_list] word = text return word else: return False
Первым делом скрипт пробегает по всем загруженным субтитрам и проверяет, входит ли наше множество слов в множество слов конкретных субтитров. Затем тексты отсеянных субтитров складываются в один список и в нём ищутся совпадения фраз целиком и возвращаются позиции слов, следующими за этими фразами. Всё заканчивается слепым выбором(random) слова. Всё как в жизни.
Так добавляются слова в список. Сам же твит собирается в функции:
def get_twit(): word_list = list() n = N while len(" ".join(word_list))<140: if not add_word(word_list, n): break if len(" ".join(word_list))>140: word_list.pop() break while word_list[-1][-1] not in ".?!": word_list.pop() return " ".join(word_list)
Всё очень просто – необходимо, чтобы твит не превышал 140 символов и заканчивался завершающим предложение знаком препинания. Всё. Генератор выполнил свою работу.

Отображение на сайте.

Отображением на сайте занимается модуль views.py.
@app.route("/") def index(): return render_template("main/index.html")
Просто отображает шаблон. Все твиты будут подтягиваться из него при помощи js.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("difference")) limit = 20 phrases = models.Phrases.query.order_by(-models.Phrases.id).all() pages = math.ceil(len(phrases)/float(limit)) count = len(phrases) phrases = phrases return json.dumps({"phrases":phrases, "pages":pages, "count":count}, cls=controllers.AlchemyEncoder)
Возвращает твиты определённой страницы. Это нужно для бесконечного скрола. Всё довольно обыденно. diff – количество твитов, добавленных после загрузки сайта при апдейте. На это количество нужно смещать выборку твитов для страницы.

И непосредственно сам апдейт:
@app.route("/update") def update(): last_count = int(request.args.get("count")) phrases = models.Phrases.query.order_by(-models.Phrases.id).all() count = len(phrases) if count > last_count: phrases = phrases[:count-last_count] return json.dumps({"phrases":phrases, "count":count}, cls=controllers.AlchemyEncoder) else: return json.dumps({"count":count})
На клиентской стороне он вызывается каждые n секунд и догружает в реальном времени вновь добавленные твиты. Так работает отображение нашего твита. (Если кому-то интересно, то можно посмотреть класс AlchemyEncoder в controllers.py, с его помощью производится сериализация твитов, полученных от SQLAlchemy)

Добавление твитов в базу и постинг в Твиттер.

Для постинга в Твиттер я использовал tweepy. Очень удобная батарейка, заводится сразу.

Как это выглядит:
def twit(): phrase = get_twit() twited = models.Phrases(phrase=phrase) db.session.add(twited) db.session.commit() auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET) auth.set_access_token(ACCESS_TOKEN, ACCESS_TOKEN_SECRET) api = tweepy.API(auth) api.update_status(status=phrase)
Вызов этой функции я вынес в cron.py в корне проекта, и, как можно догадаться, оно запускается по крону. Каждые полчаса добавляется новый твит в базу и Твиттер.

Всё заработало!

В заключение.

В данный момент я подгрузил все субтитры для сериала “Друзья” и “Теория большого взрыва”. Степень марковской цепи пока что выбрал равной двум(при увеличении базы субтитров степень будет увеличиваться). Как это работает можно посмотреть в

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

Теория

Цепи Маркова — это вероятности получения события на основе предыдущего события.

Да, знаю, туманное определение. Но, положим у нас есть игральная кость, одна грань которой тяжелее, чем остальные. Ясно, что эта грань будет падать вниз — чаще, от чего ее шанс выпадения будет мал, по сравнению с другими гранями. Цепь Маркова, в применении к кости, будет выглядеть как таблица с … например последними 10 бросками кости и их результатами. Глядя на эту таблицу мы можем примерно предсказать, какой результат будет у следующей серии бросков. Именно такое предсказание и есть результатом работы цепи, она с определенным шансом сообщает нам результат события, которое еще не случилось.

В применении к тексту это выглядит следующим образом. Возьмем поговорку:

Свобода не в том, чтоб не сдерживать себя, а в том, чтоб владеть собой.

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

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

Пишем генератор Маркова

Все что требуется — это получить массив-таблицу, приведенную выше. Ну, а далее собрать из нее некий текст.

Чтобы это сделать надо:

Очистить текст от мусора
Разбить его по пробелам в одномерный массив.
В цикле сгенерировать таблицу
В цикле собрать из таблицы текст

Собственно, чистка и составление таблицы выглядят так:

$data = file_get_contents("tz.txt"); // тут исходный текст mb_internal_encoding("UTF-8"); // знаки препинания воспринимаем как отдельные слова, то есть добавляем перед знаком пробел и после него тоже $data = preg_replace("~([,\:\-])~u"," \$1 ",$data); $data = preg_replace("~(\S+)[\s\r\n]*-[\s\r\n]*(\S+)~u"," \$1\$2 ",$data); // переносы объединяем $data = preg_replace("~[^a-zёа-я0-9 -!\?\.\,]~ui"," ",$data); // убираем лишнее, включая табы, скобки и прочее $data = mb_strtolower($data); // все в нижний регистр $words = explode(" ",$data); // разбиваем по пробелу $table = array(); // массив пар сочетаний foreach($words as $key=>$word){ if(isset($words[$key+1])){ $word = trim($word); $table[$word] = trim($words[$key+1]); // пара слово -> следующее слово $table[$word] = array_filter($table[$word],"strlen"); // убираем пустые $table[$word] = array_unique($table[$word]); // убираем дубли } else { /* если пар не найдено - пропускаем */ } }

Если посмотреть на результат работы этого кода, то мы увидим следующее:

Осталось все это немного подфильтровать и объединить в цикле.

Делается это, например, так:

$text = ""; // тут будет результат $prcount = 5; // кол-во предложений, которые надо сгенерировать $wcount = count($table); // число элементов в таблице $wkeys = array_keys($table); // ключи, то есть первые входные слова. Используется для генерации начал предложений. for($i=0; $i<$prcount; $i++){ $word = $wkeys; // первое слово с заглавной буквы $word = mb_convert_case($your_string, MB_CASE_TITLE, "UTF-8"); $predl = array(); $predl = $word; // массив слов будущего предложения $prlen = rand(5,15); // средняя длинна предложения от 6 до 16 слов(+1 слово, заглавное) while(mb_strpos($word,".") === false){ // пока не выпадет точка $subw = $table[$word]; $word = $subw; // если слово содержит точку и при этом кол-во слов в результате меньше, чем надо if(mb_strpos($word,".") !== false && count($predl) < $prlen){ // убираем точку $predl = trim($word,"."); }else $predl = $word; } $text .= implode(" ",$predl)." "; }

Результат будет таким:

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

Код генератора Маркова

text = $text; $this->pr_count = intval($pr_count); $this->prepare(); $this->generate(); } # Public // получение результата public function get_result(){ return $this->result; } # Private: // генерация private function generate(){ if(empty($this->table)) throw new Exception("Вызовите метод ->prepare перед генерацией!"); $word = ""; for($i=0; $i < $this->pr_count; $i++){ $word = $this->get_random_word($word,array("!",".","?")); // массив слов будущего предложения $predl = array(); $predl = $this->mb_ucfirst($word); // с заглавной буквы - первое слово $prlen = rand(5,15); // средняя длина предложения от 6 до 16 слов(+1 слово, заглавное) while(!$this->in_str($word,array("!",".","?"))){ // пока не выпадет точка $word = $this->get_random_word($word); // если слово содержит точку и при этом кол-во слов в результате меньше, чем надо if($this->in_str($word,array("!",".","?")) && count($predl) < $prlen){ // убираем точку $word = str_replace(array("!",".","?"),"",$word); } $predl = $word; } if(mb_strlen(end($predl)) < 4){ // если кол-во букв в последнем слове предложения меньше 4 array_pop($predl); // удаляем это слово $predl = "."; // и добавляем в конец точку } $this->result .= implode(" ",$predl)." "; } $this->result = preg_replace("~s([!?.,])s~u","1 ",$this->result); // убираем пробелы перед знаками препинания } // подготовка private function prepare(){ if($this->text == "") throw new Exception("Ваш текст пуст!"); $data = $this->text; //$data = preg_replace("~([,:-])~u"," $1 ",$data); // знаки препинания воспринимаем как отдельные слова, то есть добавляем перед знаком пробел и после него тоже $data = preg_replace("~(S+)s*+-+s*+(S+)~u"," $1$2 ",$data); // переносы объединяем $data = preg_replace("~[^a-zёа-я0-9 -!?.,]~ui"," ",$data); // убираем лишнее $data = preg_replace("~.+~ui",".",$data); // дубли точек и многоточия объединяем $words = explode(" ",$data); // разбиваем полученные данные по пробелу $table = array(); // строим массив пар сочетаний foreach($words as $key=>$word){ if(isset($words[$key+1])){ $word = trim($word); $word = $this->trimUpper($word, $words[$key-1]); $sword = $words[$key+1]; $sword = $this->trimUpper($sword, $word); $table[$word] = trim($sword); // пара слово -> следующее слово $table[$word] = array_filter($table[$word],"strlen"); // убираем пустые $table[$word] = array_unique($table[$word]); // убираем дубли /** * Если слово содержит за собой один из спецсимволов - убираем символ, после чего помещаем копию слова без символа в массив */ if($this->in_str($word,array("!",".","?"))){ $word = str_replace(array("!",".","?"),"",$word); $table[$word] = trim($sword); } } else { /* если пар не найдено - пропускаем */ } } $this->table = $table; } // проверяет есть ли символы из массива $items в строке $str private function in_str($str,$items = array(".")){ foreach($items as $item){ if(mb_strpos($str,$item) !== false) return true; } return false; } // мультибайтовый аналог ucfirst private function mb_ucfirst($value) { return mb_strtoupper(mb_substr($value, 0, 1)) . mb_substr($value, 1); } // убирает заглавные только в том случае, если в $previous есть знаки препинания private function trimUpper($word, $previous = null){ if(preg_match("~~",$word)){ /** * И если предыдущее слово отсутствует или содержит.!? знак, то мы опускаем его в нижний регистр т.к. это начало предложения. * Во всех остальных случаях очевидно, что заглавные буквы являются именами собственными, то есть именами людей, стран и прочего. */ if(!isset($previous) || $this->in_str($previous,array("!",".","?"))){ $word = mb_strtolower($word); } } return $word; } // генерирует уникальное случайное слово private function get_random_word($word = "", $ex = array()){ // получает случайное слово $nw = ""; if($word == ""){ $wkeys = array_keys($this->table); // ключи, то есть первые входные слова. Используется для генерации начал предложений. $nw = $wkeys; }else { $subw = $this->table[$word]; if(empty($subw)){ return $this->get_random_word("", $ex); } $nw = $subw; } /** * Рекурсивно исключаем дубли, слова с запрещенными символами($ex), а так-же просто пустые строчки */ if(!$nw || !empty($ex) && $this->in_str($nw,$ex) || $nw == $word){ return $this->get_random_word($nw, $ex); } return $nw; } }

Использовать так:

get_result(); echo "

".$text."

Демонстрация

Результат работы данного кода можно посмотреть .

В качестве исходника взят труд Ф. Энгельса «Крестьянская война в Германии», отсюда .

Итоговый текст выглядит так:

Тут, как вы видите, учитываются имена Собственные, есть знаки препинания(хоть и не все), да и в целом текст выглядит вполне … прилично. Я не постесняюсь заявить, что мой генератор текста по цепям Маркова — пока лучший из опубликованных в сети.

К стати, это не полноценная цепь Маркова т.к. тут не учитывается вероятность появления того или иного слова. Чтобы она учитывалась, надо убрать из кода эту строчку:

$table[$word] = array_unique($table[$word]); // убираем дубли

Если это сделать массив лексем будет выглядеть так:

Шанс выпадения дублированного слова выше, чем всех остальных. Это и есть цепь Маркова. Полноценная. Почему я не использую этот подход? Ответ прост: для большей уникальности исходного текста. Но вам, разумеется, никто не запрещает изменить код и использовать именно такую версию генератора ибо читабельность результата немного повышается.

Умеют ли поисковики детектить такой сгенерированный текст? Сложный вопрос. А вот пользователи — умеют, поэтому поведенческие у сайта с таким наполнением будут очень плохие (от чего трафика на нем не будет вообще). Я думаю, можно попробовать комбинировать читабельный копипаст и цепи Маркова, но лично экспериментировать с этим не хочу. Но вы — можете попробовать.

Доргенам — дорогу, хехе!

Исходники

Ну и, раз уж на то пошло, выложу исходники сюда и на гитхаб .