頻度に応じて項目をランダムに選択する効率的なアルゴリズム

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

  •  22-08-2019
  •  | 
  •  

質問

の配列が与えられると、 n 単語と頻度のペア:

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

どこ w私 という言葉です、 f私 は整数の周波数であり、周波数の合計です。 ∑f私 = m,

疑似乱数発生器 (pRNG) を使用して選択したい p 言葉 wj0, wj1, ..., wjp-1 単語を選択する確率は、その頻度に比例するようにします。

P(w私 = wjk) = P(i = jk) = f私 / m

(これは置換を伴う選択であるため、同じ単語であることに注意してください) できた 毎回選ばれます）。

これまでに 3 つのアルゴリズムを考え出しました。

  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. 入力配列を 1 回ステップスルーして計算します

    m私 = ∑h≤ifh = mi-1 + f私
    そして計算後 m私, 、pRNG を使用して数値を生成します xk 範囲内 0...m私-1 それぞれに k で 0...p-1そして選択します w私 のために wjk (おそらく現在の値を置き換えます) wjk） もし xk < 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 を使用して数値を生成します xk 範囲内 0...m-1 次に、トリプルの配列に対して二分検索を実行して、 i セント m私-f私 ≤ xk < m私, を選択し、 w私 のために wjk.
    これには必要です O(n + p log n) 仕事。

私の質問は:これに使用できるより効率的なアルゴリズムはありますか? それとも、これらは可能な限り優れたアルゴリズムですか?

役に立ちましたか？

解決 3

OK、別のアルゴリズムを見つけました。 エイリアスメソッド (また言及 この回答では）。基本的には、次のような確率空間のパーティションを作成します。

  • がある n パーティション、すべて同じ幅 r セント nr = m.
  • 各パーティションには、ある比率で 2 つのワードが含まれます (パーティションとともに保存されます)。
  • それぞれの言葉に対して w私, f私 = ∑パーティション t s.t w私 ∈ t r × ratio(t,w私)

すべてのパーティションは同じサイズであるため、どのパーティションを選択するかは一定の作業で行うことができます (インデックスを選択する) 0...n-1 ランダムに)、パーティションの比率を使用して、定常作業でどの単語を使用するかを選択できます (pRNG された数値を 2 つの単語間の比率と比較します)。つまり、これは、 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 の 2 つの単語で構成されているため、このプロセスを反復しても、擬似単語から擬似単語を作成することは決してなく、そのような反復は次のコードで終了する必要があることがわかります。必要なパーティションである n 個の擬似ワードのシーケンス。

このパーティションを構築するには O(n) 時間、

  • 単語のリストを 1 回調べて、2 つのリストを作成します。
    • 頻度 ≤ r の単語の 1 つ
    • 頻度 > r の単語の 1 つ
  • 次に最初のリストから単語を取り出します
    • その頻度 = r の場合、それを 1 要素のパーティションにします
    • それ以外の場合は、他のリストから単語を取得し、それを使用して 2 単語のパーティションを埋めます。次に、調整された頻度に従って 2 番目の単語を最初または 2 番目のリストに戻します。

これは実際には、パーティションの数が変わっても機能します。 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

他のヒント

これは主に、遺伝的/進化的アルゴリズムにおける選択プロセスに使用するルーレット選択、のような音ます。

遺伝的アルゴリズムの

でルーレット選択を見てください

あなたは、ターゲット配列、それが選んだ、と乱数によるアレイ内の単語を交換しなければならないという確率を決定する言葉をループを作成することができます。

最初の単語の確率がf <サブ> 0 / M <サブ> 0 （M <サブ> N = F <サブ> 0 + .. + F <サブ> N ）、すなわち、100％、したがって標的配列内のすべての位置は、Wで充填される<サブ> 0 。

次の単語の確率が低下し、あなたはターゲットアレイが周波数にaccoding無作為に選んだ言葉で満たされた最後の言葉に達したときます。

の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;
        }
    }
}
所属していません StackOverflow
scroll top