Производство искусственного текста

dimcom

Сегодня окончательно решил, что мне вконец надоела vesna от Яndex, а потому необходимо что-то решать.
Задача
Создать генератор текста, работа которого издалека была бы похожа на совсем обычный текст. Весна все-таки грешит чересчур длинными словами, да еще там нет тире, дефисов и прочих тонкостей.
Шаг №1
Допустим, мы произвели статистический анализ, запомнили распределение. Теперь наш генератор выдает псевдотекст с правильным распределением букв. Почтовый декодер скажет, что все в порядке, однако это не так. Ошибки очевидны: после «а» запросто последует «ъ», а после «й» — какое-нибудь «,ы1».
Шаг №2
Что ж, в таком случае будем записывать в дополнение к вероятностям появления символа еще и вероятность перехода в другой символ. Получится, как нетрудно догадаться, квадратная таблица. Результат очевиден: в этом случае мы избавляемся от «аъ», «й:ыы» и другого мусора, ибо вероятность перехода «а» в «ъ» будет равна нулю, и генератор никогда не выдаст такого сочетания. Ошибки уже не так очевидны, но они есть. Все же, будут присутствовать предложения, начинающиеся со строчной буквы, два тире подряд, и другие казусы.
Шаг №3
Идем дальше, и записываем те же вероятности перехода, но для второго шага и далее. В этом случае после точки всегда пойдет пробел и далее — заглавная буква.
Вот здесь и появляется основная загадка: когда следует остановиться? На шаге, номер которого равен максимальной длине слова? Или на шаге, в котором ненулевые вероятности перехода только в знаки препинания?
Так что же нужно?
Буду рад любым советам по данной теме: алгоритмам, критике вышеизложенного, полезным ссылкам по теории. Сам учусь на 5-м курсе физического факультета, если это имеет значение. Алгоритм будет реализован в виде программы и выложен в интернет для свободного использования. Если получится, можно будет сделать и онлайн-версию.
P. S.: Читал когда-то, что некий товарищ (филолог) сделал на этом диссертацию. Таким способом он определял автора текста. Анализировал известные произведения, а потом сравнивал полученные матрицы переходов с матрицами для изучаемого. Потом делал вывод. Эх, филологи, халявщики.

Sanych

Интересно, а примеры работы какой-нибудь программы будут? И что предполагается в качестве сырья?
Можно попробовать разбивать ветку с наибольшей вероятностью, пока не получится нужное количество. Или, что в сущности то же самое, поставить предельную вероятность. Тогда можно будет, увеличивая пошагово длину, каждый раз запоминать уже маловероятные последовательности, и далее считать для оставшихся.
Добавлять произвольную букву надо со стороны, противоположной той, в которую будет строиться текст -- чтобы потом его по получившемуся набору действительно можно было строить. В какую сторону строить текст, кстати, хороший вопрос. Известно, что человеку надо знать, что он хочет получить. Может и компу тоже полезно
//
ветка это например
abcz
её вероятность -- это какая у неё доля встречаемости

dimcom

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

zuzaka

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

Anastasia85

Сравниватель текстов на авторство:
http://www.rusf.ru/cgi-bin/fr.cgi?get=input
Автор этой проги - Дмитрий Хмелев - весной у нас на факультете делал доклад про современные методы анализа текстов. Всякие там суффиксные деревья и массивы..
Весна яндекса хороша тем, что текст более-менее осмысляемый. Если же по вероятнестям генерить, то будет мешанина букв. Тут хорошо словари иметь и слова согласовывать уметь. Кстати, кроме весны были еще какие-то, вроде..

Anastasia85

Шаг №3
Идем дальше, и записываем те же вероятности перехода, но для второго шага и далее. В этом случае после точки всегда пойдет пробел и далее — заглавная буква.
Вот здесь и появляется основная загадка: когда следует остановиться? На шаге, номер которого равен максимальной длине слова? Или на шаге, в котором ненулевые вероятности перехода только в знаки препинания?

