Генератор текста на цепях Маркова

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

Теория

 

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

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

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

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

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

 

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

 

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

Более подробно можно почитать тут, если вы дружите с английским.

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

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

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

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

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

$data = file_get_contents("tz.txt"); // тут исходный текст

mb_internal_encoding("UTF-8");

// знаки препинания воспринимаем как отдельные слова, то есть добавляем перед знаком пробел и после него тоже
$data = preg_replace("~([,\:\-])~u"," \ ",$data); 
$data = preg_replace("~(\S+)[\s\r\n]*-[\s\r\n]*(\S+)~u"," \\ ",$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[array_rand($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[array_rand($subw)];
		
		// если слово содержит точку и при этом кол-во слов в результате меньше, чем надо
		if(mb_strpos($word,".") !== false && count($predl) < $prlen){
			// убираем точку
			$predl[] = trim($word,".");
		}else
			$predl[] = $word;
	}
	
	$text .= implode(" ",$predl)." ";
}

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

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

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

 

<?php
/**
 * Алгоритм Маркова для Кириллических текстов, учитывающий пунктуацию и имена собственные
 * минимально-допустимая версия php - 5.4, обязательно расширение mbstring
 * @author Александр Штокман
 * @year 2017
 */

namespace Generator;
 
class Markov{
	# Var
	private $table = array(); // массив лексем
	private $text = ""; // базовый текст
	private $pr_count = 15; // базовый текст
	
	public $result = ""; // результат
	
	
	/**
	 * Конструктор
	 * @var $text - исходный текст
	 * @var $pr_count - кол-во генерируемых предложений
	 */
    function __construct( $text, $pr_count = 15 ){
		mb_internal_encoding("UTF-8");
		
		$this->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*[rn]+-+s*[rn]+(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("~[A-ZА-Я]~",$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[array_rand($wkeys)];
		}else {
			$subw = $this->table[$word];
			if(empty($subw)){
				return $this->get_random_word("", $ex);
			}
			$nw = $subw[array_rand($subw)];
		}
		
		/**
		 * Рекурсивно исключаем дубли, слова с запрещенными символами($ex), а так-же просто пустые строчки
		 */
		if(!$nw || !empty($ex) && $this->in_str($nw,$ex) || $nw == $word){
			return $this->get_random_word($nw, $ex);
		}
		return $nw;
	}
}

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

<?php
/**
 * Генератор текста на цепях Маркова
 */
header('Content-Type: text/html; charset=utf-8'); 

require_once("class_markov.php");

$data = file_get_contents("tz.txt");

$mk = new Markov($data,15);
$text = $mk->get_result();

echo "<p style='word-wrap: break-word;'>".$text."</p>";

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

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

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

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

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

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

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

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

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

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

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

Исходники

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