Разработать программу-генератор текста на основе цепи Маркова.

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

Алгоритм частотного синтеза на уровне символов прост:

строка S =пустое слово
пока не достигнем строки заданной длины
  из таблицы символов выбираем символ C с вероятностью P(C)
  дописываем символ C к строке S

В результате образуется строка заданной длины, состоящая из символов.

Полученная строка, скорее всего, совершенно бессмысленна (и трудночитаема). Повысить читаемость можно, составляя текст из k-сочетаний, наиболее часто встречающихся в языке.

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

СТ, НО, ЕН, ТО, НА, ОВ, НИ, РА, ВО, КО
СТО, ЕНО, НОВ, ТОВ, ОВО, ОВА

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

Рассмотрим пример, основанный на цепи Маркова

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

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

Описание алгоритма:

поместить в W1 и W2 первые два слова
вывести W1 и W2
цикл:
  случайно выбрать W3 из набора суффиксов
  к префиксу W1 и W2
  заменить W1 и W2 на W2 и W3
  повторить цикл

В данной работе должны использоваться элементы стандартной библиотеки.

typedef deque<string> prefix;          // очередь префиксов
map<prefix, vector<string> > statetab; // префикс-суффиксы

В качестве параметров необходимо задать размер префикса (в словах) и объем генерируемого текста:

const int NPREF=2; // количество слов в префиксе
const int MAXGEN=1000; //объем текста на выходе

Процесс работы программы можно представить следующим образом:

• открывается входной файл на чтение
• файл читается по словам и в памяти создается таблица префиксов и суффиксов
• после обработки входного файла начинается процесс генерации выходного текста
• из таблицы берется первый префикс и случайно выбирается для него продолжение (в вифе суффикса)
• происходит переход на очередной префикс и для него снова выбирается суффикс
• генерация заканчивается либо при достижении заданного размера, либо при обработке последнего префикса

Пример генерации текста на основе текста ''Сказка о Золотой рыбке''

Жил старик со своею старухой У самого синего моря; 
Они жили в ветхой землянке Ровно тридцать лет и три года. 
Старик ловил неводом рыбу, Старуха пряла свою пряжу. 
Раз он в море синее просилась, Дорогою ценою откупалась: 
Откупалась чем только пожелаю Не посмел я взять с неё корыто, 
Наше-то совсем раскололось". Отвечает золотая рыбка: 
"Не печалься, ступай себе с богом". Воротился старик ко старухе, 
Что ж он видит? Высокий терем. На крыльце стоит его старуха 
В дорогой собольей душегрейке, Парчевая на маковке кичка, 
Жемчуги огрузили шею, На руках золотые перстни, На ногах красные сапожки. 
Перед нею усердные слуги; Она бьёт их, за чупрун таскает. 
Говорит старик своей старухе: "Здравствуй, барыня-сударыня дворянка! 
Чай, теперь твоя душенька довольна". На него прикрикнула старуха, 
На конюшне служить его послала. Вот неделя, другая проходит, 
Ещё пуще старуха бранится, Не даёт старику мне покою: 
Надобно ей новое корыто; Наше-то совсем раскололось". 
Отвечает золотая рыбка: "Не печалься, ступай себе с богом! 
Добро! будет старуха царицей!" Старичок к старухе воротился 
Глядь: опять перед ним землянка; На пороге сидит его старуха, 
А пред нею разбитое корыто. корыто. 

В данном проекте необходимо реализовать следующие тесты:

• формирование префикса из заданного числа слов
• формирование записи "префикс-суффикс"
• выбор единственного суффикса из вектора суффиксом (использование ПСЧ)
• выбор суффикса из вектора, содержащего несколько вариантом (ПСЧ)
• формирование текста заданной длины (на основе таблицы, заполненной вручную)

• include/textgen.h
• src/textgen.cpp
• src/main.cpp
• test/tests.cpp

