Автор: Евгений Трофименко

В одном из постов ниже я выплескивал все свои гадкие мысли по поводу убийства дорвеев. Однако, есть класс дорвеев, который не убивается такими способами. Это дорвеи, генеренные с использованием цепей Маркова – они сохраняют грамматику оригинала (с пунктуацией, правда, проблемы, но ее отлавливать вряд ли возможно)

Что такое «цепи Маркова»?

Есть компьютерная игрушка – алгоритм, угадывающий мысли. Я тоже когда-то писал по нему программу :). Мысли человек формулирует в виде последовательности ноликов и единичек, введенных в компьютер. А компьютер отвечает или не отвечает так: после того, как ты задумал число, он пытается его угадать, а ты потом его вводишь. Обманывать компьютер нельзя, это нечестно! 🙂

Через некоторое время он начинает прилично угадывать. Даже удивительно. А алгоритм основан на том, что датчик случайных мыслей (цифирок :)) в человеке не случаен, а берет на вход предыдущие сгенеренные цифирки. И то, что следующим ходом человек сгенерит, определяется тем, какие цифры он сгенерил до того. И как ему компьютер отвечал (как вариант игры – он может угадывать втихую и не отвечать сразу, а отвечать потом).

Короче говоря, вся ситуация отслеживается на N ходов назад, и данные аккумулируются в таком виде: для каждой последовательности из N введенных ранее [0,1] считаем число введенных ПОСЛЕ этой последовательности единичек и число нулей. И считаем вероятность того, что человек введет следующим ходом. Если статистика по единичкам сильно больше, значит, «угадываем» единичку. Наоборот – ноль. Примерно одинаково – генерим случайно. А еще есть вариант игры с ответом «не знаю» в виде двойки, только тогда для эффективного угадывания данные накапливать дольше надо.

Вот такая простая скотина этот человек :). Сложным натурам можно на 3 хода назад отслеживать, простым – на 2.

Так вот цепи Маркова – это цепи событий. Они используются в жизни таких вариантах:

• когда надо посчитать некое стационарное состояние (распределение) при наличии ограниченного набора событий. Например, перескоки электронов по энергетическим уровням. Или перескоки юзера по матрице ссылок при расчете PageRank: http://www.yandex.ru/yandsearch?text=цепи маркова pagerank&stype=www
• Или когда надо предсказать поведение системы на основе ее нынешнего состояния. Тут используется понятно какая гипотеза – что развитие ситуации определяется тем, как она развивалась раньше на N ходов. Например, тот же текст может быть описан как последовательность и по ней выбрано слово, появление которого в тексте «следующим ходом» наиболее вероятно.

Так вот про текст и говорим. Слов, однако, гораздо больше, чем 2 (ноль и единица), поэтому эффективно угадать следующее слово не выйдет. А неэффективно, но грамматически связно – пожалуйста! Это и есть генерация по цепям Маркова.

***
Вот несколько ссылок по теме:

Про PageRank: http://www.mediacraft.ru/sections/articles/1/2.html
На форуме SeoChase: http://www.seochase.com/viewtopic.php?t=2149
Про генерацию текстов: http://predpinimatel-cd.com.ru/book/Programming/Praktical_programing/Glava3/Index2.htm (терминология там, правда, стремная)
***
Короче говоря, вероятности в случае генерации связного текста можно выбросить за ненадобностью… Алгоритм получается такой:
0) берем текст, разбиваем его по предложениям, а внутри каждого предложения выделяем последовательности из N (допустим, 2-х) слов и пишем в таблицу
1) Берем случайно одно из «первых» слов в предложении, и ставим эту пару как первую.
2) По второму слову в паре выбираем все те пары, в которых это слово идет первым и дополняем текст вторым словом
3) Идем к предыдущему пункту 2, не забывая иногда закрывать предложение (например, парами, которые встречаются в концах предложений)

Вот примерно так. Это дает грамматически связный текст в любых количествах. Для размножения можно использовать и вероятности появления той или иной последовательности, и увеличивать N, выбирая одно следующее слово по предыдущим N-1. И все цепочки слов (здесь: пары) встречаются в реальной жизни, а на пробивку по тройкам и N-кам слов никаких ресурсов у поисковика не хватит.

А как бороться с «дорвеями по цепям Маркова»?

А так, что основная цель дорвейщика – увеличить количество текста. И, взяв на вход 100-200 КБ (15-30 тыс. слов), получить на выходе огромную гору текста, разбитую по страницам.

Но свойство любого текста будет в том, что распределение тех же пар слов будет иметь длинный и тонкий хвост из редко (1 раз, например) используемых словосочетаний. Просто потому, что в русском языке слов – до фига. Даже словарный запас из 100 тыс. слов –больше, чем весь исходный для дорвейщика текст. И длина этого хвоста (ну, скажем, число пар, встречающихся в тексте 1 раз, поделенное на общее число пар) – будет измеряться в десятках процентов. А то и до 70-90%, чую, доходить будет. Ну это поверяется легко.

А поскольку лорвейщик текста нагенерил в 10-100 раз больше, чем был исходный текст, словосочетания там поюзаны многократно. Гораздо больше, чем 1 раз. Конечно, дорвейщик разбил текст по страницам, так что ловить надо в пределах сайта.

В принципе, даже ресурсов много не надо… Пробить по нескольким хорошим крупным сайтам свойства текстов. Прикинуть, например, сколько из 10 тыкнутых наугад пар слов встречаются на сайте более 1 раза. Допустим, 10-30%.

А у дорвейщика будет сильно больше 99%. Например, если дорвейщик из 100 Кб текста нагенерил 10 Мб, он каждое словосочетание использует где-то 100 раз. Ну и вероятность, что ты попадешь на уникальное в пределах сайта словосочетание – порядка 1%. А 99 будут неуникальных.

Ну и дальше сайт – ф топку. Т.е., звонок модератору.