如���偏置一个随机数生成器？

Question

我建立了一个单词生成器，它选择长度并随机选择字母来组成单词。

程序虽然能够工作，但99%的输出都是垃圾，因为它没有遵守英语语言的结构规则，我得到了和e一样多的x和z单词。

我有什么选项来偏置RNG，使其更经常使用常用字母。

我正在使用从STL中种植的rand()和时间。

- Skeith

---

我感到有义务在这里提供一个链接：http://thedailywtf.com/Articles/The-Automated-Curse-Generator.aspx - R. Martinho Fernandes

@Martinho：没错，马尔可夫链是正确的选择！ - B. Decoster

哦，人们一直在建议使用马尔可夫链，并链接到维基百科上的文章。你读过那篇文章吗？我觉得它一点也不有用。 - R. Martinho Fernandes

Answer 1

输出仍然会是垃圾，因为调整随机数生成器的偏差并不足以构建正确的英语单词。但可以通过以下方法来调整随机数生成器的偏差：

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'。

- Björn Lindqvist

---

想法是让事物像宝可梦的名字一样，所以我想要稍微奇怪一点但还是有点可读性的东西。 - Skeith

+1 可能是偏置随机数生成器的最佳方式。然而，如果你想要看起来不错的单词，那么我建议使用马尔可夫链，就像 duedl0r 的答案中所述。 - Dan

Answer 2

一种方法是使用字母频率。为每个字母定义一个范围：a = [0, 2]（如果字母'a'有2％的使用几率），b = [2, 5]（3％的概率），以此类推... 然后生成0到100之间的随机数并选择一个字母。

另一种方法是使用非确定性有限自动机，其中可以定义某些转换（可以解析圣经并构建概率）。 因此，您有很多这样的转换：例如从'a'到'b'的转换为5％。 然后您可以通过有限自动机并生成一些单词。

我刚看到正确术语是马尔可夫链，这可能比NFA更好。

- duedl0r

Answer 3

你可以对某段文本进行n-gram分析，并将其用作偏差的基础。你可以按字母或音节来进行分析。按音节进行分析可能更加复杂。

按字母进行分析很容易。你可以遍历源文本中的每个字符，并跟踪你遇到的最后n-1个字符。然后，对于每个下一个字符，你将上次遇到的n-1个字符和这个新字符（一个n-gram）添加到频率表中。

这个频率表是什么样子的？你可以使用映射将n-grams映射到它们的频率。但是，这种方法对我下面建议的算法来说并不是很好。为此，最好将每个(n-1)-gram映射到一个映射，该映射将n-gram的最后一个字母映射到其频率。类似于：std::map<std::string, std::map<char,int>>。

进行分析并收集统计数据后，算法将如下所示：

选取一个随机的起始n-gram。您之前的分析可能包含有权数据，其中字母通常用于开始单词； 从以前的n-1个字母开头的所有n-gram中选择一个随机的最后一个字母（考虑分析中的权重）； 重复以上步骤，直到达到单词的结尾（可以使用预定义的长度或来自单词结束频率的数据）。

从具有不同权重的值集合中选择随机值，您可以首先设置一个累积频率表。然后，您选择一个小于频率总和的随机数字，并查看它在哪个区间内。

例如：

A发生了10次； B发生了7次； C发生了9次；

您建立以下表：{ A: 10, B: 17, C: 26 }。您选择1到26之间的数字。如果它小于10，它是A；如果它大于或等于10但小于17，则是B；如果它大于17，则是C。

- R. Martinho Fernandes

Answer 4

如果你想要更真实的输出，可以使用英语字母频率：http://en.wikipedia.org/wiki/Letter_frequency。

但是如果你想要可发音的单词，最好从音节中生成它们。你可以在网上找到更多信息，例如这里：http://spell.psychology.wustl.edu/SyllStructDistPhon/CVC.html

- slaphappy

---

一旦您拥有一个音节列表，您可以研究音节相对于彼此出现的频率，并在马尔可夫链生成器中使用统计数据！ - otto

问题是如何做到这一点。 - Skeith

Answer 5

你可以通过阅读源文本来推导出马尔可夫模型，然后生成与源文本“相似”的单词。

这也适用于从单词中生成句子。嗯，有点适用。

- spraff

Answer 6

如果你想创建可发音的单词，不要试图将字母拼在一起。

拼接音素。制作一个音素列表以供选择："abe"、"ape"、"gre"等。

- QuentinUK

Answer 7

如果您想仅更改单词中的字母频率，而不进行进一步的词汇分析（例如qu对），请获取英语语言字母频率列表。

然后创建一个加权随机生成器，它将更有可能输出e（7分之1的机会）而不是x（大约1000分之1的机会）。

要生成加权随机生成器（rand生成整数，如果我没记错）：
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之间的随机数，并使用它来找到相应的字母。这样，您将拥有正确的字母频率。

- SWeko

---

请阅读问题，它说的是如何制作你建议我使用的加权随机数生成器。 - Skeith

Answer 8

首先，您需要一个包含字母及其权重的表格，类似于以下内容：

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”一样可能出现，没有任何阻止没有元音的单词或只有元音的十个字母的单词。维基百科关于英语音系学有一些关于哪些组合可以在哪里发生的好信息，但它没有任何统计数据。另一方面，如果你正在尝试编造可能的单词，比如贾伯沃克，那么这可能不是一个问题：选择一个随机数量的音节，从1到某个最大值，然后是开端、核心和闭韵。(别忘了开端和闭韵可以为空。)

- James Kanze