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