effizienter Algorithmus zum zufälligen Auswahl von Elementen mit frequenz

Question

Gegeben eine Anordnung von n Worthäufigkeitspaaren:

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

wo wi ist ein Wort, fi eine ganze Zahl frequencey, und die Summe der Frequenzen ∑fi = m,

Ich möchte mit einem Pseudozufallszahlengenerator (pRNG) p Wörter wj0, wj1, ..., wjp-1 so wählen, dass die Wahrscheinlichkeit der Auswahl eines Wortes ist proportional zu seiner Frequenz:

P(wi = wjk) = P(i = jk) = fi/m

(Beachten Sie, ist diese Auswahl mit Ersatz, so dass das gleiche Wort kann jedes Mal gewählt werden).

Ich habe bisher mit drei Algorithmen kommen:

1. eine Reihe von Größe erstellen m, und füllen Sie es so die ersten f0 Einträge sind w0, die nächsten f1 Einträge sind w1, und so weiter , so die letzten fp-1 Einträge sind wp-1.

   [ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]

   Dann verwenden Sie die pRNG, um Indizes im Bereich 0...m-1 auszuwählen, und melden Sie die Wörter in diesen Indizes gespeichert.
   Dies dauert O(n + m + p) Arbeit, die nicht gut ist, da m viel viel größer als n sein kann.

2. Schritt durch die Eingangsanordnung einmal Rechen

   mi = ∑h≤ifh = mi-1 + fi

   und mi nach Berechnung verwenden, um die pRNG eine Anzahl xk im Bereich zu erzeugen 0...mi-1 für jeden k in 0...p-1 und wählt wi für wjk (möglicherweise den aktuellen Wert des Ersetzen wjk) wenn xk < fi.
   Dies erfordert O(n + np) Arbeit.

3. Compute mi wie in Algorithmus 2 und erzeugen die folgende Anordnung auf n Wortfrequenz-Teilsumme Tripel:

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

   und dann für jeden k in 0...p-1, verwenden, um die pRNG eine Anzahl xk im Bereich zu erzeugen 0...m-1 dann binäre Suche auf dem Array von Tripeln, um die i st zu finden mi-fi ≤ xk < mi, und wählen Sie wi für wjk.
   Dies erfordert O(n + p log n) Arbeit.

Meine Frage ist: Gibt es einen effizienteren Algorithmus ich dafür verwenden können, oder sind diese so gut wie es geht?

Answer 1

Ok, fand ich einen anderen Algorithmus: the alias method (auch erwähnt in this answer). Grundsätzlich erstellt es eine Teilung des Wahrscheinlichkeitsraum, so dass:

• Es gibt n Partitionen, alle von der gleichen Breite r S. T. nr = m.
• jede Partition enthält zwei Wörter in einem Verhältnis (das mit der Partition gespeichert wird).
• für jedes Wort wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Da alle Partitionen sind von der gleichen Größe, die Auswahl, welche Partition in konstanten Arbeit getan werden kann (einen Index von 0...n-1 zufällig wählen), und das Verhältnis der Partition kann dann verwendet werden, um auszuwählen, welches Wort in konstanter Arbeit verwendet wird (vergleiche eine pRNGed-Zahl mit dem Verhältnis zwischen den beiden Wörtern). Das bedeutet also, dass die Auswahlen in O(p) Arbeit getan werden können, vorausgesetzt solch eine Partition.

Der Grund, warum eine solche Partitionierung existiert, ist, dass es ein Wort gibt wi s.t. fi < r, wenn und nur wenn es ein Wort gibt wi' s.t. fi' > r, da r der Durchschnitt der Frequenzen ist.

Bei einem solchen Paar wi und wi' wir sie mit einem Pseudowort f'i = rw'i der Frequenz ersetzen kann (das bedeutet wi mit Wahrscheinlichkeit fi/rwi' und mit einer Wahrscheinlichkeit von 1 - fi/r) und ein neues Wort w'i' der eingestellten Frequenz f'i' = fi' - (r - fi) sind. Die durchschnittliche Häufigkeit aller Wörter ist immer noch r, und die Regel aus dem vorherigen Absatz gilt immer noch. Da das Pseudowort die Frequenz r hat und aus zwei Wörtern mit der Frequenz ≠ r besteht, wissen wir, dass wir, wenn wir diesen Prozess iterieren, niemals ein Pseudowort aus einem Pseudowort erzeugen werden, und eine solche Iteration muss mit a enden Folge von n Pseudowörtern, die die gewünschte Partition darstellen.

Um diese Partition in O(n) Zeit zu konstruieren,

• einmal die Liste der Wörter gehen, zwei Listen Konstruktion:
  • einem der Wörter mit der Frequenz ≤ r
  • einem der Wörter mit Frequenz > r
• dann ziehen Sie ein Wort von der ersten lis t
  • wenn seine Frequenz = r, dann ist es in eine Partition eines Elements bilden
  • Andernfalls zieht ein Wort aus der anderen Liste, und verwenden sie eine Zwei-Wort-Partition auszufüllen. Dann lege das zweite Wort entsprechend der eingestellten Frequenz entweder in die erste oder in die zweite Liste zurück.

Dies funktioniert eigentlich immer noch, wenn die Anzahl der Partitionen q > n (Sie es gerade anders beweisen müssen). Wenn Sie sicherstellen möchten, dass r integral ist, und Sie nicht leicht einen Faktor q von m s.t finden können. q > n können Sie alle Frequenzen mit einem Faktor von n, also f'i = nfi, die m' = mn aktualisiert und r' = m wenn q = n setzt.

In jedem Fall braucht dieser Algorithmus nur O(n + p) Arbeit, die ich für optimal halte.

in Ruby:

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 

Answer 2

Dies klingt wie Rouletteauswahl, hauptsächlich für den Auswahlprozess in genetischen/evolutionären Algorithmen verwendet.

Blick auf Roulette Selection in Genetic Algorithms

Answer 3

könnten Sie das Ziel Array erstellen, dann Schleife durch die Worte, um die Wahrscheinlichkeit zu bestimmen, dass sie abgeholt werden sollen, und die Worte in der Anordnung ersetzen nach einer Zufallszahl.

für das erste Wort der Wahrscheinlichkeit f würde/m (wobei m n = f 0 + .. + f n), dh 100%, so dass alle Positionen in das Zielarray würde mit w gefüllt werden.

Für die folgenden Wörter fällt die Wahrscheinlichkeit, und wenn Sie das letzte Wort erreichen, wird das Zielarray mit zufällig ausgewählten Wörtern entsprechend der Häufigkeit gefüllt.

Beispiel Code in 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; 
     } 
    } 
}