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

Question

给定一个数组 n 词频对：

[ (w0, f0), (w1, f1), ..., (wn-1, fn-1) ]

在哪里 w我 是一个词， f我 是一个整数频率，频率之和 ∑f我 = m,

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

P(w我 = wjk) = P(i = jk) = f我 / m

（注意，这是带有替换的选择，所以同一个单词 可以 每次都会选择）。

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

1. 创建一个大小的数组 m, ，并填充它，所以第一个 f0 条目是 w0, ， 下一个 f1 条目是 w1, ，依此类推，所以最后一个 fp-1 条目是 wp-1.

   [ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]

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

2. 单步遍历输入数组一次，计算

   m我 = ∑h≤ifH = mi-1 + f我

   并计算后 m我, ，使用pRNG生成一个数字 xk 在范围中 0...m我-1 对于每个 k 在 0...p-1并选择 w我 为了 wjk （可能替换当前值 wjk） 如果 xk < f我.
   这需要 O(n + np) 工作。

3. 计算 m我 如算法 2 所示，并在 n 个词频部分和三元组上生成以下数组：

   [ (w0, f0, m0), (w1, f1, m1), ..., (wn-1, fn-1, mn-1) ]

   然后，对于每个 k 0...p-1, ，使用pRNG生成一个数字 xk 在范围中 0...m-1 然后对三元组数组进行二分搜索以找到 i 英石。 m我-f我 ≤ xk < m我, ，然后选择 w我 为了 wjk.
   这需要 O(n + p log n) 工作。

我的问题是:我是否可以使用更有效的算法来实现此目的，或者这些算法是否已经达到最佳状态？

Answer 1

好吧，我找到了另一种算法： 别名方法 （还提到 在这个答案中）。基本上它创建了概率空间的划分，使得：

• 有 n 分区，全部宽度相同 r 英石。 nr = m.
• 每个分区包含一定比例的两个单词（与分区一起存储）。
• 对于每个单词 w我, f我 = ∑分区 t s.t w我 ε t r × ratio(t,w我)

由于所有分区的大小相同，因此可以通过不断的工作来选择哪个分区（从 0...n-1 随机），然后可以使用分区的比率来选择在恒定工作中使用哪个单词（将 pRNG 后的数字与两个单词之间的比率进行比较）。所以这意味着 p 选择可以在 O(p) 工作，给定这样的分区。

之所以存在这样的划分，是因为存在一个词 w我 英石。 f我 < r, ，当且仅当存在一个单词 w我' 英石。 f我' > r, ，因为 r 是频率的平均值。

给定这样一对 w我 和 w我' 我们可以用伪词替换它们 w'我 频率 f'我 = r （这代表 w我 有概率 f我/r 和 w我' 有概率 1 - f我/r）和一个新词 w'我' 调整频率 f'我' = f我' - (r - f我) 分别。所有单词的平均频率仍然是r，并且上一段的规则仍然适用。由于伪词的频率为r，并且由频率≠r的两个词组成，我们知道，如果我们迭代这个过程，我们永远不会从一个伪词中生成一个伪词，并且这样的迭代必须以a结束n 个伪字的序列，它们是所需的分区。

要构造此分区 O(n) 时间，

• 遍历单词列表一次，构建两个列表：
  • 频率 ≤ r 的单词之一
  • 频率 > r 的单词之一
• 然后从第一个列表中提取一个单词
  • 如果它的频率= r，则将其制成单元素分区
  • 否则，从另一个列表中提取一个单词，并用它来填充两个单词的分区。然后根据调整后的频率将第二个单词放回第一个或第二个列表中。

如果分区数量增加，这实际上仍然有效 q > n （你只需要以不同的方式证明它）。如果你想确保 r 是整数，并且你不能轻易找到一个因子 q 的 m 英石。 q > n, ，您可以将所有频率填充一个因子 n, ， 所以 f'我 = nf我, ，更新 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

Answer 2

这听起来像轮盘赌选择，主要用于遗传/进化算法中的选择过程。

看着 遗传算法中的轮盘选择

Answer 3

您可以创建目标数组，然后循环遍历单词，确定应该选择它的概率，并根据随机数替换数组中的单词。

对于第一个单词，概率为 f₀/米₀ （其中米_n=f₀+..+f_n）， IE。100%，因此目标数组中的所有位置都将填充 w₀.

对于以下单词，概率会下降，当到达最后一个单词时，目标数组将填充根据频率随机挑选的单词。

C# 中的示例代码：

public class WordFrequency {

    public string Word { get; private set; }
    public int Frequency { get; private set; }

    public WordFrequency(string word, int frequency) {
        Word = word;
        Frequency = frequency;
    }

}

WordFrequency[] words = new WordFrequency[] {
    new WordFrequency("Hero", 80),
    new WordFrequency("Monkey", 4),
    new WordFrequency("Shoe", 13),
    new WordFrequency("Highway", 3),
};

int p = 7;
string[] result = new string[p];
int sum = 0;
Random rnd = new Random();
foreach (WordFrequency wf in words) {
    sum += wf.Frequency;
    for (int i = 0; i < p; i++) {
        if (rnd.Next(sum) < wf.Frequency) {
            result[i] = wf.Word;
        }
    }
}