1. Малинин Дмитрий Дмитриевич 19 ПМИ-2 b60
2. Бакланов Алексей Александрович 19 ПМИ-2 b61
3. Баринов Даниил Сергеевич 19 ПМИ-1 b62
4. Богомазов Михаил Васильевич 19 ПМИ-1 b63
5. Бугров Лев Валерьевич 19 ПМИ-1 b64
6. Бузанов Егор Андреевич 19 ПМИ-1 b65
7. Варлачёв Валерий Максимович 19 ПМИ-1 b66
8. Голованов Денис Максимович 19 ПМИ-1 b67
9. Дробот Елизавета Денисовна 19 ПМИ-1 b68
10. Жаравина Полина Дмитриевна 19 ПМИ-1 b69
11. Зайцев Тимур Олегович 19 ПМИ-1 b70
12. Кабанов Денис Сергеевич 19 ПМИ-1 b71
13. Канев Владислав Олегович 19 ПМИ-1 b72
14. Карцева Мария Дмитриевна 19 ПМИ-1 b73
15. Касьянов Никита Юрьевич 19 ПМИ-1 b74
16. Козлова Дарья Андреевна 19 ПМИ-1 b75
17. Кузнецов Михаил Дмитриевич 19 ПМИ-1 b76
18. Лавров Артём Романович 19 ПМИ-1 b77
19. Матвеев Андрей Сергеевич 19 ПМИ-1 b78
20. Машанова Карина Алексеевна 19 ПМИ-1 b79
21. Наумов Никита Александрович 19 ПМИ-1 b80
22. Нещеткин Глеб Максимович 19 ПМИ-1 b81
23. Пасманик Ирина Дмитриевна 19 ПМИ-1 b82
24. Рогозян Анастасия Тимофеевна 19 ПМИ-1 b83
25. Соболев Данил Александрович 19 ПМИ-1 b84
26. Софронов Валерий Александрович 19 ПМИ-1 b85
27. Трутнев Алексей Игоревич 19 ПМИ-1 b86
28. Тумаков Вадим Сергеевич 19 ПМИ-1 b87
29. Фролова Ольга Михайловна 19 ПМИ-1 b88
30. Шарибжанова Диана Рашидовна 19 ПМИ-1 b89
31. Щеникова Анна Юрьевна 19 ПМИ-1 b90
32. Андросов Вадим Дмитриевич 19 ПМИ-2 b91
33. Бирина Елизавета Сергеевна 19 ПМИ-2 b92
34. Булатов Дмитрий Александрович 19 ПМИ-2 b93
35. Демашов Никита Александрович 19 ПМИ-2 b94
36. Добряев Иван Александрович 19 ПМИ-2 b95
37. Дрожжачих Евгений Валерьевич 19 ПМИ-2 b96
38. Егорова Кристина Олеговна 19 ПМИ-2 b97
39. Загоскин Владислав Андреевич 19 ПМИ-2 b98
40. Зарубина Ирина Михайловна 19 ПМИ-2 b99
41. Иванов Даниил Андреевич 19 ПМИ-2 b100
42. Клыков Антон Романович 19 ПМИ-2 b101
43. Королев Денис Витальевич 19 ПМИ-2 b102
44. Краюшкина Екатерина Алексеевна 19 ПМИ-2 b103
45. Назаров Вячеслав Андреевич 19 ПМИ-2 b104
46. Оленев Дмитрий Сергеевич 19 ПМИ-2 b105
47. Панина Полина Сергеевна 19 ПМИ-2 b106
48. Прыгаев Денис Алексеевич 19 ПМИ-2 b107
49. Рогов Андрей Дмитриевич 19 ПМИ-2 b108
50. Симонова Арина Валерьевна 19 ПМИ-2 b109
51. Созинов Кирилл Игоревич 19 ПМИ-2 b110
52. Титова Нина Ивановна 19 ПМИ-2 b111
53. Уртюков Илья Алексеевич 19 ПМИ-2 b112
54. Хорев Егор Алексеевич 19 ПМИ-2 b113
55. Шабаршин Леонид Георгиевич 19 ПМИ-2 b114

Для выполнения работы необходимо:

1. Выполнить fork репозитария в свой аккаунт.
2. Выполнить клонирование репозитария из своего аккаунта к себе на локальную машину (git clone).
3. Создать ветку git с индивидуальным номером (git branch имя_ветки).
4. Сделать ветку активной (git checkout имя).
5. Необходимо разместить как исходные файлы с решениями задач, поместив cpp файлы в src, а заголовочные - в include.
6. Добавить файлы в хранилище (git add).
7. Выполнить фиксацию изменений (git commit -m "комментарий").
8. Отправить содержимое ветки в свой удаленный репозитарий (git push origin имя_ветки).
9. Создать пул-запрос в репозитарий группы и ждать результата от Travis-CI.