好的，我找到了另一个算法：别名方法提到）。基本上，它创建概率空间的分区，使得：
- 有
n
分区，所有分区都具有相同的宽度r
stnr = m
。 - 每个分区以一定比例包含两个单词（与分区一起存储）。
- 对于每个字，
wi``fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)
由于所有分区的大小相同，因此可以选择在恒定工作中进行分区（
0...n-1随机选择索引），然后使用分区的比率来选择在恒定工作中使用哪个字（比较pRNGed数）以及两个词之间的比率）。因此，这意味着
p只要有
O(p)这样的分区，选择就可以在工作中完成。
这样的分区中存在的原因是，存在一个字ST ，当且仅当存在一个字ST ，因为r是平均的频率。
wi``fi < r``wi'``fi' > r
给定这样的一对，我们可以分别用一个伪频率的单词（用概率和概率表示）和一个新的调整频率的单词代替它们。所有单词的平均频率仍将是r，并且上一段中的规则仍然适用。由于伪单词的频率为r，并且由频率为≠r的两个单词组成，因此我们知道，如果我们对此过程进行迭代，则永远不会从伪单词中生成伪单词，并且此类迭代必须以a结尾n个伪字序列，它们是所需的分区。
wi``wi'``w'i``f'i= r``wi``fi/r``wi'``1 - fi/r``w'i'``f'i' = fi' - (r - fi)
要及时构建此分区
O(n)，
- 遍历单词列表一次，构造两个列表：
- 频率≤r的单词之一
- 频率> r的单词之一
- 然后从第一个列表中拉一个字
- 如果它的频率= r，则使其成为一个元素分区
- 否则，请从另一个列表中拉出一个单词，并用它来填充两个单词的分区。然后根据调整后的频率将第二个单词放回第一或第二个列表中。
如果分区的数量仍然有效
q > n（您只需证明它不同）。如果你想确保r是不可或缺的，你可以随便找一个因素
q的
mST
q >n，你可以垫所有频率的因数
n，那么，哪些更新和设置时。
f'i = nfi``m' = mn``r' = m``q = n
无论如何，这种算法只能
O(n + p)起作用，我认为这是最佳的。
在红宝石中：
def weighted_sample_with_replacement(input, p) n = input.size m = input.inject(0) { |sum,(word,freq)| sum + freq } # find the words with frequency lesser and greater than average lessers, greaters = input.map do |word,freq| # pad the frequency so we can keep it integral # when subdivided [ word, freq*n ] end.partition do |word,adj_freq| adj_freq <= m end partitions = Array.new(n) do word, adj_freq = lessers.shift other_word = if adj_freq < m # use part of another word's frequency to pad # out the partition other_word, other_adj_freq = greaters.shift other_adj_freq -= (m - adj_freq) (other_adj_freq <= m ? lessers : greaters) << [ other_word, other_adj_freq ] other_word end [ word, other_word , adj_freq ] end (0...p).map do # pick a partition at random word, other_word, adj_freq = partitions[ rand(n) ] # select the first word in the partition with appropriate # probability if rand(m) < adj_freq word else other_word end endend
