Effizienter Algorithmus zum zufälligen Auswahl von Elementen mit der Frequenz
Frage
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:
-
Erstellen Sie eine Reihe von Größe
m
, und füllen Sie es so die erstenf0
Einträge sindw0
, die nächstenf1
Einträge sindw1
, und so weiter, so dass die letztenfp-1
Einträge sindwp-1
.[ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]
Dann die pRNG verwendenp
Indizes im Bereich0...m-1
auszuwählen, und die Worte an diesem Indizes gespeichert melden.
Dies geschiehtO(n + m + p)
Arbeit, die nicht groß, dam
viel viel größer als n sein kann. -
Schritt durch die Eingangsanordnung einmal, Berechnen
mi = ∑h≤ifh = mi-1 + fi
und nach den Rechenmi
, verwenden, um die pRNG eine Zahl im Bereichxk
0...mi-1
für jedek
in0...p-1
zu erzeugen, und wählen Siewi
fürwjk
(möglicherweise ersetzt den aktuellen Wert vonwjk
), wennxk < fi
.
Dies erfordertO(n + np)
Arbeit. - 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 in0...p-1
, verwenden, um die pRNG eine Zahl im Bereichxk
0...m-1
erzeugt dann auf dem Array von Tripeln Binärsuche tun, um diei
S.T. zu findenmi-fi ≤ xk < mi
und wählenwi
fürwjk
.
Dies erfordertO(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
Lösung 3
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 Breiter
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
Andere Tipps
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
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 0 / m 0 (wobei m n = f 0 + .. + 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;
}
}
}