تم الاختراق من قبل دكتور سعودي511 Hacked by Dr.KsA511

Ноя

Алгоритмы генерации текста

by dr.ksa

На днях вместе с программистом разрабатывали новый дорген. Пришлось подумать над своим алгоритмом генерации текста. В этом посте я хочу рассказать какие существуют алгоритмы и как они определяются ПС.

Что такое генерация текста? Генерация текста это создание текста по определенному закону. Чем “человечнее” нужен текст тем сложнее алгоритм описывающий генерацию. Начнем с самых простых алгоритмов.

Алгоритм первый. Равновероятный. Если вероятность любой буквы алфавита (включая и пробел) примерно одинакова, то получим следующий текст:

пзятпедвярне поыйяьозпосиенапя моеывйоизчткн првждячашъ

Очевидно, что распознать что перед ним набор символов, а не текст поисковики могут. Значит этот алгоритм нам не подходит. Идем дальше.

Алгоритм второй. Частотно-вероятный. В любом реальном языке какие-то буквы встречаются чаще чем другие (например, в любом, достаточно большом тексте буква “О” будет составлять 11% от всех букв, а вот твердых знак всего лишь 0.03%). Учитывая это, а также что в среднем, в слове 8 букв, можно получить такие результаты:

аонлатраеа оноон илзаеок онаое тло енасопна онрвемду кяпоае

Уже что-то начинает вырисовываться, но все еще очень плохо.

Алгоритм третий. цепи Маркова. Этот алгоритм и его производные, являлся одним из самых популярных несколько лет назад. Но поисковые механизмы не стоят на месте Вкратце, алгоритм такой – если проанализировать текст, то увидим что вероятность сочетаний пар букв различается. Например, после буквы “о” с гораздой большей вероятностью следует “р” чем “м”. На практике использовались более сложные алгоритмы – исследовалась вероятность появления за данным словом другого слова или пары слов. На основе этих данных генерировался текст. Вот пример работы генератора над этим абзацем:

Назад но поисковые механизмы не стоят на практике использовались. Более сложные, алгоритмы исследовалась.

С тех пор как Яндекс научился достаточно хорошо понимать русскую морфологию использовать цепи Маркова в доргенах не имеет смысла.

Алгоритм четвертый. Генерация по паттерну. Давайте глянем в сторону программ проверки правильности написания (тот же SpellCeck в MS Word). Что же они делают? Они проверяют правильность расстановки запятых, точек и прочих знаков препинания, проверяют некие простые лингвистические правила. ПС безусловно все это умеют. Значит, что бы выдать генерированный текст за настоящий нам необходимо создавать его по определенным правилам. Так как, правил в русском языке в разы больше чем в английском, рационально использовать так называемый паттерн или шаблон. Рассмотрим простой пример предложения:

Солнце светит горячо и ярко

Если составить шаблон по членам предложения и частям речи, опустив предлоги и союзы, то получим:

$Подлежащие $сказуемое $обстоятельство1 и $обстоятельство2

$Существительное $глагол $наречие1 и $наречие2

Используя эти два шаблона можно легко сгенерировать сколько угодно предложений такой структуры. Разнообразив количество шаблонов, получаем отличный текст на выходе. Единственный и главный недостаток этого метода это согласование слов в предложении. В своем алгоритме я решил избавится от этого недостатка весьма изящным способом, о котором я расскажу в следующих постах.

Существуют и другие, более сложные алгоритмы, но использование их в доргенах не рационально из-за низкой скорости генерации.

Что еще почитать по теме:

Топик на Армаде
Википедия про цепи Маркова
Простенький генератор текста по шаблону

Enjoyed reading this post?
Subscribe to the RSS feed and have all new posts delivered straight to you.

17 Comments:

falkhan 7 Ноя, 2009

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

Откройте секрет – каким способом вы решили эту проблему?
Хитрый дорвейщик 7 Ноя, 2009

falkhan:

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

Откройте секрет – каким способом вы решили эту проблему?

Копайте в сторону phpmorphy
falkhan 7 Ноя, 2009

Хитрый дорвейщик:

falkhan:

> недостатка весьма изящным способом
Не осталось тут ни одного изящного способа, который реально бы справлялся со своей задачей.
Откройте секрет – каким способом вы решили эту проблему?

Копайте в сторону phpmorphy

Ну тогда это уж совсем не изящно )
horniest 9 Ноя, 2009

Боян боянистый.

Если в русском языке такая схема:

$Подлежащие $сказуемое $обстоятельство1 и $обстоятельство2

то можно эту схему поменять и будет все равно правильно.

Анализируем изходник «Солнце светит горячо и ярко»
Делаем перестановку «Солнце светит ярко и горячо » или «Горячо и ярко Солнце светит» и т.д. Все предложения правильные.

В англ. языке все проще. Есть только одна стандартная схема: подлежаще – сказуемое- второстепенные члены предложения. И никак иначе.

Для этого надо испольовать несколько баз текста для генерации, а именно:

- существительные
- прилагательные
- глагоды
- наречия
и т.д.

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

Тема применяется уже несколько лет. Цепь Маркова рулит
Хитрый дорвейщик 9 Ноя, 2009

horniest:

Если в русском языке такая схема:

$Подлежащие $сказуемое $обстоятельство1 и $обстоятельство2

то можно эту схему поменять и будет все равно правильно.

