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

StackOverflow https://stackoverflow.com/questions/872563

  •  22-08-2019
  •  | 
  •  

Вопрос

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

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

где wя это слово, fя — целая частота, а сумма частот ∑fя = m,

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

P(wя = wджк) = P(i = jк) = fя / m

(Обратите внимание, это выбор с заменой, поэтому одно и то же слово мог выбирать каждый раз).

На данный момент я придумал три алгоритма:

  1. Создайте массив размером m, и заполните его так, чтобы первый f0 записи w0, следующий f1 записи w1, и так далее, поэтому последнее fр-1 записи wр-1.

    [ w0, ..., w0, w1,..., w1, ..., wр-1, ..., wр-1 ]
    Затем используйте PRNG, чтобы выбрать p индексы в диапазоне 0...m-1, и сообщите слова, хранящиеся по этим индексам.
    Это занимает O(n + m + p) работа, что не очень хорошо, поскольку m может быть намного больше, чем n.

  2. Пройдите через входной массив один раз, вычислив

    mя = ∑h≤ifчас = mя-1 + fя
    и после вычислений mя, используйте PRNG для генерации числа xк В диапазоне 0...mя-1 для каждого k в 0...p-1и выберите wя для wджк (возможно замена текущего значения wджк) если xк < 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 для генерации числа xк В диапазоне 0...m-1 затем выполните двоичный поиск в массиве троек, чтобы найти i с.т. mя-fя ≤ xк < mя, и выберите wя для wджк.
    Это требует O(n + p log n) работа.

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

Это было полезно?

Решение 3

Хорошо, я нашел другой алгоритм: метод псевдонимов (также упоминается в этом ответе).По сути, он создает раздел вероятностного пространства так, что:

  • Есть n перегородки, все одинаковой ширины r с.т. nr = m.
  • каждый раздел содержит два слова в некотором соотношении (которое хранится вместе с разделом).
  • за каждое слово wя, fя = ∑перегородки t s.t wя ∈ т 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, мы знаем, что если мы будем повторять этот процесс, мы никогда не создадим псевдослово из псевдослова, и такая итерация должна заканчиваться последовательность из 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

Другие советы

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

Посмотри на Выбор в рулетке в генетических алгоритмах

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

Для первого слова вероятность будет f0/м0 (где мн=f0+..+фн), т.е.100%, поэтому все позиции в целевом массиве будут заполнены w0.

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

Пример кода на 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;
        }
    }
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top