Effizienter Algorithmus zum zufälligen Auswahl von Elementen mit der Frequenz

Question

ein Feld von n Worthäufigkeitspaaren Gegeben:

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

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

Ich mag einen Pseudo-Zufallszahlengenerator (pRNG) verwenden, um p Worte wj0, wj1, ..., wjp-1 so zu wählen, dass die Wahrscheinlichkeit des Auswählens jedes Wort auf seine Frequenz proportional:

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

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

Ich habe mit drei Algorithmen kommt so weit:

1. Erstellen Sie eine Reihe von Größe 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 dass die letzten fp-1 Einträge sind wp-1.

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

   Dann die pRNG verwenden p Indizes im Bereich 0...m-1 auszuwählen, und die Worte an diesem Indizes gespeichert melden.
   Dies geschieht O(n + m + p) Arbeit, die nicht groß, da m viel viel größer als n sein kann.

2. Schritt durch die Eingangsanordnung einmal, Berechnen

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

   und nach den Rechen mi, verwenden, um die pRNG eine Zahl im Bereich xk 0...mi-1 für jede k in 0...p-1 zu erzeugen, und wählen Sie wi für wjk (möglicherweise ersetzt den aktuellen Wert von wjk), wenn xk < fi.
   Dies erfordert O(n + np) Arbeit.

3. Compute mi Algorithmus wie in 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 Zahl im Bereich xk 0...m-1 erzeugt dann auf dem Array von Tripeln Binärsuche tun, um die i S.T. zu finden mi-fi ≤ xk < mi und wählen 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, ich fand einen anderen Algorithmus: der Alias-Methode (genannt auch in dieser Antwort ). Im Grunde ist es schafft eine Teilung des Wahrscheinlichkeitsraum, so dass:

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

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

Der Grund, dass eine solche Unterteilung existiert, ist, dass es ein Wort wi S. T. existiert fi < r, wenn und nur wenn es ein Wort wi' S. T. fi' > r, da r ist der Durchschnitt der Frequenzen.

Bei einer solchen Paar wi und wi' wir sie mit einem pseudo-Wort w'i der Frequenz f'i = r ersetzen kann (das entspricht wi mit Wahrscheinlichkeit fi/r und wi' mit Wahrscheinlichkeit 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 noch r sein, und die Regel aus dem Stand der Absatz immer noch gilt. Da die Pseudowortfrequenz r hat und aus zwei Worten mit der Frequenz ≠ r gemacht, wissen wir, dass, wenn wir diesen Prozess durchlaufen, werden wir nie ein pseudo-Wort aus einem pseudo-Wort machen, und solche Iteration muss mit einem Ende Sequenz von n Pseudo-Wörter, die die gewünschte Partition sind.

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

• gehen Sie durch die Liste der Wörter einmal, den Bau zwei Listen:
  • eine der Wörter mit Frequenz ≤ r
  • ein von Worten mit einer Frequenz> r
• dann ein Wort aus der ersten Liste ziehen
  • , wenn seine Frequenz = r, dann machen Sie es in eine ein Element Partition
  • sonst, ziehen Sie ein Wort aus der anderen Liste, und es verwendet, eine Zwei-Wort-Partition zu füllen. setzt dann das zweite Wort zurück in entweder der erste oder zweite Liste gemäß ihrer eingestellten Frequenz.

Das 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 verbunden ist, und man kann nicht einfach einen Faktor q von m finden S. T. q > n, können Sie Pad alle Frequenzen um einen Faktor von n, so f'i = nfi, die m' = mn aktualisiert und setzt r' = m wenn q = n.

In jedem Fall dieser Algorithmus nimmt nur O(n + p) Arbeit, die ich habe zu denken, optimal ist.

In rubin:

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

Das klingt wie Roulette-Rad Auswahl, vor allem für den Auswahlprozess in der genetischen / evolutionären Algorithmen verwendet.

Lesen Sie Roulette-Auswahl in Genetic Algorithms

Answer 3

Sie könnten die 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 würde die Wahrscheinlichkeit, f ₀ / m ₀ (wobei m _n = f ₀ + .. + f _{n , dh 100%, so würde alle Positionen in der Zielanordnung mit> w 0}

Für die folgenden Wörter die Wahrscheinlichkeit sinkt, und wenn Sie das letzte Wort das Ziel-Array erreicht wird mit zufällig ausgewählten Wörtern gefüllt accoding auf die Frequenz.

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;
        }
    }
}