Создание большого объема текста на основе цепи Маркова

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

 

Омский государственный  технический университет

 

Кафедра «Прикладная математика и фундаментальная информатика»

Специальность 010503 – «Математическое обеспечение и администрирование информационных систем»

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

на тему: __________________________________________________

_________________________________________________________

_________________________________________________________

 

по дисциплине _____________________________________________

 

Студент   Лейс Евгений Александрович    группы МО-310

 

 

Пояснительная записка

Шифр проекта (работы)____________________________

 

 

 

Руководитель проекта (работы)

А.Г. Купш        

___________________________

(Подпись, дата)

Разработал студент Е.А. Лейс

        ___________________________

(Подпись, дата)

Омск  2012

 

 

 

Кафедра________________________________________________________________________
Специальность_________________________________________________________________

Задание

на курсовое проектирование

по дисциплине ___________________________________________________________________

Студент ____________________________________________________ группа _____________

(Ф.И.О. полностью)

1. Тема проекта __________________________________________________________________

________________________________________________________________________________________________________________________________________________________________

2. Срок сдачи студентом законченного  проекта_______________________________________

3. Исходные данные к проекту  _____________________________________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

4. Содержание проекта (работы): ___________________________________________________

4.1. Разделы пояснительной записки  (перечень подлежащих разработке  вопросов) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

4.2. Перечень графического материала  (с указанием обязательных чертежей)___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

5. Основная рекомендуемая литература _____________________________________________

________________________________________________________________________________________________________________________________________________________________ 6. Дата выдачи задания ___________________________________________________________

 

Зав. кафедрой ___________________________________________________________________

(подпись, дата)

Руководитель ____________________________________________________________________

(подпись, дата)

 

Студент ________________________________________________________________________

(подпись, дата)

Реферат

Отчет  26с, 5 рис., 3 прил., 7 источника

ГЕНЕРАТОР ТЕКСТА, ДОРВЕЙ, ЦЕПЬ МАРКОВА, СПАМ, СННИПЕТ, ПОИСКОВАЯ СИСТЕМА

Данная работа посвящена разработке средств для массового порождения неестественных текстов. В работе предлагается теоретическая обобщенная модель текстов, порожденных с помощью цепей Маркова.

Цель работы – разработать приложение для создания большого объема текста на основе цепи Маркова .

В ходе работы было разработано приложение под Microsoft Windows в среде программирования  Python для генерации текста на основе цепей Маркова .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

Введение 5

Задание и исходные данные в соответсвии  с номером варианта………… 6

1) Обобщённая структурная схема системы связи для передачи дискретных сообщений …………………………………………………………………………….7

2) Расчёт  информационных характеристик источник .……………………..9

3) Построение  кода для сообщений источника……………………………..11

4) Статистические  характеристики закодированных сообщени……… ….13

5) Оптимальное по минимуму средней ошибки правило восстановления символа при приёме в условиях сильно зашумленного сигнала…………………15

6) Ошибки в передаче сообщений и вероятность правильного приема последовательности сообщений по слабо зашумленному сигналу………………17

Заключение…………………………………………………………………….19

Список использованных источников………………………………………… 20

Приложение А Код программы………………………………………………. 21

Приложение Б Входной текст…………………………………………………22

Приложение В Сгенерированный текст………………………………………23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

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

Отметим, что в настоящее время не существует полной теории,  описывающей законы порождения связных осмысленных текстов.  Как следствие отсутствуют в общем случае методы порождения текстов, не отличимых от созданных человеком. Тем не менее, известны многие закономерности, характерные естественным текстам:

- единство стиля;

- следование законом жанра;

- локальная связность;

- глобальная тематическая связность и т.п. 

Цепи Маркова позволяют  моделировать лишь локальную связность  текста и общие тематические характеристики. 

Основная  идея настоящей работы состоит в  том,  чтобы с учетом статистических характеристик стилистических и жанровых особенностей естественных текстов порождать неестественные тексты,  обладающие локальной связностью.

 

1 Методы порождения текстов

Создание  поискового спама сопряжено с  созданием большого количества текстов  для автоматического наполнения сайтов.  В настоящий момент существует несколько подходов к созданию текстов  для спам-сайтов:

-  Создание  текстов вручную; 

-  Копирование  текстов из других источников;

-  Автоматическая  генерация текстов; 

-  Автоматическая  модификация существующих текстов. 

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

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

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

 

2. Пораждение поискового спама с помощью цепей Маркова

Распространенным  видом генераторов текста являются генераторы текста на основе цепей  Маркова. 

Цепью Маркова  с дискретным временем называется последовательность случайных величин,  для которой  условное распределение каждой величины зависит только от значения предыдущих величин. Цепь Маркова описывается  множеством значений случайных величин,  которое называется пространством  состояний;  а также матрицей переходных вероятностей между состояниями. Матрица переходных состояний определяет вероятность перехода в следующее состояние, с учетом текущего. В случае если матрица переходных вероятностей не зависит от шага, она называется однородной,  именно однородные матрицы чаще всего применяются для порождения текстов.

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

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

 Во-вторых, порожденный текст является с высокой вероятностью уникальным. Это затрудняет обнаружение таких текстов методами обнаружения дубликатов.

Применение  автоматических генераторов текстов  на основе цепей Маркова часто  используется в таком виде спама  как дорвеи.  Функция дорвея перенаправить пользователя на некоторый целевой сайт, при этом само содержимое такого сайта никакой ценности для пользователя не несет.  Дорвеи должны попадать в выдачу по популярным запросам,  поэтому эффективное порождения такого вида спама может увеличить количество спама в выдаче поисковых систем.

Пусть k – порядок цепи Маркова, тогда  элемент матрицы переходов для  этого алгоритма не равен нулю, только если предыдущие k слов для двух состояний совпадают. Введем сходства на множестве состояний. Два состояния схожи по k предыдущим, если предыдущие k слов для этих двух состояний совпадают.

Очевидно, отношение сходства по k предыдущим состояниям является отношением эквивалентности и множество состояний разделяется на классы эквивалентности T₁^k ,..,T^k_Nk .

Обозначим P(T) - множество состояний, непосредственно предшествующих состояниям из множества T. Тогда вероятность перехода между состояниями может быть выражена через их классы эквивалентности:

;                                                 (1)

 

 

Пример:

для примера возьмем детский стишок:

 

Из-за леса, из-за гор 
едет дедушка Егор: 
сам на лошадке, 
жена на коровке, 
дети на телятках, 
внуки на козлятках.

 

Разберем  текст на звенья и связки:

 

из-за [леса, гор] 
леса [из-за] 
гор [едет] 
едет [дедушка] 
дедушка [Егор] 
Егор [сам] 
сам [на] 
на [лошадке, коровке, телятках, козлятках] 
лошадке [жена] 
жена [на] 
коровке [дети] 
дети [на] 
телятках [внуки] 
внуки [на]

 

Звенья  в этом списке представляют собой  уникальные слова из текста, а в  квадратных скобках перечислены  связи - список слов, которые могут  располагаться после этого слова.

При генерации  текста из списка звеньев на первой итерации выбирается случайное звено, определяются его связи, из списка связей выбирается случайная и прини -мается уже как новое звено. Затем действие повторяется до достижения нужного размера текста. В результате, например, может получиться что-то подобное: