आवृत्ति के साथ यादृच्छिक रूप से आइटम का चयन करने के लिए कुशल एल्गोरिदम

Question

n शब्द आवृत्ति जोड़े की एक सरणी को देखते हुए:

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

जहां wi एक शब्द है, fi एक पूर्णांक आवृत्ति है, और आवृत्तियों का योग ∑fi = m,

मैं एक छद्म-यादृच्छिक उपयोग करना चाहता हूं p शब्द wj0, wj1, ..., wjp-1 का चयन करने के लिए संख्या जेनरेटर (पीआरएनजी) जैसे किसी भी शब्द का चयन करने की संभावना इसकी आवृत्ति के आनुपातिक है:

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

(ध्यान दें, यह प्रतिस्थापन के साथ चयन है, इसलिए वही शब्द चुना जा सकता है हर बार)।

मैं अब तक तीन एल्गोरिदम के साथ आया हूं:

1. आकार m की एक सरणी बनाएं, और इसे पॉप्युलेट करें ताकि पहली f0 प्रविष्टियां w0 हों, अगली f1 प्रविष्टियां w1 हैं, और इसी तरह , इसलिए अंतिम fp-1 प्रविष्टियां wp-1 हैं।

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

   फिर श्रेणी 0...m-1 में p सूचकांक का चयन करने के लिए पीआरएनजी का उपयोग करें, और उन सूचकांक में संग्रहीत शब्दों की रिपोर्ट करें।
   यह O(n + m + p) काम लेता है, जो कि बहुत अच्छा नहीं है, क्योंकि m n से बहुत बड़ा हो सकता है।

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

   कंप्यूटिंग के बाद एक बार इनपुट सरणी के माध्यम से चरण और mi कंप्यूटिंग के बाद, 0...p-1 में प्रत्येक k के लिए 0...mi-1 श्रेणी xk उत्पन्न करने के लिए पीआरएनजी का उपयोग करें और wjk के लिए wi का चयन करें (संभवतः वर्तमान मूल्य को बदलना wjk) अगर xk < fi।
   यह O(n + np) काम की आवश्यकता है।

3. mi को एल्गोरिदम 2 के रूप में गणना करें, और एन वर्ड-आवृत्ति-आंशिक-योग ट्रिपल पर निम्न सरणी उत्पन्न करें:

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

   और फिर, 0...p-1 में प्रत्येक के लिए, 0...m-1 श्रेणी में xk संख्या उत्पन्न करने के लिए पीआरएनजी का उपयोग करें फिर i सेंट खोजने के लिए ट्रिपल की सरणी पर बाइनरी खोज करें mi-fi ≤ xk < mi, और wjk के लिए wi का चयन करें।
   यह O(n + p log n) काम की आवश्यकता है।

मेरा प्रश्न है: क्या इसके लिए एक और अधिक कुशल एल्गोरिदम मैं उपयोग कर सकता हूं, या ये उतना ही अच्छा है जितना इसे प्राप्त होता है?

Answer 1

ठीक है, मैं एक एल्गोरिथ्म पाया: the alias method (भी in this answer उल्लेख किया)। मूल रूप से यह संभावना अंतरिक्ष के एक विभाजन बनाता है ऐसा है कि:

• n विभाजन, एक ही चौड़ाई r s.t. के सभी कर रहे हैं nr = m।
• प्रत्येक विभाजन में कुछ अनुपात में दो शब्द होते हैं (जो विभाजन के साथ संग्रहीत होते हैं)।
प्रत्येक शब्द wi के लिए
• , fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

के बाद से सभी विभाजनों एक ही आकार, चयन जो विभाजन लगातार काम किया जा सकता है के हैं (0...n-1 यादृच्छिक पर से एक सूचकांक लेने), और विभाजन के अनुपात से पता तो कर सकते हैं निरंतर काम में कौन सा शब्द प्रयोग किया जाता है, यह चुनने के लिए प्रयोग किया जाए (दो शब्दों के बीच अनुपात के साथ एक पीआरएनजीड संख्या की तुलना करें)। तो इसका मतलब है कि p चयन O(p) कार्य में ऐसा विभाजन दिया जा सकता है।

