course.tr

.de MX
.sp 1.5
.mk tmp
.sp 0.5
.ta \\n(.luR
	\\$1
.sp |\\n[tmp]u-0.5v
.ce 1
..
.
.so .tmac.tmac
.
.so .titul.tr
.so .content.tr
.bp
.
.
.
.H2 Введение
.
.PP 2
Цепь Маркова \(em стохастическая модель, описывающая
последовательность возможных событий, при этом каждое
событие зависит только от предыдущего события.
.
.PP 0
Области использования марковских цепей:
.RS
.PI
Термодинамика,
.
.PI
Статическая механика,
.
.PI
Химия,
.
.PI
Информатика,
.
.PI
Статистика,
.
.PI
Генетика,
.
.PI
Экономика,
.
.PI
Системы распознавания речи,
.
.PI
Марковские текстовые генераторы.
.RE
.
.PP 1
Цель работы \(em разработать программу, генерирующую
случайный текст на основе исходного текста, с
использованием цепи Маркова.
.
.PP 0
Для достижения этой цели были поставлены следующие задачи:
.
.RS
.PI
Изучить соответствующую учебную и научную литературу;
.
.PI
Разработать библиотеку для работы с цепями Маркова;
.
.PI
Использовать эту библиотеку для написания программы,
генерирующую случайный текст.
.RE
.bp
.
.H2 1.\ Теория
.sp 1
.
.H3 1.1.\ Вступление
.sp 1
\fBСвязность графа\fP
.PP
Для ориентированного графа существование пути \(em
не симметричное отношение, поэтому вместо понятия связности
различают понятие слабой и сильной связности.[5]
.
.PP 0
Ориентированный граф называется сильно связным, если
в нём существует ориентированный путь из любой
вершины в любую другую, или, что эквивалентно, граф
содержит ровно одну сильно связную компоненту.
Пример сильно связного графа на Рис. 1.
.
.IM img/mc4.eps Сильно\ связный\ граф
.
.PP 1
Ориентированный граф называется слабо связным, если
является связным неориентированный граф, полученный
из него заменой ориентированных рёбер неориентированными.[3]
Пример слабо связного графа на Рис. 2.
.
.IM img/mc3.eps Слабо\ связный\ граф
.sp 1
.
\fBЭргодические марковские цепи\fP
.
.PP
Группы состояний марковской цепи (подмножества вершин
графа переходов), которым соответствуют тупиковые
вершины диаграммы порядка графа переходов, называются
эргодическими классами цепи.
.
.PP 0
Состояния, которые находятся в эргодических классах,
называются существенными, а остальные \(em несущественными.
Если эргодический класс состоит из одного состояния,
такое состояние является поглощающим.[4]
.
.PP 0
Рассмотрим Рис. 3, видно, что в нём 1 эргодический класс
(состоит из одного поглощающего состояния),
.
.EQ
M sub 1 = roman "{" E roman "},"
.EN
.
достижимый из части сильной связности, соответствующей
подмножеству вершин
.
.EQ
M sub 2 = roman "{" A, B, C, D roman "}."
.EN
.
.IM img/mc2.eps Цепь\ Маркова\ с\ поглощающим\ состоянием\ E
.
.PP
Конечная дискретная цепь определяется:
.RS
.PI
\fBМножеством состояний\fP
.
.EQ
S = roman "{" s sub {1}, s sub {2}, ..., s sub n roman "},"
.EN
.
событием является переход из одного состояние в другое
в результате случайного испытания.
.
.PI
\fBВектором начальных вероятностей (начальным распределением)\fP
.
.EQ
p sup 0 = roman "{" p sub 1 sup {0}, ..., p sub n sup 0 roman "},"
.EN
.
определяющим вероятности того, что в начальный момент времени
процесс находился в состоянии
.
.EQ
s sub n roman "."
.EN
.
.PI
\fBМатрицей переходных состояний\fP
.
.EQ
P = roman "{" p sub ij roman "},"
.EN
.
характеризующей вероятность перехода процесса с текущего
состояния в следующее. При этом сумма переходов из одного
состояния равна 1.
.RE
.
.PP 1
Любая цепь Маркова представляется в виде матрицы, где
строки матрицы\h'4p'\(em это текущее состояние, а столбцы \(em
следующее состояние.
.sp 1
.
.H3 1.2.\ Пример
.
.PP
Рассмотрим марковские цепи на примере изменения погоды.
Возьмём несколько состояний \fIS =\fP {дождь, солнце, облачно}
и составим марковскую цепь для этих состояний.
.
.IM img/mc1.eps "Пример цепи"
.
.PP
Данной цепи соответствует следующая матрица (1).
.
.MX (1)
.EQ
P sub 1 =
left (
~rpile {0.2 above 0.2 above 0.4}
~~rpile {0.7 above 0.6 above 0.4}
~~rpile {0.1 above 0.2 above 0.2}
~right )
.EN
.
.PP
Посчитаем матрицу переходов за два шага. Для этого возведём
матрицу (1) в квадрат (2).
.
.MX (2)
.EQ
P sub 2 ~~=~~
left (
~rpile {0.2 above 0.2 above 0.4}
~~rpile {0.7 above 0.6 above 0.4}
~~rpile {0.1 above 0.2 above 0.2}
~right )
~~\(mu~~
left (
~rpile {0.2 above 0.2 above 0.4}
~~rpile {0.7 above 0.6 above 0.4}
~~rpile {0.1 above 0.2 above 0.2}
~right )
~~=~~
left (
~rpile {0.22 above 0.24 above 0.24}
~~rpile {0.60 above 0.58 above 0.60}
~~rpile {0.18 above 0.18 above 0.16}
~right )
.EN
.
.PP 1
Допустим, что изначально на улице было облачно. Тогда
на следующий шаг вероятность солнечной или дождливой
погоды одинакова и равна 0.4. При этом если подождать
ещё один шаг, то вероятность солнечной погоды возрастает
до 0.6, а вероятность дождя уменьшается до 0.24.
.
.PP 0
Продолжаем возводить матрицу в степень \fIn\fP \(-> \(if
при этом получая матрицы переходов за \fIn\fP шагов.
.
.MX (3)
.EQ
P sub 3 ~~=~~
left (
~rpile {0.2 above 0.2 above 0.4}
~~rpile {0.7 above 0.6 above 0.4}
~~rpile {0.1 above 0.2 above 0.2}
~right )
~~\(mu~~
left (
~rpile {0.22 above 0.24 above 0.24}
~~rpile {0.60 above 0.58 above 0.60}
~~rpile {0.18 above 0.18 above 0.16}
~right )
~~=~~
left (
~rpile {0.236 above 0.236 above 0.232}
~~rpile {0.586 above 0.588 above 0.592}
~~rpile {0.178 above 0.176 above 0.176}
~right )
.EN
.
.MX (4)
.EQ
P sub 4 ~~=~~
left (
~rpile {0.22 above 0.24 above 0.24}
~~rpile {0.60 above 0.58 above 0.60}
~~rpile {0.18 above 0.18 above 0.16}
~right )
~~\(mu~~
left (
~rpile {0.22 above 0.24 above 0.24}
~~rpile {0.60 above 0.58 above 0.60}
~~rpile {0.18 above 0.18 above 0.16}
~right )
~~=~~
left (
~rpile {0.2356 above 0.2352 above 0.2352}
~~rpile {0.5880 above 0.5884 above 0.5880}
~~rpile {0.1764 above 0.1764 above 0.1768}
~right )
.EN
.bp
.
.PP
Видно, что при увеличении \fIn\fP столбцы
матрицы стремятся к одному числу.
То есть с течением времени система начинает
\(Foзабывать\(Fc исходное состояние. В данном примере
на состояние через четыре хода состояние в момент времени
\fIt\fP = 0 уже не имеет практически никакого значения.
.bp
.
.H2 2.\ Практика
.sp 1
.H3 2.1.\ Реализация\ библиотеки
.
.PP
Приступим к реализации библиотеки.
Для хранения данных используются следующие структуры:[1]
.sp 1
.
.fam C
  1 struct matrix {
  2     int maxj;
  3     double *pj;
  4 };
  5
  6 struct markov {
  7     int maxi;
  8     int maxel;
  9     struct matrix *mp;
 10 };
.fam T
.
.PP
На Рис. 5 приведён пример массива структур \fBmatrix\fP.
.
.IM img/matrix.eps "Пример массива структур matrix"
.
.PP
Структура \fBmatrix\fP используется для хранения матрицы переходов.
Структура \fBmarkov\fP хранит указатель на матрицу и необходимые
данные для работы с ней. Для \fBstruct markov\fP
применяется определение типа:
.sp 1
.
.fam C
 1 typedef struct markov *MARK;
.fam T
.
.PP
Также для работы с цепями
Маркова необходимы следующие функции:
.bp
.
.RS
.PI
\fBMARK minit(void)\fP
.
.PI
\fBvoid mfree(MARK p)\fP
.
.PI
\fBvoid mcount(MARK p, int ni, int nj)\fP
.
.PI
\fBvoid normalize(MARK p)\fP
.
.PI
\fBint getel(MARK p, int prewel)\fP
.RE
.
.PP
Код всех функций приведён в Приложении A.
Заголовочный файл приведён в Приложении B,
подраздел \(FoФайл markov.h\(Fc.
.
.PP
\fBMARK minit(void)\fP \(em
функция для инициализации структуры цепи. Возвращает
готовый элемент типа MARK.
.
.PP
\fBvoid mfree(MARK p)\fP \(em
функция для освобождения памяти.
.
.PP
\fBvoid mcount(MARK p, int ni, int nj)\fP \(em
принимает на вход инициализированную переменную типа MARK,
предыдущее и настоящее состояние системы. В функции
реализовано динамическое выделение памяти.
.
.PP
\fBvoid normalize(MARK p)\fP \(em
нормализация матрицы переходов
(приведение количества переходов к вероятностям).
.
.PP
\fBint getel(MARK p, int prewel)\fP \(em
получение номера элемента по предыдущему номеру.
.sp 2
.
.H3 2.2.\ Генератор\ текста
.
.PP
Для работы с текстом нам понадобятся ещё несколько
структур данных.
.sp 1
.
\fBХеш-таблица\fP
.
.PP
Хеш-таблица \(em это структура данных, реализующая
интерфейс ассоциативного массива, а именно, она позволяет
хранить пары (ключ, значение) и выполняет три операции:
добавление новой пары, поиск, удаление пары по ключу.[1]
.
.PP 0
Реализация хеш-таблицы представлена в приложении C.
Операция удаления не реализована за ненадобностью.
.
.PP 0
Простая хеш-таблица имеет фиксированный размер и для
добавления нового элемента вычисляется его хеш-сумма.
Результат хеш-суммы должен иметь значения в пределе от
0 до \fIn\fP - 1, где \fIn\fP \(em это размер массива.
Так как у двух разных элементов может быть одинаковая
хеш-сумма, могут возникать коллизии.
.
.PP 0
В представленной реализации используется хеш-сумма djb2.
И вычисляется так:
.sp 1
.fam C
 1 for (i = 0, hash = 5381; s[i] != '\\0'; ++i)
 2     hash += (hash << 5) + s[i];
.fam T
.
.PP
Код хеш-таблицы находится в Приложении C, заголовочный файл
в Приложении B, подраздел \(FoФайл hashtb.h\(Fc
.
.PP
Коллизии могут решаться несколькими способами:
.
.RS
.PI
Метод цепочек
.
.PI
Открытая адресация
.RE
.
.PP 1
Рассмотрим каждый метод подробнее.
.sp 1
.
\fBМетод цепочек\fP
.
.PP
На Рис. 6 показана схема хеш-таблица с односвязным
списком. В самой таблице
хранятся указатели на односвязный список.
В записи списка хранится идентификатор слова
(ключ), само слово (значение) и указатель на следующую
запись или NULL, если запись конечная.
.
.IM img/ht.eps "Хеш-таблица с односвязными списками"
.sp 1
.
\fBМетод открытой адресации\fP
.
.PP
На Рис. 7 показана хеш-таблица с открытой адресацией.
Будем считать, что строки добавлялись в таблицу в
следующем порядке: сначала строка s1, потом s3, потом s2.
.
.IM img/ht2.eps "Хеш-таблица с открытой адресацией"
.
.PP
Добавление происходит путём вычисления хеш-суммы ключа и
прохождения таблицы с индекса, равного хешу до тех пор, пока
не встретится пустая ячейка.
.
.PP 0
Алгоритм поиска просматривает ячейки хеш-таблицы в том же
порядке, что и при вставке, до тех пор, пока не встретится
ячейка с искомым ключом, либо пустая ячейка (что означает,
что элемент не найден).
.
.PP 0
Удаление элементов в такой схеме несколько затруднено.
Обычно поступают так: заводят булевый флаг для каждой
ячейки, помечающий, удален элемент в ней или нет. Тогда
удаление элемента состоит в установке этого флага для
соответствующей ячейки хеш-таблицы, но при этом необходимо
модифицировать процедуру поиска существующего элемента так,
чтобы она считала удалённые ячейки занятыми, а процедуру
добавления \(em чтобы она их считала свободными и сбрасывала
значение флага при добавлении. 
.sp 1
.
\fBСловарь\fP
.
.PP
Схема словаря показана на Рис. 8. По сути это просто
массив слов. При этом индекс массива \(em это ключ слова.
.
.IM img/dict.eps Словарь
.
.PP
С помощью словаря можно быстро найти слово по его индексу.
.sp 1
.
\fBГенрация текста\fP
.
.PP
Для начала необходимо определится с тем, что мы понимаем
под словом \(Foслово\(Fc. Слово \(em любое сочетание
буквенных символов и минус \(Fo-\(Fc, также словом являются
символы {,;?!}. Символы {'"[]{}(),:} игнорируются.
.PP 0
Теперь мы можем получать слова и назначать им уникальные
номера, которые используются для подсчёта переходов.
Когда все переходы подсчитаны, матрица нормализуется. Т.е.
сумма значений в строках должна стать равной 1.
После этого получаем номера слов, ищем их в словаре и
выводим их на экран.
.PP 0
Код программы находится в Приложении D и Приложении E.
.sp 1
.
\fBВывод программы\fP
.
.PP
Теперь попробуем сгенерировать текст из 10 слов. Для начала используем
небольшую выдержку из статьи на Википедии о Википедии на 262 слова.
.PP 0
Получившийся текст: \(FoВикипедия сейчас является символом эпохи
взаимодействия в ней может любой\(Fc.
.PP 0
Во второй попытке используем текст на 167873 слова.
.PP 0
Получившийся текст: \(Foочень точными математическими множества
таких возможностей было точного этого процесса\(Fc
.PP 0
Как можно заметить второй вариант оказался менее разборчив т.к.
с увеличением слов переходы от слова к слову начинают носить более
случайный характер. Далее будет рассказано как при необходимости
можно улучшить вывод программы.
.bp
.
.H2 Заключение
.
.PP
В данной работе были выполнены все поставленные задачи.
Была изучена литература, связанная с цепями Маркова, также
рассмотрена теория цепей Маркова. Была написана библиотека
для работы с цепями Маркова и программа для генерации
случайного текста.
.
.PP 0
В конце хотелось бы отметить некоторые возможности по
улучшению кода.
.PP 0
Как видно из примеров вывода программы, текст, полученный из
большого текста, получается бессмысленным. Чтобы улучшить
вывод, можно анализировать переходы не от слова к слову,
а от пары слов к паре слов и т.д.
.PP 0
Так же при каждом запуске программы, она заново анализирует
текст, что при большом тексте затрачивает много времени.
Для сокращения этого времени, сразу после нормализации
матрицы можно выводить необходимые данные в файл. А при старте
загружать их в обход парсера.
.RE
.bp
.
.so .books.tr
.bp
.so .appendixA.tr
.bp
.so .appendixB.tr
.bp
.so .appendixC.tr
.bp
.so .appendixD.tr
.bp
.so .appendixE.tr