3

我构建了一个单词生成器，它会选择一个长度，然后随机选择字母表中的字母来组成单词。

该程序有效，但 99% 的输出是垃圾，因为它没有观察英语的结构，我得到的带有 x 和 z 的单词和我做的 e 一样多。

我有哪些选项可以让 RNG 更频繁地使用常用字母。

我正在使用随时间播种的 stl 中的 rand() 。

4

8 回答 8

5

输出仍然是垃圾，因为偏向随机数生成器不足以构建正确的英语单词。但是偏向 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 之间的任何数字都给你 ab，但只有 3500 给你一个 'q'。
于 2011-07-29T09:14:44.573 回答
2

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

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

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

于 2011-07-29T09:17:19.800 回答
1

您可以对某些文本进行n-gram分析，并将其用作偏差的基础。你可以通过字母或音节来做到这一点。按音节进行分析可能更复杂。

用字母来做，很容易。您遍历源文本中的每个字符并跟踪您遇到的最后 n-1 个字符。然后，对于每个下一个字符，将最后 n-1 个字符和这个新字符（一个 n-gram）添加到频率表中。

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

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

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

要从一组具有不同权重的值中选择随机值，您可以从设置累积频率表开始。然后你选择一个小于频率总和的随机数，看看它落在哪个区间。

例如：

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

您构建下表：{ A: 10, B: 17, C: 26 }。您选择一个介于 1 和 26 之间的数字。如果小于 10，则为 A；如果小于 10，则为 A。如果大于或等于 10，但小于 17，则为 B；如果大于 17，则为 C。

于 2011-07-29T09:43:42.127 回答
0

您可能希望使用英语的字母频率来获得更真实的输出：http ://en.wikipedia.org/wiki/Letter_frequency 。

但是，如果您想要可发音的单词，您可能应该从音节生成它们。您可以在线找到更多信息，例如：http: //spell.psychology.wustl.edu/SyllStructDistPhon/CVC.html

于 2011-07-29T09:08:47.683 回答
0

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

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

要生成加权随机生成器（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 之间的随机数，并用它来找到对应的字母。这样，您将拥有正确的字母频率。

于 2011-07-29T09:13:56.423 回答
0

您可以在阅读源文本时导出马尔可夫模型，然后生成与源“相似”的单词。

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

于 2011-07-29T09:32:14.603 回答
0

首先，您需要一个包含字母及其权重的表格，例如：

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 page on English Phonology提供了一些关于哪些组合可以在哪里出现的很好的信息，但它没有任何关于它们的统计数据。另一方面，如果你想编造可能的词，比如 Jabberwocky，那么这可能不是问题：选择随机数量的音节，从 1 到某个最大值，然后是开头、核心和结尾。（不要忘记开头和结尾可以是空的。）

于 2011-07-29T09:47:53.380 回答
0

如果您想创建可发音的单词，请不要尝试将字母连接在一起。

加入声音。列出声音以供选择：“abe”、“ape”、“gre”等

于 2011-07-29T11:21:10.143 回答