Каков возможный способ смещения генератора случайных чисел?

Question

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

Программа работает, но 99% вывода - мусор, так как она не соблюдает конструкции английского языка, я получаю столько слов с x и z, сколько и e.

Какие у меня есть варианты смещения ГСЧ, чтобы он чаще использовал обычные буквы.

Я использую rand () из stl, посеянного со временем.

Answer 1

Вывод все равно будет мусором, потому что смещения генератора случайных чисел недостаточно для построения правильных английских слов. Но один из подходов к смещению rng:

1. Составьте гистограмму появления букв в большом английском тексте (корпус). Вы получите что-то вроде 500 'e', ​​3 'x', 1 'q', 450 'a', 200 'b' и т. Д.
2. Разделите интервал на диапазоны, где каждая буква получает срез, а длина среза - это число вхождений в интервале. a получает [0-450), b [450,650), ..., q [3500,3501).
3. Генерирует случайное число от 0 до общей длины интервала и проверяет, где оно находится. Любое число в пределах 450-650 дает вам b, но только 3500 дает вам 'q'.

Answer 2

Один из методов - использовать частоту букв.Для каждой буквы определите диапазон: a = [0, 2] (если буква «a» имеет 2% вероятности использования), b = [2, 5] (3% вероятности) и т. Д., Затем сгенерируйтеслучайное число от 0 до 100 и выберите букву.

Другой метод - использовать недетерминированные конечные автоматы, где вы можете определить определенные переходы (вы можете проанализировать библию и построить свою вероятность).Таким образом, у вас есть много таких переходов: например, переход от «a» к «b» составляет 5%.Затем вы проходите через автоматы и генерируете несколько слов.

Я только что увидел, что правильным термином является цепочка Маркова, которая, вероятно, лучше, чем NFA.

Answer 3

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

Сделать это буквально легко.Вы просматриваете каждый символ в исходном тексте и отслеживаете последние n-1 символов, с которыми вы столкнулись.Затем для каждого следующего символа вы добавляете последние n-1 символов и этот новый (n-грамм) в таблицу частот.

Как выглядит эта таблица частот?Вы можете использовать карту, отображающую n-граммы на их частоты.Но этот подход не очень хорош для алгоритма, который я предлагаю ниже.Для этого лучше сопоставить каждую (n-1) -грамму карте последней буквы n-грамма с ее частотой.Примерно так: std::map<std::string, std::map<char,int>>.

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

1. выбрать случайный начальный n-грамм.Ваш предыдущий анализ может содержать взвешенные данные, для которых буквы обычно начинаются с слов:
2. из всех n-граммов, начинающихся с предыдущих n-1 букв, выбрать случайную последнюю букву (с учетом весов из анализа);
3. повторять до тех пор, пока вы не достигнете конца слова (используя предварительно определенную длину или данные о конечных частотах слова);

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

Например:

• A происходит 10 раз;
• B происходит 7 раз;
• C происходит 9 раз;

Вы строите следующую таблицу: {A: 10, B: 17, C: 26}.Вы выбираете число от 1 до 26. Если оно меньше 10, это A;если оно больше или равно 10, но меньше 17, это B;если оно больше 17, это C.

Answer 4

Если вы хотите создать произносимые слова, не пытайтесь объединять буквы.

Присоединяйтесь к звукам.Составьте список звуков на выбор: «abe», «ape», «gre» и т. Д.

Answer 5

Во-первых, вам нужна таблица с буквами и их весами, что-то как:

struct WeightedLetter
{
    char letter;
    int  weight;
};

static WeightedLetter const letters[] =
{
    { 'a', 82 },
    { 'b', 15 },
    { 'c', 28 },
    //  ...
};

char getLetter()
{
    int totalWeight = 0;
    for ( WeightedLetter const* iter = begin( letters );
            iter != end( letters );
            ++ iter ) {
        totalWeight += iter->weight;
    }
    int choice = rand() % totalWeight;
                // but you probably want a better generator
    WeightedLetter const* result = begin( letters );
    while ( choice > result->weight ) {
        choice -= result->weight;
        ++ result;
    }
    return result->letter;
}

Это просто не в моей голове, поэтому, скорее всего, содержит ошибки; по крайней мере, второй цикл требует некоторой проверки. Но это должен дать вам основную идею.

Конечно, это все равно не приведет к английским словам. последовательность "uq" так же вероятна, как и "qu", и ничто не мешает слово без гласной или десятибуквенное слово только с гласными. Страница Wikipedia на Фонология английского языка содержит некоторую полезную информацию о том, какие комбинации могут происходить и где, но не имеет никакой статистики по ним. С другой стороны, если вы пытаетесь составить возможные слова, такие как Jabberwocky, тогда это может не быть проблемой: выберите случайное количество слогов от 1 до некоторого максимума, затем начало, ядро ​​и коду. (Не забывайте, что начало и код могут быть пустыми.)

Answer 6

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

Это также работает для генерации предложений из слов. Ну вроде работает.

Answer 7

Если вы хотите изменить только частоту букв в словах, без дальнейшего лексического анализа (например, пары qu), получите список частот букв английского языка.

Затем создайте взвешенный генератор случайных чисел, у которого будет больше шансов вывести e (шанс 1 в 7), чем x (около 1 на 1000).

Чтобы сгенерировать взвешенный генератор случайных чисел (rand генерирует целые числа, IIRC):
1. Нормируйте буквенные частоты, чтобы они были целыми числами (для частот Википедии в основном умножьте на 100000)
2. Создайте какую-нибудь таблицу поиска, где каждой букве вы назначаете определенный диапазон, как в таблице ниже

letter  | weight  |  start   |    end
a       |   8.17% |      0   |   8167
b       |   1.49% |   8168   |   9659
c       |   2.78% |   9660   |  12441
d       |   4.25% |  12442   |  16694
e       |  12.70% |  16695   |  29396
f       |   2.23% |  29397   |  31624
g       |   2.02% |  31625   |  33639
.....
z       |   0.07% | 99926    |  99999

3. Создайте случайное число от 0 до 99999 и используйте его, чтобы найти соответствующую букву. Таким образом, у вас будут правильные буквенные частоты.

Answer 8

Вы можете использовать частоту букв английского языка, чтобы получить более реалистичный вывод: http://en.wikipedia.org/wiki/Letter_frequency.

Но если вы хотите произносимые слова, вам, вероятно, следует генерировать их из слогов.Вы можете найти больше информации онлайн, например, здесь: http://spell.psychology.wustl.edu/SyllStructDistPhon/CVC.html