Эффективный алгоритм случайного выбора предметов с частотой - PullRequest
10 голосов
/ 16 мая 2009

Имеется массив из n пар слов-частот:

[ (w<sub>0</sub>, f<sub>0</sub>), (w<sub>1</sub>, f<sub>1</sub>), ..., (w<sub>n-1</sub>, f<sub>n-1</sub>) ]

, где w<sub>i</sub> - слово, f<sub>i</sub> - целочисленная частота, а сумма частот &sum;f<sub>i</sub> = m,

.

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

P(w<sub>i</sub> = w<sub>j<sub>k</sub></sub>) = P(i = j<sub>k</sub>) = f<sub>i</sub> / m

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

До сих пор я придумал три алгоритма:

  1. Создайте массив размером m и заполните его так, чтобы первые f<sub>0</sub> записи были w<sub>0</sub>, следующие f<sub>1</sub> записи были w<sub>1</sub> и т. Д., Так что последние f<sub>p-1</sub> записи w<sub>p-1</sub>.

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

    m<sub>i</sub> = &sum;<sub>h&le;i</sub>f<sub>h</sub> = m<sub>i-1</sub> + f<sub>i</sub>
    и после вычисления m<sub>i</sub> используйте pRNG для генерирования числа x<sub>k</sub> в диапазоне 0...m<sub>i</sub>-1 для каждого k в 0...p-1 и выберите w<sub>i</sub> для w<sub>j<sub>k</sub></sub> (возможно, заменив текущее значение w<sub>j<sub>k</sub></sub>), если x<sub>k</sub> < f<sub>i</sub>.
    Это требует O(n + np) работы.
  3. Вычислите m<sub>i</sub>, как в алгоритме 2, и сгенерируйте следующий массив для n троекратных слов частичной суммы:
    [ (w<sub>0</sub>, f<sub>0</sub>, m<sub>0</sub>), (w<sub>1</sub>, f<sub>1</sub>, m<sub>1</sub>), ..., (w<sub>n-1</sub>, f<sub>n-1</sub>, m<sub>n-1</sub>) ]
    а затем для каждого k в 0...p-1 используйте pRNG, чтобы сгенерировать число x<sub>k</sub> в диапазоне 0...m-1, затем выполните двоичный поиск по массиву троек, чтобы найти i s.t. m<sub>i</sub>-f<sub>i</sub> &le; x<sub>k</sub> < m<sub>i</sub> и выберите w<sub>i</sub> для w<sub>j<sub>k</sub></sub>.
    Это требует O(n + p log n) работы.

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

Ответы [ 3 ]

6 голосов
/ 16 мая 2009

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

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

2 голосов
/ 16 мая 2009

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

Для первого слова вероятность будет 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;
        }
    }
}
1 голос
/ 17 мая 2009

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

  • Есть n разделов одинаковой ширины r s.t. nr = m.
  • каждый раздел содержит два слова в некотором соотношении (которое хранится вместе с разделом).
  • для каждого слова w<sub>i</sub>, f<sub>i</sub> = &sum;<sub>partitions t s.t w<sub>i</sub> &isin; t</sub> r &times; ratio(t,w<sub>i</sub>)

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

Причина, по которой существует такое разбиение, состоит в том, что существует слово w<sub>i</sub> s.t. f<sub>i</sub> < r, если и только если существует слово w<sub>i'</sub> s.t. f<sub>i'</sub> > r, поскольку r является средним значением частот.

При наличии такой пары w<sub>i</sub> и w<sub>i'</sub> мы можем заменить их псевдословом w'<sub>i</sub> с частотой f'<sub>i</sub> = r (который представляет w<sub>i</sub> с вероятностью f<sub>i</sub>/r и w<sub>i'</sub> с вероятностью 1 - f<sub>i</sub>/r) и новое слово w'<sub>i'</sub> скорректированной частоты f'<sub>i'</sub> = f<sub>i'</sub> - (r - f<sub>i</sub>) соответственно. Средняя частота всех слов по-прежнему будет r, и правило из предыдущего абзаца будет по-прежнему применяться. Поскольку псевдослово имеет частоту r и состоит из двух слов с частотой & ne; r, мы знаем, что если мы повторим этот процесс, мы никогда не сделаем псевдослова из псевдослова, и такая итерация должна заканчиваться последовательностью из n псевдословов, которые являются желаемым разбиением.

Чтобы построить этот раздел в O(n) времени,

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

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