Анализируем изходник «Солнце светит горячо и ярко»
Делаем перестановку «Солнце светит ярко и горячо » или «Горячо и ярко Солнце светит» и т.д. Все предложения правильные.

В англ. языке все проще. Есть только одна стандартная схема: подлежаще – сказуемое- второстепенные члены предложения. И никак иначе.

Для этого надо испольовать несколько баз текста для генерации, а именно:

- существительные
- прилагательные
- глагоды
- наречия
и т.д.

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

Тема применяется уже несколько лет. Цепь Маркова рулит

Про это я и говорил в последнем пункте.

horniest:

Цепь Маркова рулит

Нет, не рулит. Скопируйте результат генерации в Word и проверьте ошибки. Мне он вывел:

Нет предлога перед существительным находящемся в предложном падеже.
Не хватает запятой после слова (тут слово)
Предлог не связан с существительным или местоимением.
Предложение несогласованно (!)

Если Word смог понять что предложение несогласованно (читать предложение – бред), то почему вы думаете что этого не сможет сделать Яндекс? Ну и соответственно принять меры по выкидыванию дора из индекса. Поэтому и нужен алгоритмы который будет генерить с учетом этого.
То что у вас попадает часть доров на Маркове в индекс вовсе не означает крутость данного алго.
robobee 10 Ноя, 2009

Но ведь в первую очередь анализируется не столько морфология сколько семантика. Самый простой способ это анализировать набор слов в тексте с матрицей вероятностей их нахождения в одном тексте/абзаце/предложении. Так вот Марков как раз эти вопросы решает, а предложенный алгоритм генерации грамматически правильного текста – нет.
Хитрый дорвейщик 10 Ноя, 2009

robobee:

Но ведь в первую очередь анализируется не столько морфология сколько семантика.

Важна и морфология, и семантика, и грамматика. Вообще, нужна полная иллюзия настоящего текста. Чтобы доры жили не по несколько апов, а месяцами.

robobee:

Так вот Марков как раз эти вопросы решает, а предложенный алгоритм генерации грамматически правильного текста – нет.

Я не утверждаю что данный алгоритм идеален, но то что он показывает лучшие результаты – это факт. Шесть тестовых дорвеев сделанных по более простому алгоритму (паттерн был один, согласование было не до конца отшлифовано), чем тот который я привел в пункте 4, как вылезли 27 августа, так до сих пор висят. Выводы делайте сами.
Автоматическая аддурилка для RedButton любой версии « Блог хитрого дорвейщика 10 Ноя, 2009

[...] Главная « Алгоритмы генерации текста [...]
Blizz 12 Ноя, 2009

robobee:

Но ведь в первую очередь анализируется не столько морфология сколько семантика. Самый простой способ это анализировать набор слов в тексте с матрицей вероятностей их нахождения в одном тексте/абзаце/предложении. Так вот Марков как раз эти вопросы решает, а предложенный алгоритм генерации грамматически правильного текста – нет.

А что мешает совместить 2 метода?
Вано 15 Ноя, 2009

Алгоритм четвертый.
$Подлежащие $сказуемое $обстоятельство1 и $обстоятельство2
.$Существительное $глагол $наречие1 и $наречие2

Здравствуйте,
Скажите пожалуйста, как это к баттону прикрутить?
Хитрый дорвейщик 16 Ноя, 2009

Вано:

Здравствуйте,
Скажите пожалуйста, как это к баттону прикрутить?

В файлике functions.php есть функция KarlMarks, которая отвечает за генерацию текста. Ее и нужно менять.
robobee 17 Ноя, 2009

Blizz:

А что мешает совместить 2 метода?

Думаю, что рабочий алгоритм в таком ключе создать будет очень сложно, если вообще возможно.
tol1k 19 Ноя, 2009

текст еще и немного смысловым можно сделать если создать тематическую выборку слов. Но чето не вериться что он будет жить месяцами
Хитрый дорвейщик 30 Ноя, 2009

robobee:

Думаю, что рабочий алгоритм в таком ключе создать будет очень сложно, если вообще возможно.

За n-ую сумму любой толковый программист накодит что угодно.

tol1k:

текст еще и немного смысловым можно сделать если создать тематическую выборку слов.

Ну то что текст должен быть тематическим это само собой разумеется.

tol1k:

Но чето не вериться что он будет жить месяцами

Я думаю вы знаете единственный способ проверить. Взять и сделать дор.
Кстати, введение алгоритма Снежинск ровным счетом ничего не изменило.
tol1k 1 Дек, 2009

если кому надо, нашел словари глаголов, существительных и т.д.
http://www.uinc.ru/forum/faqs/wordlist.shtml
Solo 19 Янв, 2010

Я думаю не стоит так резко отсекать цепи маркова. У меня они прекрасно живут, экспериментирую с длинной цепи. В вашем описании слова вставлялись текст по одному, в зависимости от предыдущего. У меня же один чаще вставляются по два, кроме того учитываются знаки препинания и хорошенько проработана вставка кеев, сильно не портящая морфологию. (кстати в вашей статье нислова о вставке кеев)
Alex 13 Авг, 2010

Прикольная идея генерации текста по мастеру Йода
вот тут обсуждают
http://forum.searchengines.ru/showthread.php?t=531116

Алгоритмы генерации текста

Что ищем?

Ссылки