按使用频率随机选择字母

Question

在将少量莎士比亚书籍送到我的Perl脚本后,我有一个哈希,其中包含26个英文字母作为键,以及它们在文本中出现的次数 - 作为值:

%freq = (
    a => 24645246,
    b => 1409459,
    ....
    z => 807451,
);

当然还有所有字母的总数 - 让我们在$total变量中说.

是否有一个很好的技巧来生成一个包含16个随机字母的字符串(一个字母可以在那里出现几次) - 按使用频率加权？

要在类似于Ruzzle的文字游戏中使用:

优雅的东西 - 比如从文件中挑选一条随机行,如Perl Cookbook收据所示:

rand($.) < 1 && ($line = $_) while <>;

Answer 1

我对Perl语法一无所知所以我只会编写伪代码.你可以做那样的事情

sum <= 0
foreach (letter in {a, z})
  sum <= sum + freq[letter]
pick r, a random integer in [0, sum[ 
letter <= 'a' - 1
do
  letter <= letter + 1
  r <= r - freq(letter)
while r > 0

letter is the resulting value

这段代码背后的想法是为每个字母制作一堆盒子.每个框的大小是字母的频率.然后我们在这个堆栈上选择一个随机位置,看看我们登陆的是哪个字母的框.

示例:

freq(a) = 5
freq(b) = 3
freq(c) = 3
sum = 11

|    a    |  b  |  c  | 
 - - - - - - - - - - - 

当我们选择0 <= r <11时,我们有以下概率

• 选择'a'= 5/11
• 选择'b'= 3/11
• 选择'c'= 3/11

这正是我们想要的.

Answer 2

选择随机线的Perl Cookbook技巧(也可以在perlfaq5中找到)也可以用于加权采样:

my $chosen;
my $sum = 0;
foreach my $item (keys %freq) {
    $sum += $freq{$item};
    $chosen = $item if rand($sum) < $freq{$item};
}

这里,$sum对应于行计数器$.和Cookbook版本中$freq{$item}的常量1.

如果您要选择大量加权随机样本,可以通过一些准备加快一点(注意这会破坏%freq,所以如果你想保留它,请先复制一份):

# first, scale all frequencies so that the average frequency is 1:
my $avg = 0;
$avg += $_ for values %freq;
$avg /= keys %freq;
$_ /= $avg for values %freq;

# now, prepare the array we'll need for fast weighted sampling:
my @lookup;
while (keys %freq) {
    my ($lo, $hi) = (sort {$freq{$a} <=> $freq{$b}} keys %freq)[0, -1];
    push @lookup, [$lo, $hi, $freq{$lo} + @lookup];
    $freq{$hi} -= (1 - $freq{$lo});
    delete $freq{$lo};
}

现在,要从准备好的分布中绘制随机加权样本,您只需执行以下操作:

my $r = rand @lookup;
my ($lo, $hi, $threshold) = @{$lookup[$r]};
my $chosen = ($r < $threshold ? $lo : $hi);

(这基本上是Marsaglia,Tsang&Wang(2004),"Fast Generation of Discrete Random Variables",J.Stat.Soft.11(3),最初由AJ Walker(1974)所述的方形直方图方法.)