古い記事
ランダムジャンプ
新しい記事
ジップの法則 (Zipf's law) とは、「出現頻度がk番目に大きい要素が全体に占める割合が1/kに比例するという経験則」です (Wikipedia より)。
そのジップの法則に準拠した出現頻度を持つ要素のランダム順なリストを作成するスクリプトをPerlで書いてみました。

■コード(zipf-gen.pl):
#!/usr/bin/perl
use strict;
use warnings;
my $rank = shift || 1000;

my $sum;
my @sums;
for (my $i = 0; $i < $rank; $i++) {
    $sum += 1/($i+1);
    $sums[$i] = $sum;
}

while (1) {
    my $value = rand() * $sum;
    my $idx = bsearch($value);
    print $idx+1,"\n";
}

sub bsearch {
    my ($value) = @_;
    my $head = 0;
    my $tail = $rank - 1;
    while ($head <= $tail) {
        my $where = int(($head + $tail) / 2);
        if ($value <= $sums[$where]) {
            $tail = $where - 1;
        } else {
            $head = $where + 1;
        }
    }
    return $head;
}

■実行例
% ./zipf-gen.pl | head
438
333
859
48
180
27
200
64
572
1
% ./zipf-gen.pl | head -10000 | sort -n | uniq -c | head -20
1355 1
 666 2
 406 3
 341 4
 290 5
 250 6
 189 7
 156 8
 152 9
 123 10
 110 11
 111 12
 128 13
  96 14
 110 15
  90 16
  86 17
  71 18
  80 19
  66 20

完全に 1/k にはなりませんが、まあ「だいたいあってる」ということで。
あとコード中の bsearch は「アルゴリズム百選 by dankogai」を参考にしました。

- アルゴリズム百選 - 二分探索(binary search)
http://blog.livedoor.jp/dankogai/archives/50961989.html

偽ジップ


この記事は間違いがあったため5月11日に全面的に書き直しています。
最初に公開したコードがそもそもジップの法則に準拠してませんでした。
ジップの法則だと順位 k に対して 1/k なのですが、1/2^k としてしまいました。
自戒を込めて書き直す前のコードと実行例を載せておきます。

■コード(nise-zipf-gen.pl):
#!/usr/bin/perl
use strict;
use warnings;
while (1) {
    my $id = 1;
    $id++ while rand() < 0.5;
    print "$id\n";
}

■実行例
% ./nise-zipf-gen.pl | head
2
2
1
1
4
1
1
2
1
2
% ./zipf-gen.pl | head -10000 | sort -n | uniq -c
4978 1
2513 2
1221 3
 647 4
 317 5
 161 6
  84 7
  34 8
  19 9
   9 10
   8 11
   3 12
   4 14
   2 15

用途


何に使うかと言うと……。

自然言語における単語の出現頻度や共起頻度を効率的にカウントする手法のテストデータとして使います。
近いうちに解説記事を書きます。