1. 首页
  2. 问题
  3. 高效随机选择频率项目的算法
小编典典

高效随机选择频率项目的算法

algorithm

给定一个n词频对数组：

[（w 0，f 0），（w 1，f 1），...，（w n-1，f n-1）]

哪里是一个单词，是一个整数频率，频率之和，wi``fi``∑fi = m

我想使用伪随机数生成器（pRNG）选择p单词，以便选择任何单词的概率与其频率成正比：wj0, wj1, ..., wjp-1

P（w i = w j k）= P（i = j k）= f i / m

（注意，这是带有替换的选择，因此每次 都 可以选择相同的单词）。

到目前为止，我已经提出了三种算法：

  1. 创建一个size数组m，并填充它，使第一个条目为，下一个条目为，依此类推，最后一个条目为。f0``w0``f1``w1``fp-1``wp-1
    [w 0，...，w 0，w 1，...，w 1，...，w p-1，...，w p-1 ]

然后使用pRNG选择p范围内的索引0...m-1，并报告存储在这些索引处的单词。
这需要O(n + m + p)很大的工作量，因为m它可能比n大得多。

  1. 遍历输入数组一次，进行计算
    米我 =Σ h≤i ˚F ħ = M I-1 + F 我

和计算之后，使用PRNG以生成数的范围内对每个在 与选择用于（可能替换的当前值，如果）。
这需要工作。mi``xk``0...mi-1``k``0...p-1``wi``wjk``wjk``xk < fi
O(n + np)

  1. 按照算法2进行计算，并在n个词频部分和三元组上生成以下数组：mi
    [（w 0，f 0，m 0，，（w 1，f 1，m 1），...，（w n-1，f n-1，m n-1）]

然后，对于每个k 0...p-1，使用PRNG以生成数的范围内，然后做三元找到的阵列上的二进制搜索ST ，并选择对。
这需要工作。xk``0...m-1``i``mi-fi ≤ xk < mi``wi``wjk
O(n + p log n)

我的问题是 ：是否可以使用一种更有效的算法来解决这些问题？


阅读 275

收藏
2020-07-28

共1个答案

小编典典

好的，我找到了另一个算法：别名方法提到）。基本上，它创建概率空间的分区，使得：

  • 有n分区，所有分区都具有相同的宽度rst nr = 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
  end
end
2020-07-28