कारण यह विभाजन मौजूद है कि wi s.t. शब्द मौजूद है। fi < r, यदि और केवल यदि कोई शब्द wi' s.t है। fi' > r, चूंकि आर आवृत्तियों का औसत है।

इस तरह के एक जोड़ी wi और wi' हम उन्हें एक छद्म शब्द आवृत्ति f'i = r की w'i (कि संभावना 1 - fi/r साथ संभावना fi/r साथ wi और wi' प्रतिनिधित्व करता है) और क्रमशः समायोजित आवृत्ति f'i' = fi' - (r - fi) का एक नया शब्द w'i' से बदल सकते हैं को देखते हुए। सभी शब्दों की औसत आवृत्ति अभी भी आर होगी, और पूर्व अनुच्छेद से नियम अभी भी लागू होता है। चूंकि छद्म शब्द में आवृत्ति आर होती है और आवृत्ति ≠ आर के साथ दो शब्दों से बना है, हम जानते हैं कि यदि हम इस प्रक्रिया को पुन: सक्रिय करते हैं, तो हम कभी छद्म शब्द से छद्म शब्द नहीं बना पाएंगे, और इस तरह के पुनरावृत्ति को समाप्त होना चाहिए एन छद्म शब्दों का अनुक्रम जो वांछित विभाजन हैं।

O(n) समय में इस विभाजन का निर्माण करने के लिए,

• शब्दों की सूची के माध्यम से एक बार जाना, दो सूचियों के निर्माण: के साथ आवृत्ति ≤ आर
• शब्दों में से एक के साथ
  • शब्दों में से एक आवृत्ति > आर
• फिर पहले लिस से एक शब्द खींचें टी
  • अगर इसकी आवृत्ति = r, तो यह एक एक तत्व विभाजन में बनाने
  • अन्यथा, अन्य सूची से एक शब्द निकालते हैं और इसका इस्तेमाल एक दो शब्द विभाजन को भरने के लिए। फिर दूसरे शब्द को अपनी समायोजित आवृत्ति के अनुसार पहली या दूसरी सूची में वापस रखें।

यह वास्तव में अभी भी काम करता है विभाजन q > n की संख्या (आप बस इसे दूसरे तरीके से साबित करना है) है। यदि आप यह सुनिश्चित करना चाहते हैं कि आर अभिन्न है, और आप आसानी से m s.t. के कारक को आसानी से नहीं ढूंढ सकते हैं। q > n, आप सभी आवृत्तियों को n के कारक द्वारा पैड कर सकते हैं, इसलिए f'i = nfi, जो m' = mn अपडेट करता है और 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 

Answer 2

यह रूले व्हील चयन की तरह लगता है, मुख्य रूप से जेनेटिक/विकासवादी एल्गोरिदम में चयन प्रक्रिया के लिए उपयोग किया जाता है।Roulette Selection in Genetic Algorithms

Answer 3

पर

देखो आप लक्ष्य सरणी, तो शब्द संभावना यह उठाया जाना चाहिए कि निर्धारित करने के माध्यम से लूप बनाते हैं, और एक यादृच्छिक संख्या के अनुसार सरणी में शब्दों को बदलने के कर सकते हैं।

पहला शब्द संभावना f किया जाएगा के लिए/मी (जहां m _n = च + .. + एफ _n), यानी 100% है, इसलिए सभी में पदों लक्ष्य सरणी w से भरी जाएगी।

निम्नलिखित शब्दों के लिए संभावनाएं गिरती हैं, और जब आप अंतिम शब्द तक पहुंचते हैं तो लक्ष्य सरणी आवृत्ति पर एन्कोडिंग यादृच्छिक रूप से चुने गए शब्दों से भरी होती है। सी # में

उदाहरण कोड:

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