Данная работа опирается на ряд понятий из теории вероятностей. Подробное описание и полноценные определения этих понятий рассматриваются в соответствующих курсах по теории вероятностей. Здесь же предполагается, что достаточно интуитивного понимания концепции случайного события и его вероятности.
Случайная величина — величина, принятие которой конкретного значения является случайным событием.
Случайный процесс — последовательность случайных величин, заданная как функция времени. Время может быть дискретным (дискретный случайный процесс) или непрерывным (непрерывный случайный процесс). Реализацию случайного процесса можно рассматривать как сигнал.
Для моделирования случайных величин и процессов используются генераторы истинно случайных и псевдослучайных чисел (ГСЧ: ГИСЧ или ГПСЧ). Стандартная библиотека C++ определяет ряд средств (включая ГСЧ) в заголовочном файле <random>.
Дискретная случайная величина — случайная величина, множество возможных значений которой X не более чем счётно, т.е. изоморфно некоторому подмножеству натуральных чисел.
Дискретное вероятностное распределение — некая функция p: X → [0, 1] такая, что p(x) есть вероятность, с которой дискретная случайная величина, имеющая это распределение, равна x. Свойство: Σx∈X p(x) = 1.
Случайные величины используются для моделирования процессов, на которые оказывают существенное влияние неизвестные факторы. Например, мы можем моделировать работу некоего автомата, принцип действия которого нам неизвестен (чёрный ящик), считая, что этот автомат совершает случайные действия.
Стохастический автомат — автомат (например, конечный), функция состояния которого зависит от некоторой случайной величины.
Таким образом, динамика стохастического автомата является случайным процессом и для её анализа следует применять методы теории вероятностей.
Марковский процесс — случайный процесс, состояние которого в любой момент времени не зависит от истории. Таким образом, в случае дискретного по времени процесса следующее состояние является случайной величиной, вероятностное распределение которой определяется только текущим состоянием.
Если динамика стохастического автомата является дискретным марковским процессом, то переход из одного состояния в другое определяется как случайное событие, а новое состояние — как случайная величина с дискретным вероятностным распределением, зависящим только от текущего состояния.
Предположим, что автомат конечен, т.е. конечно его множество состояний Z. Так как вероятность перехода зависит от текущего состояния z, то у нас есть семейство функций pz: Z → [0, 1], задающих распределения новых состояний для всех исходных состояний z.
В простейшем случае мы можем задать |Z|×|Z|-матрицу P = (pij) такую, что если текущее состояние есть i, то элемент pij есть вероятность перехода в состояние j. Матрица P тогда называется переходной матрицей. Свойства: для всех i и всех j элемент pij ∈ [0, 1]; для всех i Σj pij = 1.
Пусть x ∈ X = { 0, 1, 2, …, n–1 } — случайная величина. Её вероятностное распределение можно задать массивом вероятностей pi, где 0 ≤ i < n.
Естественный вопрос: как моделировать x?
Предположим, что есть функция random(), возвращающая число из [0, 1). Тогда алгоритм вычисления x методом “вычерпывания” можно записать в виде (псевдо)кода:
// Некий ГСЧ с равномерным распределением в [0, 1).
float random();
size_t x(vector<float> const & p)
{
float v = random();
size_t const n = p.size();
for (size_t r = 0; r < n; ++r)
{
v -= p[r];
if (v <= 0)
return r;
}
assert(!"Ошибка или в p[i] или в random!");
return -1;
}Более вычислительно эффективный метод заключается в предварительном вычислении накопленных сумм p и выполнении среди них двоичного поиска результата random().
Моделирование марковского процесса сводится к переменной состояния, переключающей строки переходной матрицы и циклу:
void print_markov_chain(
size_t steps, // количество шагов
size_t from, // начальное состояние
vector<vector<float>> const & P // переходная матрица
)
{
cout << from << '\n';
while (steps-- != 0)
{
from = x(P[from]);
cout << from << '\n';
}
}
Рассмотрим язык, содержащий конечное число слов. Пронумеруем слова целыми числами от 0 до (n–1). Будем считать слово (или его номер) состоянием стохастического конечного автомата без входа. Динамика такого автомата является дискретным марковским процессом. В качестве переходной матрицы можно взять матрицу частот пар соответствующих номерам строки и столбца слов в некотором эталонном тексте.
Последовательность состояний такого автомата (переведённая в соответствующие слова) будет напоминать текст на языке эталонного текста. Естественно, этот текст, скорее всего, будет совершенно бессмысленным. Тем не менее, такие (и более сложные) модели используются на практике для генерации тестовых текстов в различных ситуациях: от научных изысканий и тестирования систем безопасности до игр.
Пример: “другой пускает пулю в голову и среди самой ранней молодости отчего у тебя не был о бы если вспомню”.
Написать программу “Бредогенератор”, которая работает следующим образом:
Данный нехитрый алгоритм de facto уже реализован в нижеприведённой заготовке исходного кода программы. В целях упрощения кода за её основу взята лабораторная работа №11. (Можно сделать аналог с поддержкой UTF-8 на основе лабораторной №12.)
Метками TODO помечены места для самостоятельного заполнения.
#include <cassert>
#include <cstdint>
#include <random>
#include <unordered_map>
#include <string>
#include <locale>
#include <fstream>
#include <iostream>
using namespace std;
// Представление кодировки Windows-1251
struct Windows_1251
{
// Считаем буквами также знаки - (дефис) и ' (апостроф).
// Возвращаемый этой функцией объект удалять нельзя.
static ctype_base::mask const* ctype_table()
{
static auto const
o = ctype_base::space,
l = ctype_base::alpha;
static ctype_base::mask const table[256]
{
// ASCII.
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, o, o, o, o, o, o, l, o, o, o, o, o, l, o, o,
o, o, o, o, o, o, o, o, o, o, o, o, o, o, o, o,
o, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, o, o, o, o, o,
o, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, o, o, o, o, o,
// Upper half.
l, l, o, l, o, o, o, o, o, o, l, o, l, l, l, l,
l, o, o, o, o, o, o, o, o, o, l, o, l, l, l, l,
o, l, l, l, o, l, o, o, l, o, l, o, o, o, o, l,
o, o, l, l, l, o, o, o, l, o, l, o, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
l, l, l, l, l, l, l, l, l, l, l, l, l, l, l, l,
};
return table;
}
// Отобразить большие буквы в маленькие.
static string& tolower(string & s)
{
for (auto &c: s)
{
unsigned char code = c;
if ((0x41 <= code && code < 0x5B) // ASCII
|| (0xC0 <= code && code < 0xE0))
c += 32;
else switch (code)
{
case 0x80: case 0x8A: case 0x8C:
case 0x8D: case 0x8E: case 0x8F:
case 0xA8: case 0xAA: case 0xAF:
c += 16; break;
case 0xA1: case 0xB2: case 0xBD:
++c; break;
case 0x81: c = '\x83'; break;
case 0xA3: c = '\xBC'; break;
case 0xA5: c = '\xB4'; break;
}
}
return s;
}
};
// Вызвать функцию visit для каждой пары подряд идущих слов
// в файле filename. Для каждого слова вызываем tolower.
// Возвращает false, если файл не удалось открыть.
template <class Encoding, class Visit>
bool for_each_word_pair(string const & filename, Visit visit)
{
// Возьмём локаль системы по умолчанию.
locale base_loc("");
// Создадим новую локаль, подставив фасет ctype с новой таблицей символов.
locale my_loc(base_loc, new ctype<char>(Encoding::ctype_table()));
// Откроем файл.
ifstream file(filename);
if (!file.is_open())
return false;
// Зададим локаль потоку ввода.
file.imbue(my_loc);
// Прочитаем слова и обработаем их попарно.
string first, second;
if (file >> first)
{
Encoding::tolower(first);
while (file >> second)
{
Encoding::tolower(second);
visit(first, second);
first.swap(second);
// Чем swap лучше, чем first = second?
// Лучше ли swap, чем first = move(second)?
}
}
return true;
}
// Вспомогательные типы:
// Счётчик пар.
using Int = int32_t;
// Отображение слово -> частота.
using Freqs = unordered_map<string, Int>;
// Отображение первое слово -> (второе слово -> частота).
using Words = unordered_map<string, Freqs>;
// Пример Words для исходного текста
// "Do the first, do the second, rinse and repeat.":
// {
// { "do", { { "the", 2 } } },
// { "the", { { "first", 1 }, { "second", 1 } },
// { "first", { { "do", 1 } },
// { "second", { { "rinse", 1 } },
// { "rinse", { { "and", 1 } },
// { "and", { { "repeat", 1 } } }
// }
// Считать из файла пары слов и определить их частоты.
template <class Encoding>
Words read_pairs(string const & filename)
{
Words words;
// TODO:
// использовать for_each_word_pair для заполнения words.
return words;
}
// Пример Freqs для предыдущего примера Words:
// {
// { "do", 2 },
// { "the", 2 },
// { "first", 1 },
// { "second", 1 },
// { "rinse", 1 },
// { "and", 1 }
// }
// Определить суммы частот всех вторых слов для каждого первого слова.
Freqs freq_totals(Words const & words)
{
Freqs totals;
// TODO:
// для каждого первого слова пары посчитать сумму счётчиков.
return totals;
}
// Один шаг марковского процесса.
template <class Rng>
string markov_step
(
Rng & rng, // целочисленный ГСЧ
Words const & words,
Freqs const & totals,
string const & from // исходное слово
)
{
auto totals_it = totals.find(from);
if (totals_it == totals.end())
return "";
// Алгоритм вычерпывания (целочисленный вариант).
// Сумма значений частот равна totals_it->second.
Int p = static_cast<Int>(rng() % (totals_it->second + 1));
for (auto kv: words.at(from))
{
p -= kv.second;
if (p <= 0)
return kv.first;
}
assert(!"Reached end in markov_step: impossible.");
return "";
}
///////////////////////////////////////////////////////////////////////////////
// Точка входа
#include <cstdlib>
int main()
{
// Visual C++ and Windows-specific code {
locale console_loc("Russian_Russia.1251");
locale::global(console_loc);
system("chcp 1251"); // иначе ввод русских букв может не работать.
// }
// Из файла input.txt прочитать эталонный текст
// и построить по нему таблицу частот пар слов.
auto words = read_pairs<Windows_1251>("input.txt");
assert(!words.empty());
cout << "Стартовых слов: " << words.size();
// Подсчитать суммарные частоты пар для каждого слова.
auto totals = freq_totals(words);
// Цикл запросов.
while (cin)
{
// Инициализация генератора псевдослучайных чисел.
uint64_t seed = 0;
cout << "\nЗерно ГПСЧ = ";
cin >> seed;
if (seed == 0)
seed = random_device{}();
mt19937_64 rng(seed);
// Количество слов в выводе.
int steps = 0;
cout << "Длина вывода (слов) = ";
cin >> steps;
// Начальное слово.
string word;
cout << "Начальное слово = ";
cin >> word;
// Цикл марковского процесса.
cout << '\n';
do
{
cout << word << ' ';
// TODO: вызвать markov_step.
} while (steps-- && !word.empty());
cout << endl;
}
return 0;
}
Для выполнения тестирования следует подготовить файл input.txt с каким-либо настоящим текстом (как можно большего объёма) в кодировке Windows-1251.
Кувшинов Д.Р. © 2018