Алгоритм Маркова

DirtyWay, поищи в Инете... Там встречается довольно часто примеры реализации этого алгоритма на PHP...

Приблизительно так. Есть ряд (текст):

1 2 6 3 4 9 5 6 3 4 7 2 9 0 2 3 5

Берем первые два:

1 2 6 3 4 9 5 6 3 4 7 2 9 0 2 3 5

Окончание на 2. По ряду ищем 2 и берем за ней следующее:

1 2 6 3 4 9 5 6 3 4 7 2 9 0 2 3 5

Окончание на 9. Ищем 9 и берем следующее:

1 2 6 3 4 9 5 6 3 4 7 2 9 0 2 3 5

И т.п.

По примеру получилось:

1 2 9 5

Я в блоге у себя писал о цепях.

Ссылка: Цепь Маркова

Там и пример, и вменяемое описание, как реализовать суть.

Пример у меня, к сожалению, выдает ошибку и вываливается.

По описанию, честно, не смог понять алгоритм.

Хотелось бы увидеть функцию, например на PHP или VB .NET, в которую передавался бы некий текст и возвращался текст, перемешанный по Маркову.

Вот:

set_time_limit(0);

$intext = "A b. C d."; //Исходный текст

$words = explode(" ", $intext);

$nonword = $words[count($words)-1];

$w1 = $nonword;

foreach( $words as $word) {

$wordpairs[$w1][] = $word;

if (strpos($w1, ".") === strlen($w1)-1) $capitals[] = $w1;

$w1 = $word;

}

$maxgen = 100;  //Кол-во слов

$tt = array_rand($capitals);

$nonword = $capitals[$tt];

$w1 = $nonword;

$ret="";

for($i = 0; $i < $maxgen; $i++) {

$suf = $wordpairs[$w1];

$t = array_rand($suf);

$ret .= $suf[$t]." ";

$w1 = $suf[$t];

}

echo $ret;

Вот:

//Файл, в котором лежит исходный текст 

$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);

Источники соответственно:

http://thisishot.org/?page_id=17

http://netgen.com.ua/forums/topic.php?id=444

<?php 

	Class MarkovChains
	{
		var $prepared = array();
								
		function MarkovChains($source)
		{
			$source = strtolower($source);
  			$source = str_replace(array ("? ", "! "), ".", $source);
  			$source = str_replace(array (" -", "- ", "\t", "\r", "\n", "|",  "&", '\\', '/',  " :", " ;", "©", "·"), ' ', $source);
  			$source = str_replace(array (")", "(", "]", "[", "'", "\"", '*', '•', '~', '{', '}'), '', $source);
  			$source = str_replace(" ,", ",", $source);
  			$source = preg_replace("~(\s+\d{1,2}\s+)|(\w*\.\w+)~", " ", $source);
  			$source = preg_replace("~\s+~", " ", $source);
  				
			$sentens = explode('. ', $source); 
  			$count_sentens = count($sentens);
  			for ($j=0; $j<$count_sentens; ++$j)
  			{
    				$sentens[$j] = explode(' ', $sentens[$j]); 
    				$count_words = count($sentens[$j]) - 1;
    				for ($i=0; $i < $count_words; ++$i)
    				{
      					$prefix = $sentens[$j][$i];
      					$this->prepared[$prefix][] = $sentens[$j][$i+1];
    				}
  			}
  		
			$keys = array_keys($this->prepared);
  			foreach ($keys as $key)
  			{
    				$this->prepared[$key] = array_unique($this->prepared[$key]);
  			}
		}
			
		function GenerateText($size)
		{
			$result_count = 0;
  			for ($j=0; $result_count < $size; ++$j)
  			{
    				$prev = array_rand($this->prepared); 
    				$num  = mt_rand(5, 12); 
    				for ($i=0; $i<$num; ++$i)
    				{	
					$sents[$j][$i] = $prev;
      					++$result_count;
      					$p = $this->prepared[$prev][mt_rand(0, count($this->prepared[$prev]) - 1)];
      					if ($p == '') $p = array_rand($this->prepared);
      					$prev = $p;
      					if ($prev == '') break 2;
    				}
  			}
  	
			foreach ($sents as $sent)
  			{
    				$count_word=count($sent);
    				if ($count_word<=2) continue;
    				
    				if (strlen($sent[$count_word-1]) < 4) unset($sent[$count_word-1]);
    				
    				$sent[$count_word-2] = rtrim($sent[$count_word-2], ",:;");
    				$sent[$count_word-1] = rtrim($sent[$count_word-1], ",:;");
    				$output .= ucfirst(implode(' ', $sent)).'. ';
  			}
  	
			$output = str_replace(' .', '.', $output);
			
			return $output;
		}
	
	}

	
	//Example
	//$source = file_get_contents("text.txt");
	//$markov = new MarkovChains($source);
	//$result = $markov->GenerateText(500);
	//echo $result;
	
?>

Три скрипта - три разных подхода

Всем спасибо, попробую теперь разобраться )

Установи .net framework 3.5 - все заработает :)

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

На пальцах: стремясь подгадать и получить "правильный текст", марков берет слово, и ищет в исходном корпусе все встречающиеся слова, следующие [в этих текстах] за этим, первым словом (сорри, чета фигово слова складываются )). Таким образом исходные тексты выступают в роли обучалки. Чем этих текстов больше и чем разнообразнее пары слов, тем лучше будет текст на выходе.

Так вот, найдя все (или не все - в зависимости от конкретной реализации) "следующие" слова, марков берет по рандому (или не по рандому) одно из этих слов, и приплюсовывает его в исходный текст.

Допустим у нас выше было первым слово А, затем среди пар АБ, АГ И АД было выбрано АГ, т.е. слово Г. На выходе получили АГ. Далее марков берет эту Г, и ищет пары уже с ней: из ГД, ГЕ и ГЗ выбирает, скажем, ГЕ. Плюсует. Получается АГЕ. И так далее. Это вариант для двухсловной цепочки. Их можно делать длиннее, так будет более похоже на "правильный" текст, но, соотв., необходимо и обучающие тексты покруче.

Как-то так.

В теории все понятно, со скриптом тоже разобрался.

Всем большое спасибо!