А размер таблицы прикинул? Тут уже надо переходить к деревьям, и то осторожно. Максимальная длина слова, хе-хе.. Никакой памяти не хватит.
Подобные оценки вероятностей символов в зависимости от цепочки предыдущих успользуются в методах сжатия, известных как контекстное моделирование или PPM (prediction by partial match). Почитай 4-ю главу вот здесь:
http://www.compression.ru/book/pdf/compression_methods_part1_2-4.pdf

natunchik

Типа а ты вообще в курсе как работает яндексовская шняжка? Если нет, поясняю. Есть некий набор темплейтов, в каждую позицию в которых вставляется одно из предефайнутых словосочетаний. Типа в какой-то книжке была генерилка речей для партийных выступлений, в которой каждое предложение состояло из пяти частей, и к каждой части было пять вариантов. Типа
Сегодня / В этот знаменательный день / В ситуации переходного периода /...
мы / члены партии / все советские люди / ..
собрались здесь чтобы / готовы / ...
рещительно осудить / поддержать / ...
ну и так далее.
ИМХО следует апгрейдить эту схему.
Потому что анализируя букоффки ты во-первых постоянно будешь получать бессмысленные буквосочетания (тоже прикольно, но не совсем то и во вторых на самом деле отдельные слова совершенно не будут коррелировать между собой. Потому что влияние предыдущих букв ослабевает экспоненциально, соответственно при генерации очередной буквы практически НЕ будут учитываться седьмая, восьмая, десятая буквы до. То есть ты не сможешь заставить ее хотя бы склонять прилагательные соответственно существительным. Вот.
И еще. AliceBOT изначально разрабатывалась как интерфейс для поисковой системы. Точнее даже как достаточно важная часть поисковой системы. Это я к тому, что если ты ставишь перед собой задачу получить прогу генерящую хуйню, то ничего круче проги генерящей хуйню ты не получишь =) При этом ты можешь пытаться маскировать хуйню под осмысленный текст, но, в силу отсутствия смысла, маскировка не может получиться хорошей. Поэтому ты бы лучше подумал над тем, как генерить _осмысленный_ (на самом деле) текст.
Да, предыдущий абзац, конечно же, не относится к авангардистским стихам и депрессивным сочинениям готических сучек. Их можно программно генерить в чудовищных количествах, причем отличия от "хьюман-мэйд" можно свести к минимуму. Можешь заняццо =)

avgustinka

Что-то похожее -- алгоритм сжатия PPM от Дмитрия Шкарина, если память не изменяет.

dimcom

Прикинул, а что тут такого? В русском языке 33 строчных буквы, 33 заглавных, далее:
. , ; : - — « » ( ) ! ?
ну и пробел с красной строкой, разумеется. Получаем 33 + 33 + 12 + 2 = 80. Для ровного счета делаем 100. Получаем, что для таблицы вероятностей на 1-м шаге нужно 10 000 чисел. Для последующих шагов — прибавляем еще по 10 000 на каждый шаг. Вот и выходит, что для 100 шагов нам нужно 1 000 000 чисел, что многовато, но вполне возможно при современных вычислительных мощностях.
Вообще, замечание про размер разумно. Я уже начинаю подходить к мысли, что в алгоритм следует, все же, заложить некоторые предположения относительно вида текста. Первое, конечно же, такое: после точки всегда идет пробел, а после этого пробела — всегда заглавная буква или следующий абзац. Можно даже считать, что «. » (точка-пробел) — один символ. Та же история с запятой. В общем, дело хитрое, есть над чем подумать.

zuzaka

> Для последующих шагов — прибавляем еще по 10 000 на каждый шаг
Умножаем, а не прибавляем.
Такие вещи, как заглавные и строчные буквы, естественно, должны анализироваться уже после генерации текста.

dimcom

