1行1ラベル形式で、
1万種類のラベルを持つ、
100万行のデータがあるとします
（ラベルの頻度分布はジップの法則にだいたい準拠するとします）。

各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。（1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。）

しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。

そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。

そこで登場するのが「誤り許容カウント法(lossy count method)」。

低頻度のものを途中で適宜捨てていくことで必要なメモリ領域を小さくす
る方法なのです。
簡単に言うと、入力データをブロック単位に分け、各ブロックの読み込み後に低頻度のハッシュエントリを捨てる感じです。もちろん「現ブロックでは頻度ゼロだけど過去の実績があるから捨てない」などの要素もあります。

詳しくは「オンラインアルゴリズムとストリームアルゴリズム」[2010-05-11-1]の第6章をご参照ください。

■徳山豪 / オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ 5 数理技法編)


以下、サンプルプログラムで実演解説していきます。

サンプルデータ

まずは実演で使うサンプルデータを準備します。
1行1ラベル形式で、1万種類のラベルを持つ、100万行のデータで、ジップの法則に従うものを用意します。
先日の記事「ジップの法則に準拠した出現頻度を持つ要素のランダム順なリストを作成する」[2010-05-08-6]の zipf-gen.pl を使って生成します。

% ./zipf-gen.pl 10000 | head -1000000 > samp.txt
% head samp.txt 
32
2
105
3
33
586
1
1
924
247

単純カウント

まずは単純な方法でカウントしてみます。
全てをハッシュに入れてカウントする Perl プログラムです。

■コード(naive-freq.pl)：

#!/usr/bin/perl
use strict;
use warnings;
my $gamma = 0.005;
my %count;
my $N;

while (<>) {
    chomp;
    next if /^\s*$/;
    $count{$_}++;
    $N++;
}

foreach my $k (sort {$count{$b} <=> $count{$a}} keys %count) {
    last if $count{$k} < $gamma * $N;
    print "$k $count{$k}\n";
}

print "max hash size = ".scalar(keys %count)."\n";

■実行例

% ./naive-freq.pl samp.txt
1 102069
2 51389
3 33944
4 25432
5 20513
6 16856
7 14365
8 12780
9 11436
10 10353
11 9108
12 8528
13 8039
14 7259
15 6931
16 6377
17 6028
18 5704
19 5332
20 5050
21 5002
max hash size = 10000

出力フォーマットは、第1カラムがラベルで第2カラムがそのラベルの出現頻度です。
最後の "max hash size" はプログラム内で使用する最大ハッシュエントリ数で、実行時のメモリ使用量の目安となります。ラベルは1万種類なので当然10000になります。

LCMカウント

「誤り許容カウント法(lossy count method)」によるカウントプログラムです。
「オンラインアルゴリズムとストリームアルゴリズム」[2010-05-11-1]での記述の通りに Perl で実装したものです。

■コード(lcm-freq.pl)：

#!/usr/bin/perl
use strict;
use warnings;
my $gamma = 0.005;
my $epsilon = 0.004;
my $b_current = 1;
my %count;
my $N;
my $max_hash_size = 0;

while (<>) {
    chomp;
    next if /^\s*$/;
    add($_);
    $N++;
    if ($N % int(1/$epsilon) == 0) {
        next_backet();
    }
}

foreach my $k (sort {$count{$b}{f} <=> $count{$a}{f}} keys %count) {
    if ($count{$k}{f} >= ($gamma - $epsilon) * $N) {
        print "$k $count{$k}{f} $count{$k}{d}\n";
    }
}
print "max hash size = $max_hash_size\n";

sub add {
    my ($k) = @_;
    if (not $count{$k}) {
        $count{$k}{f} = 1;
        $count{$k}{d} = $b_current - 1;
    } else {
        $count{$k}{f}++;
    }
}

sub next_backet {
    my $hash_size = scalar(keys %count);
    $max_hash_size = $hash_size  if $max_hash_size < $hash_size;
    foreach my $k (keys %count) {
        if ($count{$k}{f} <= $b_current - $count{$k}{d}) {
            delete $count{$k};
        }
    }
    $b_current++;
}

■実行例

% ./lcm-freq.pl samp.txt
1 102069 0
2 51389 0
3 33944 0
4 25432 0
5 20513 0
6 16856 0
7 14365 0
8 12780 1
9 11436 0
10 10353 0
11 9108 0
12 8527 1
13 8039 0
14 7259 0
15 6929 4
16 6377 1
17 6027 1
18 5702 2
19 5327 5
20 5047 6
21 5002 0
22 4601 16
23 4379 11
24 3945 344
25 3632 421
max hash size = 203

出力フォーマットは、第1カラムがラベル、第2カラムがそのラベルの出現頻度、第3カラムがバケット番号($b_current)です。
バケット番号が0ではないやつは頻度に若干の誤差があるかもしれないことを意味します（番号が小さい場合は誤差はないです）。
誤差の許容範囲は $epsilon で調整します。
この辺は本を読んでください。

プログラム内で使用する最大ハッシュエントリ数 "max hash size" が 10000 と比べかなり小さくなっていることが分かります。
少ないメモリ容量で実行できるということです。

比較

最大ハッシュサイズの比較です。
前述の例では50倍ほどの差があります（実際は各ハッシュエントリが持つデータ量が違うのですがそれでも25倍の差）。
LCM の gamma、epsilon で調整できます。

	単純カウント	LCMカウント
最大ハッシュサイズ	10000	203

カウント結果の比較です。
LCM側でバケット番号が0じゃないものは太字にしています。

ラベル	頻度（単純カウント）	頻度（LCMカウント）
1	102069	102069
2	51389	51389
3	33944	33944
4	25432	25432
5	20513	20513
6	16856	16856
7	14365	14365
8	12780	12780
9	11436	11436
10	10353	10353
11	9108	9108
12	8528	8527
13	8039	8039
14	7259	7259
15	6931	6929
16	6377	6377
17	6028	6027
18	5704	5702
19	5332	5327
20	5050	5047
21	5002	5002

おわりに

巨大データを扱うとなると、「マシンが何台も必要！」とか「MapReduce で Hadoop がホゲホゲ！」とか「クラウドで5万円！」とかいろいろ心配になりがちです。
しかし、高頻度のものを取り出したいだけならば、貧弱なマシン環境でもなんとかなる場合があります。
ウェブサーバのログ解析もこういう高頻度チェック用途ならサクッと行けそうです。

贅沢なマシン環境の整備がなかなか難しい週末プログラマーやウェブベンチャーの方！
「誤り許容カウント法(lossy count method)」などのストリームアルゴリズムは要チェックですよ！

■徳山豪 / オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ 5 数理技法編)

(ref. [2010-05-11-1])

ref.
- lossy countingアルゴリズム (機械学習の「朱鷺の杜Wiki」)
http://ibisforest.org/index.php?lossy%20counting%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
- [O] イプシロン劣シノプス性を保持した頻度カウント
http://diary.overlasting.net/2010-04-23-3.html