10

给定一个n词频对数组：

[ (w 0 , f 0 ), (w 1 , f 1 ), ..., (w n-1 , f n-1 ) ]

其中是一个词，是一个整数频率，频率之和，wifi∑fi = m

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

P(w i = w j k ) = P(i = j k ) = f i / m

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

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

  1. 创建一个大小为 的数组m，并将其填充为第一个条目是，下一个条目是，依此类推，所以最后一个条目是。f0w0f1w1fp-1wp-1

    [ w 0 , ..., w 0 , w 1 ,..., w 1 , ..., w p-1 , ..., w p-1 ]
    然后使用 pRNG 选择prange 中的索引0...m-1，并报告存储在这些索引处的单词。
    这需要O(n + m + p)工作，这不是很好，因为m它可能比 n 大得多。

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

    m i = ∑ h≤i f h = m i-1 + f i
    在计算 之后，使用 pRNG为每个in生成一个范围内的数字， 并选择for （可能替换 的当前值） if 。 这需要工作。mixk0...mi-1k0...p-1wiwjkwjkxk < fi
    O(n + np)

  3. 按照算法 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 in ，使用 pRNG在范围内0...p-1生成一个数字，然后对三元组数组进行二进制搜索以找到st ，然后选择for 。 这需要工作。xk0...m-1imi-fi ≤ xk < miwiwjk
    O(n + p log n)

我的问题是：有没有更有效的算法可以用于此，或者这些算法是否尽可能好？

4

3 回答 3

6

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

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

于 2009-05-16T15:06:17.987 回答
2

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

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

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

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;
        }
    }
}
于 2009-05-16T15:54:48.103 回答
0

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

  • 有n分区，宽度都一样rst nr = m。
  • 每个分区包含一定比例的两个单词（与分区一起存储）。
  • 对于每个单词，wifi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

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

存在这种划分的原因是存在一个词st ，当且仅当存在一个词st时，因为 r 是频率的平均值。 wifi < rwi'fi' > r

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

为了及时构建这个分区O(n)，

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

如果分区的数量，这实际上仍然有效q > n（你只需要以不同的方式证明它）。如果您想确保 r 是整数，并且您不能轻易找到st的因子q，则可以将所有频率填充, so的因子，它会在 时更新和设置。mq > nnf'i = nfim' = mnr' = mq = 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
于 2009-05-16T22:10:18.920 回答