algoritmo eficiente para selecionar aleatoriamente itens com frequência

Question

Dada uma matriz de pares palavra-frequência n:

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

onde wi é uma palavra, fi é um frequencey inteiro, e a soma do ∑fi = m frequências,

Eu quero usar um gerador de números pseudo-aleatório (PRNG) para selecionar palavras p wj0, wj1, ..., wjp-1 tal que a probabilidade de selecionar qualquer palavra é proporcional à sua frequência:

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

(Note, esta é a seleção com a substituição, por isso a mesma palavra poderia ser escolhido a cada vez).

Eu vim com três algoritmos até agora:

1. Criar uma matriz de tamanho m, e preenchê-lo para as primeiras entradas f0 são w0, as inscrições seguinte f1 são w1, e assim por diante, de modo que as entradas última fp-1 são wp-1.

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

   Em seguida, use o PRNG para selecionar índices p na 0...m-1 gama, e relatar as palavras armazenadas nesses índices.
   Isso leva trabalho O(n + m + p), que não é grande, já que m pode ser muito, muito maior do que n.

2. Passo através da matriz de entrada uma vez que, de computação

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

   e depois mi computação, utilizar o PRNG para gerar um número xk no 0...mi-1 gama para cada k em 0...p-1 e selecione wi para wjk (possivelmente substituindo o valor atual de wjk) se xk < fi.
   Isso requer trabalho O(n + np).

3. Computar mi como no algoritmo 2, e gerar a seguinte matriz em triplos n palavra-frequência-parcial de soma:

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

   e, em seguida, para cada k em 0...p-1, utilize o PRNG para gerar uma xk número no 0...m-1 gama em seguida, fazer busca binária sobre a matriz de triplos para encontrar o S. T. i mi-fi ≤ xk < mi e selecione wi para wjk.
   Isso requer trabalho O(n + p log n).

A minha pergunta é :? Existe um algoritmo mais eficiente que eu posso usar para isso, ou são estes tão bom quanto ele ganha

Answer 1

Ok, eu encontrei um outro algoritmo: o método apelido (também mencionou nesta resposta ). Basicamente, ele cria uma partição do espaço de probabilidade de tal forma que:

• Existem partições n, todo o r S. T. mesma largura nr = m.
• cada partição contém duas palavras em alguma proporção (que é armazenado com a partição).
• para cada palavra wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Uma vez que todas as partições são do mesmo tamanho, selecionar qual partição pode ser feito em trabalho constante (escolher um índice de 0...n-1 de forma aleatória), e relação da partição pode ser usado para selecionar qual palavra é usada em trabalho constante ( comparar um número pRNGed com a relação entre as duas palavras). Então isso significa que as seleções p pode ser feito no trabalho O(p), dado tal partição.

A razão que existe tal particionamento é que existe um S. T. wi palavra fi < r, se e somente se existe um S. T. wi' palavra fi' > r, uma vez que r é a média das frequências.

Dada tal wi par e wi' podemos substituí-los com uma pseudo-palavra w'i de f'i = r frequência (que representa wi com fi/r probabilidade e wi' com 1 - fi/r probabilidade) e uma nova w'i' palavra de f'i' = fi' - (r - fi) frequência ajustada respectivamente. A frequência média de todas as palavras ainda será r, e a regra do parágrafo anterior ainda se aplica. Desde o pseudo-palavra tem frequência r e é feito de duas palavras com frequência r ?, sabemos que se nós iterate este processo, nunca iremos fazer uma pseudo-palavra para fora de um pseudo-palavra, e tal iteração deve terminar com um sequência de palavras pseudo-n que são a partição desejada.

Para construir esta partição no tempo O(n),

• percorrer a lista das palavras uma vez, a construção de duas listas:
  • uma das palavras com frequência = r
  • uma das palavras com frequência> r
• em seguida, puxe uma palavra da primeira lista
  • Se a sua frequência = r, em seguida, fazê-lo em uma partição elemento
  • Caso contrário, puxar uma palavra da outra lista, e usá-lo para preencher uma partição de duas palavras. Em seguida, coloque a segunda palavra de volta para a primeira ou segunda lista de acordo com a sua frequência ajustada.

Este realmente ainda funciona se o número de partições q > n (você só tem que provar isso de forma diferente). Se você quiser ter certeza de que r é integral, e você não pode facilmente encontrar um q fator de S. T. m q > n, você pode pad todas as freqüências por um fator de n, assim f'i = nfi, que atualiza m' = mn e conjuntos r' = m quando q = n.

Em qualquer caso, esse algoritmo leva apenas trabalho O(n + p), que eu tenho que pensar é o ideal.

Em 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

Isso soa como seleção roleta, usado principalmente para o processo de seleção em algoritmos genéticos / evolutivas.

Roulette Seleção em Algoritmos Genéticos

Answer 3

Pode-se criar a matriz alvo, então percorrer as palavras que determinam a probabilidade de que ele deve ser escolhido, e substituir as palavras na matriz de acordo com um número aleatório.

Para a primeira palavra a probabilidade seria f ₀ / m ₀ (em que m _n = f ₀ + .. + f _n ), ou seja 100%, de modo que todas as posições na matriz de destino seria preenchido com w ₀ .

Para as seguintes palavras, a probabilidade cai, e quando chegar a última palavra da matriz de destino é preenchido com palavras escolhidas aleatoriamente accoding à freqüência.

código Exemplo em 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;
        }
    }
}