Binary Indexed Tree (Fenwick Tree)

圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。

累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。

Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更新の計算時間が有利なだけでなく、空間も n しか要求しません。配列で二分木を実現して、累積頻度表の各種操作の計算量を木の高さに抑えることで対数時間を実現します。BIT の詳しい解説は参考文献を参照してください。

さて、こんな風に書くとなんだか実装が難しそうなのですが、BIT は実装が非常に簡単なのが利点であり面白いところです。Algorithm::BIT という perl の Binary Indexed Tree のライブラリを作ってみました。

実装はこれだけです。

package Algorithm::BIT;
use strict;
use warnings;
use integer;

use Carp qw/croak/;

sub new {
    my ($class, $n) = @_;
    my $self = bless [], $class;
    for (my $i = 0; $i < $n; $i++) {
        $self->[$i] = 0;
    }
    return $self;
}

sub read {
    my ($self, $idx) = @_;

    if ($idx > @$self) {
        croak 'assert: index overflow';
    }

    my $sum = 0;
    while ($idx > 0) {
        $sum += $self->[$idx];
        $idx = $idx & $idx - 1;
    }

    return $sum;
}

sub update {
    my ($self, $idx, $val) = @_;
    my $max = @$self;
    while ($idx <= $max) {
        $self->[$idx] += $val;
        $idx += ($idx & -$idx);
    }
}

1;

使い方は

use Algorithm::BIT;

my $bit = Algorithm::BIT->new(16);

$bit->update(1, 10);
$bit->update(2, 1);
$bit->update(5, 1);

is $bit->read(1), 10;
is $bit->read(2), 11;
is $bit->read(5), 12;

といった具合です。

なんでこれだけで O(lg n) で累積頻度表を管理できるのか、ですが肝になるのは

    while ($idx > 0) {
        $sum += $self->[$idx];
        $idx = $idx & $idx - 1;
    }

の部分です。この処理が配列で表現された二分木を traverse しているところにあたります。BIT が巧妙なのは、例えば索引 11 の累積頻度が欲しい場合、11 の節から根まで traverse しながら適切な節の値を足し込む(これで各節の左部分木の累積値を求めたことになる)のですが、この traverse が次のルールで完了するように木を構成しているところです。

  • 11 を二進表記にすると 1011
  • 1011 の二進表記の最右の 1 のビットを 0 にする ･･･ 1010 → 10
  • 同様に 1010 の最右の 1 のビットを 0 にする ･･･ 1000 → 8
  • 1000 を同様に扱うと 0000 になって 0、ということで終了

このルールに従って、11 → 10 → 8 の索引の配列の要素にアクセスして、値を足し込めば索引 11 の累積頻度が得られます。この最右の 1 のビットを 0 にするという演算は $idx & $idx - 1 だけで実装できてしまいます。ところでこれは 1 が立っているビットの回数だけ加算をしていることになりますから、2進表現で任意の整数を表現するのと、考え方としては似たようなをやっているとも言えます。最初に見たとき、巧みすぎて思わず感心してしまいました。

参考文献, URL

[1] が P.Fenwick 氏による BIT のの論文です。

いつもお世話になっている [2] では適応型 Range Coder の効率アップに BIT を使う中で、詳しい解説があります。とても分かりやすいです。TopCoder のサイトにある [3] にも詳細な解説があります。プログラミングコンテストの問題を解く時にも使えるデータ構造なんですね。Algorithm::BIT の実装は [3] を参考にしました。

[4] にも BIT について概要が記載されています。[4] を読んでいたら BIT の話が出てきて、そういえば以前にわけもわからず実装した物があったな、と蔵出ししてきたのが今回のコードです。