シェイクスピアの本をいくつか Perl スクリプトに入力した後、キーとして 26 文字の英字とテキスト内での出現回数を値として持つハッシュを取得しました。
%freq = (
a => 24645246,
b => 1409459,
....
z => 807451,
);
そしてもちろん、すべての文字の総数 -$total変数で言ってみましょう。
16 個のランダムな文字を保持する文字列を生成するための良いトリックはありますか (文字はそこで数回発生する可能性があります) - 使用頻度によって重み付けされますか?
Ruzzle に似た単語ゲームで使用するには:
Perlクックブックの領収書で提案されているように、ファイルからランダムな行を選択するようなエレガントなもの：
rand($.) < 1 && ($line = $_) while <>;
私は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を選択すると、次の確率が得られます。
それがまさに私たちが望んでいることです。
ランダムな行を選択するための Perl クックブックのトリック ( perlfaq5にもあります) は、加重サンプリングにも適用できます:
my $chosen;
my $sum = 0;
foreach my $item (keys %freq) {
$sum += $freq{$item};
$chosen = $item if rand($sum) < $freq{$item};
}
ここでは、Cookbook バージョン$sumの行カウンター$.と$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) による Square Histogram 法です。)
最初に、頻度の実行中の合計の表を作成できます。したがって、次のデータがある場合：
%freq = (
a => 15,
b => 25,
c => 30,
d => 20
);
現在の合計は次のようになります。
%running_sums = (
a => 0,
b => 15,
c => 40, # 15 + 25
d => 70, # 15 + 25 + 30
);
$max_sum = 90; # 15 + 25 + 30 + 20
重み付けされた頻度で単一の文字を選択するには、 の間の数値を選択する必要があります[0,90)。その後、その文字を含む範囲について running_sum テーブルで線形検索を実行できます。たとえば、乱数が 20 の場合、適切な範囲は 15 ～ 40 で、これは文字 'b' です。O(m*n)線形検索を使用すると、m が必要な文字数、n がアルファベットのサイズ (したがって、m=16、n=26)の合計実行時間が得られます。これは基本的に @default ロケールが行うことです。
線形検索の代わりに、running_sum テーブルで二分検索を実行して、切り捨てられた最も近い数値を取得することもできます。これにより、合計実行時間が になりO(m*log(n))ます。
ただし、 m 文字を選択する場合はO(m*log(n))、特に ifよりも高速な方法がありn < mます。まずm、ソートされた順序で乱数を生成します (これは でソートせずに実行できます)。次に、ソートさO(n)れた乱数のリストと実行中の合計のリストの間の範囲について線形マッチングを行います。これにより、総実行時間はO(m+n). コード全体が Ideone で実行されています。
use List::Util qw(shuffle);
my %freq = (...);
# list of letters in sorted order, i.e. "a", "b", "c", ..., "x", "y", "z"
# sorting is O(n*log(n)) but it can be avoided if you already have
# a list of letters you're interested in using
my @letters = sort keys %freq;
# compute the running_sums table in O(n)
my $sum = 0;
my %running_sum;
for(@letters) {
$running_sum{$_} = $sum;
$sum += $freq{$_};
}
# generate a string with letters in $freq frequency in O(m)
my $curmax = 1;
my $curletter = $#letters;
my $i = 16; # the number of letters we want to generate
my @result;
while ($i > 0) {
# $curmax generates a uniformly distributed decreasing random number in [0,1)
# see http://repository.cmu.edu/cgi/viewcontent.cgi?article=3483&context=compsci
$curmax = $curmax * (1-rand())**(1. / $i);
# scale the random number $curmax to [0,$sum)
my $num = int ($curmax * $sum);
# find the range that includes $num
while ($num < $running_sum{$letters[$curletter]}) {
$curletter--;
}
push(@result, $letters[$curletter]);
$i--;
}
# since $result is sorted, you may want to use shuffle it first
# Fisher-Yates shuffle is O(m)
print "", join('', shuffle(@result));