10

n単語と頻度のペアの配列が与えられた場合:

[ (w 0 , f 0 ), (w 1 , f 1 ), ..., (w n-1 , f n-1 ) ]

ここで、 は単語、は整数の周波数、周波数の合計、wifi∑fi = m

任意の単語を選択する確率がその頻度に比例するように、擬似乱数ジェネレータ (pRNG) を使用してp単語を選択したいと考えています。wj0, wj1, ..., wjp-1

P(w i = w j k ) = P(i = j k ) = f i / m

(これは置換を伴う選択であるため、毎回同じ単語が選択される可能性があることに注意してください)。

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

  1. サイズ の配列を作成しm、最初のエントリが、次のエントリが、というように、最後のエントリがになるように入力します。f0w0f1w1fp-1wp-1

    [ w 0 , ..., w 0 , w 1 ,..., w 1 , ..., w p-1 , ..., w p-1 ]
    次に、pRNG を使用pして範囲内のインデックスを選択し0...m-1、それらのインデックスに格納されている単語を報告します。n よりもはるかに大きくなる可能性があるため、
    これには手間がかかります。O(n + m + p)m

  2. 入力配列を 1 回ステップ実行し、計算します。

    m i = ∑ h≤i f h = m i-1 + f i
    を計算した後、pRNG を使用して のそれぞれの範囲内の数値を生成し、 for を選択します(場合によっては の現在の値を置き換えます) 。 これには作業が必要です。mixk0...mi-1k0...p-1wiwjkwjkxk < fi
    O(n + np)

  3. アルゴリズム 2 のように計算し、n 個の単語-頻度-部分和のトリプルで次の配列を生成します。mi
    [ (w 0 , f 0 , m 0 ), (w 1 , f 1 , m 1 ), ..., (w n-1 , f n-1 , m n-1 ) ]
    次に、各 k in0...p-1について、pRNG を使用して範囲内の数値を生成し、トリプルの配列でバイナリ検索を実行してstを見つけ、 forを選択します。 これには作業が必要です。xk0...m-1imi-fi ≤ xk < miwiwjk
    O(n + p log n)

私の質問は次のとおりです。これに使用できるより効率的なアルゴリズムはありますか、それともこれほど優れていますか?

4

3 に答える 3

6

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

遺伝的アルゴリズムのルーレット選択を見てください

于 2009-05-16T15:06:17.987 に答える
2

ターゲット配列を作成し、単語をループして選択する確率を決定し、乱数に従って配列内の単語を置き換えることができます。

最初の単語の場合、確率は 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;
        }
    }
}
于 2009-05-16T15:54:48.103 に答える
0

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

  • パーティションがありn、すべて同じ幅rstnr = mです。
  • 各パーティションには、ある比率で2つの単語が含まれています（これはパーティションとともに保存されます）。
  • 単語ごとに、wifi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

すべてのパーティションが同じサイズであるため、一定の作業で実行できるパーティションを選択し（0...n-1ランダムにインデックスを選択）、パーティションの比率を使用して、一定の作業で使用する単語を選択できます（pRNGされた数を比較します） 2つの単語の比率で）。つまり、このようなパーティションpがあれば、選択は作業中に行うことができます。O(p)

このような分割が存在する理由は、rが頻度の平均であるため 、単語stが存在する場合に限り、単語stが存在するためです。wifi < rwi'fi' > r

そのようなペアが与えられ、それらを頻度の擬似単語（確率と確率で表す）と調整された頻度の新しい単語にそれぞれ置き換えることができます。すべての単語の平均頻度は引き続きrであり、前の段落の規則が引き続き適用されます。疑似単語の頻度はrであり、頻度≠rの2つの単語で構成されているため、このプロセスを繰り返すと、疑似単語から疑似単語が作成されることはなく、そのような反復は次のように終了する必要があります。目的のパーティションであるn個の擬似単語のシーケンス。wiwi'w'if'i = rwifi/rwi'1 - fi/rw'i'f'i' = fi' - (r - fi)

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

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

これは、パーティションの数が多い場合でも実際に機能しq > nます（別の方法で証明する必要があります）。rが整数であることを確認したい場合で、 stの係数qを簡単に見つけることができない場合は、すべての周波数を係数、soで埋めることができます。これにより、が更新および設定されます。mq > nnf'i = nfim' = mnr' = mq = 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
于 2009-05-16T22:10:18.920 に答える