خوارزمية فعالة لتحديد العناصر بشكل عشوائي مع التردد

Question

نظرا لمجموعة من n أزواج تردد الكلمات:

[ (w0, f0), (w1, f1), ..., (wن-1, fن-1) ]

أين wأنا هي كلمة، fأنا هو تردد عدد صحيح، ومجموع الترددات ∑fأنا = m,

أريد استخدام منشئ أرقام عشوائية زائفة (pRNG) للاختيار p كلمات wي0, wي1, ..., wيص-1 مثل أن احتمال اختيار أي كلمة يتناسب مع تواترها:

P(wأنا = wيك) = P(i = jك) = fأنا / m

(ملاحظة، هذا اختيار مع استبدال، لذا فإن نفس الكلمة استطاع يتم اختياره في كل مرة).

لقد توصلت إلى ثلاث خوارزميات حتى الآن:

1. إنشاء مجموعة من الحجم m, ، واملأها بذلك الأول f0 الإدخالات هي w0, ، التالي f1 الإدخالات هي w1, ، وهكذا، وهكذا الأخير fص-1 الإدخالات هي wص-1.

   [ w0, ..., w0, w1,..., w1, ..., wص-1, ..., wص-1 ]

   ثم استخدم pRNG للاختيار p المؤشرات في النطاق 0...m-1, ، والإبلاغ عن الكلمات المخزنة في تلك الفهارس.
   هذا يأخذ O(n + m + p) العمل، وهو ليس رائعًا، منذ ذلك الحين m يمكن أن يكون أكبر بكثير من n.

2. قم بالمرور عبر مصفوفة الإدخال مرة واحدة، وقم بالحوسبة

   mأنا = ∑h<ifح = mأنا-1 + fأنا

   وبعد الحوسبة mأنا, ، استخدم pRNG لإنشاء رقم xك في النطاق 0...mأنا-1 لكل k في 0...p-1وحدد wأنا ل wيك (ربما تحل محل القيمة الحالية لـ wيك) لو xك < fأنا.
   هذا يتطلب O(n + np) عمل.

3. إحصاء - عد mأنا كما هو الحال في الخوارزمية 2، وقم بإنشاء المصفوفة التالية على عدد ثلاثي من الكلمات ذات التردد الجزئي:

   [ (w0, f0, m0), (w1, f1, m1), ..., (wن-1, fن-1, mن-1) ]

   وبعد ذلك، لكل k في 0...p-1, ، استخدم pRNG لإنشاء رقم xك في النطاق 0...m-1 ثم قم بإجراء بحث ثنائي على مجموعة الثلاثيات للعثور على i شارع. mأنا-fأنا ≤ xك < mأنا, ، وحدد wأنا ل wيك.
   هذا يتطلب O(n + p log n) عمل.

سؤالي هو:هل هناك خوارزمية أكثر كفاءة يمكنني استخدامها لهذا، أم أنها جيدة كما هي؟

Answer 1

حسنًا، لقد وجدت خوارزمية أخرى: طريقة الاسم المستعار (كما ذكر في هذه الإجابة).يقوم في الأساس بإنشاء قسم من مساحة الاحتمال مثل:

• هناك n أقسام، كلها بنفس العرض r شارع. nr = m.
• يحتوي كل قسم على كلمتين بنسبة ما (يتم تخزينهما مع القسم).
• لكل كلمة wأنا, fأنا = ∑أقسام t s.t wأنا ∈ ر r × ratio(t,wأنا)

نظرًا لأن جميع الأقسام لها نفس الحجم، فإن تحديد القسم الذي يمكن إجراؤه من خلال العمل المستمر (اختر فهرسًا من 0...n-1 عشوائيًا)، ويمكن بعد ذلك استخدام نسبة القسم لتحديد الكلمة المستخدمة في العمل المستمر (مقارنة رقم pRNGed مع النسبة بين الكلمتين).إذن هذا يعني p يمكن إجراء التحديدات في O(p) العمل، نظرا لمثل هذا التقسيم.

سبب وجود مثل هذا التقسيم هو وجود كلمة wأنا شارع. fأنا < r, ، إذا وفقط إذا كانت هناك كلمة wأنا' شارع. fأنا' > r, حيث أن r هو متوسط ​​الترددات.

نظرا لمثل هذا الزوج wأنا و wأنا' يمكننا استبدالها بكلمة زائفة w'أنا من تكرار f'أنا = r (الذي يمثل wأنا مع الاحتمال fأنا/r و wأنا' مع الاحتمال 1 - fأنا/r) وكلمة جديدة w'أنا' من التردد المعدل f'أنا' = fأنا' - (r - fأنا) على التوالى.سيظل متوسط ​​تكرار جميع الكلمات هو r، وستظل القاعدة من الفقرة السابقة سارية.نظرًا لأن الكلمة الزائفة لها تردد r ومكونة من كلمتين بتردد ≠ r، فإننا نعلم أنه إذا كررنا هذه العملية، فلن نصنع أبدًا كلمة زائفة من كلمة زائفة، ويجب أن ينتهي هذا التكرار بـ تسلسل n من الكلمات الزائفة التي تمثل القسم المطلوب.

لبناء هذا القسم في O(n) وقت،

• قم بالاطلاع على قائمة الكلمات مرة واحدة، وقم بإنشاء قائمتين:
  • إحدى الكلمات ذات التردد ≥ r
  • إحدى الكلمات ذات التردد> r
• ثم اسحب كلمة من القائمة الأولى
  • إذا كان تردده = r، فاجعله قسمًا مكونًا من عنصر واحد
  • وإلا، فاسحب كلمة من القائمة الأخرى، واستخدمها لملء قسم مكون من كلمتين.ثم ضع الكلمة الثانية مرة أخرى في القائمة الأولى أو الثانية حسب تكرارها المعدل.

هذا في الواقع لا يزال يعمل إذا كان عدد الأقسام q > n (عليك فقط إثبات ذلك بشكل مختلف).إذا كنت تريد التأكد من أن r جزء لا يتجزأ، ولا يمكنك العثور على عامل بسهولة q ل m شارع. q > n, ، يمكنك وسادة جميع الترددات بعامل n, ، لذا f'أنا = nfأنا, ، الذي يقوم بالتحديث m' = mn ومجموعات r' = m متى 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

يبدو هذا مثل اختيار عجلة الروليت، والذي يستخدم بشكل أساسي في عملية الاختيار في الخوارزميات الجينية/التطورية.

ينظر الى اختيار الروليت في الخوارزميات الجينية

Answer 3

يمكنك إنشاء المصفوفة المستهدفة، ثم تكرار الكلمات لتحديد احتمالية اختيارها، واستبدال الكلمات الموجودة في المصفوفة وفقًا لرقم عشوائي.

بالنسبة للكلمة الأولى فإن الاحتمال هو f₀/م₀ (حيث م_ن= و₀+..+و_ن)، أي.100%، لذلك سيتم ملء جميع المواضع في المصفوفة المستهدفة بـ w₀.

بالنسبة للكلمات التالية، ينخفض ​​الاحتمال، وعندما تصل إلى الكلمة الأخيرة، تمتلئ المصفوفة المستهدفة بكلمات منتقاة عشوائيًا وفقًا للتكرار.

رمز المثال في 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;
        }
    }
}