Эффективный алгоритм для случайного выбора элементов с частотой

Question

Учитывая массив n пар слов частоты:

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

, где wi это слово, fi представляет собой целое число frequencey, а сумма частот ∑fi = m,

Я хочу использовать генератор псевдослучайных чисел (pRNG) для выбора p слов wj0, wj1, ..., wjp-1 таких, что вероятность выбора любого слова пропорциональна его частоте:

P(wi = wjk) = P(i = jk) = fi/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. Шаг через входной массив раз, вычислительной

   mi = ∑h≤ifh = mi-1 + fi

   и после вычисления mi, использовать PRNG, чтобы генерировать номер xk в диапазоне 0...mi-1 для каждого k в 0...p-1 и выберите wi для wjk (возможно заменить текущее значение wjk) если xk < fi.
   Для этого требуется O(n + np) работы.

3. Вычислить mi, как и в алгоритме 2, и генерировать следующий массив на п слово-частотной частичной суммы троек:

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

   , а затем, для каждого к в 0...p-1, использовать PRNG, чтобы генерировать номер xk в диапазоне 0...m-1 затем выполните двоичный поиск по массиву троек, чтобы найти i st mi-fi ≤ xk < mi, и выберите wi для wjk.
   Для работы требуется O(n + p log n).

Мой вопрос: Есть ли более эффективный алгоритм можно использовать для этого, или это так же хорошо, как он получает?

Answer 1

Хорошо, я нашел другой алгоритм: the alias method (также упоминается in this answer). В основном это создает раздел вероятностного пространства таким образом, что:

• Есть n перегородки, все те же ширины r S.T. nr = m.
• Каждая секция содержит два слова в некотором соотношении (которое хранится с разделом).
• для каждого слова wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Поскольку все перегородки имеют одинаковый размер, выбор, какой раздел может быть сделано в постоянной работе (выбрать индекс из 0...n-1 в случайном порядке), а соотношение перегородка может затем используется для выбора того, какое слово используется в постоянной работе (сравните число pRNGed с соотношением между двумя словами). Таким образом, это означает, что выбор p может быть выполнен в O(p) работе, учитывая такой раздел.

Причина, по которой существует такое разделение, состоит в том, что существует слово wi s.t. fi < r, если и только если существует слово wi' s.t. fi' > r, так как r - среднее значение частот.

Учитывая такую ​​пару wi и wi' мы можем заменить их псевдо-слова w'i частоты f'i = r (что представляет wi с вероятностью fi/r и wi' с вероятностью 1 - fi/r) и новое слово w'i' скорректированной частоты f'i' = fi' - (r - fi) соответственно. Средняя частота всех слов будет по-прежнему равна r, и правило от предыдущего абзаца все еще применяется. Так как псевдослое имеет частоту r и состоит из двух слов с частотой ≠ r, мы знаем, что если мы итерируем этот процесс, мы не будем делать псевдо-слово из псевдословного слова, и такая итерация должна заканчиваться последовательность n псевдослов, которые являются нужным разделом.

Для построения этого раздела в O(n) время

• пройти через список слов, однажды, строительство двух списков:
  • один из слов с частотой ≤ г
  • одним из слов с частота > r
• затем вытащить слово из первого лиза т
  • , если его частота = г, а затем сделать его в перегородке на один элемент
  • иначе, вытащить слово из другого списка, и использовать его для заполнения раздела двух слов. Затем верните второе слово в первый или второй список в соответствии с его скорректированной частотой.

Это на самом деле все еще работает, если количество разделов q > n (вы просто должны доказать это по-другому). Если вы хотите убедиться, что r является интегральным, и вы не можете легко найти коэффициент q из m s.t. 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 

Answer 2

Это звучит как выбор колесика рулетки, в основном используемый для процесса выбора в генетических/эволюционных алгоритмах.

Посмотрите на Roulette Selection in Genetic Algorithms

Answer 3

Вы можете создать целевой массив, а затем через цикл слов, определяющих вероятность того, что она должна быть определена, и заменить слова в массиве в соответствии с случайным числом.

Для первого слова вероятность того, будет F/м (где т _п = F + .. + F _п), т.е. 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; 
     } 
    } 
}