А почему умножаем-то? Никак не пойму, чем второй переход принципиально отличается от первого. Почему при дальнейших шагах каждому символу нужно ставить в соответствие не строку, а целую матрицу?

zuzaka

aa - N^2 возможностей.
aaa - N^3
aaa..a - N^n
Вероятность перехода на третьем шаге уже не для элемента вектора, а для эл-та матрицы.

filippov2005

Интересная задачка
читателей прошу не оставлять тему без внимания, ибо вещь если получится, то получится весьма полезной
Можно поподробней? Что хочется сделать и почему это может получится полезным?
Пока я не понимаю, чем выход программы будет существенно отличаться от случайного набора слов? Случайный набор можно, наверно, получить так.
Берем тескт из 100 000 слов. Словом можно считать то, что заключено между пробелами. Сохраняем текст в массиве строк. Далее генерируем случайное число i из отрезка [1, 100 000] и выдаем слово, лежащее в i-ом элементе массива. Ставим после него пробел. И так нужное количество раз.
Хотя я вроде начинаю понимать в чем дело.
Как нетрудно заметить, двойные корреляции будут такими же как у первоначального текста. А вот с тройными дело обстоит хуже. Корреляции типа "***" будут такими же, а вот те в которых участвует пробел "* *" уже нет. Например, в тексте может ни разу не встретиться корреляция "я я", а в сгенеренном достаточно часто (Пример: "я люблю яблоки" => "люблю я яблоки люблю "). С другой стороны таких корреляций (с пробелом посередине) немного (33х33) и можно пытаться следить и за ними, что, конечно, на порядок усложнит алгоритм.
Рассуждения про корреляции мне напомнили одну игру на знание слов. В общих чертах: двое по очереди называют буквосочетания. Первым ходом называется одна буква. Каждым следующим ходом либо называется буквосочетание, отличающееся от предыдущего ровно на одну букву, либо делается запрос: "Скажи слово". При этом букву можно добавлять как с конца так и сначала.
Игрок проигрывает, если он либо очередным ходом назвал нарицательное существительное (далее "слово" либо не смог ответить на запрос (ответом на запрос должно быть слово с подстрокой равной последнему буквосочетанию либо получил ответ на свой запрос.
Например,
1-ый "р" 2-ой "юр" 1-ый "юре" 2-ой "пюре" 2-ой проиграл
1-ый "р" 2-ой "юр" 1-ый "юру" 2-ой "Скажи слово" 1-ый "Нет слова" 1-ый проиграл
1-ый "р" 2-ой "юр" 1-ый "юре" 2-ой "юрер" 1-ый: "Скажи слово" 2-ой "фюрер" 1-ый проиграл

Anastasia85

А почему умножаем-то? Никак не пойму, чем второй переход принципиально отличается от первого.

Вот именно, что не отличается. Первый раз 100 на 100 умножали, и второй раз умножай. И третий...
Я такую штуку реализовывал, когда писал свой архиватор с PPM (лучше рара оказался, на факультете еще никто лучше не сделал).
Фишка в том, что реально в текстах встречаются далеко не все комбинации. Вероятность встретить "ъъъ" в осмысленном тексте нулевая. Поэтому строишь дерево: в вершине символ и N указателей на возможные предшествующие символы. Можно еще экономней, но уже сложнее.
Почитай ту книжку, короче.

Vitaminka

на факультете еще никто лучше не сделал

уверен?

Anastasia85

Я сужу по результатам конкурса на спецкурсе "Методы сжатия данных":
В прошлом году я участвовал и был первым:
http://graphics.cs.msu.su/courses/mdc2003/
В этом не участвовал, но тот набор файлов, на которых в этом году сравнивали, мой сжимает лучше, чем лучший из участников:
http://graphics.cs.msu.su/courses/mdc2004/
Еще никто не превзошел.

Vitaminka

какой алгоритм использовал?

Anastasia85

Тут все описано кратко:
http://about.thedeemon.com/products/arh/
Оставить комментарий
Имя или ник:
Комментарий: