1994年の論文

summary

binary indexed treeは 動的算術圧縮を支援するために必要である 累積頻度を維持するために提示された新しい手法. table elementのindexを並列にbinary表現する 累積頻度を部分に分解することが基になっている. データ構造を横断する操作は indexのbinary codingが基になっている. 以前の方法で比較すると, よりコンパクトなデータとシンプルなコードを用いることで binary indexed treeは速い. すべての操作のaccess timeは 定数時間か table sizeの対数時間に比例する. コンパクトなデータ構造と一緒に これは large symbol alphabetsにとって部分的に適切な新しい手法を 作る.

Introduction

適応算術データ圧縮の 大部分のコストは 継続するシンボルの範囲を削減するのに必要な 累積頻度のテーブルの のメンテナンスである. Neal and Clearyは 最も頻度の高い記号を 最も近い場所に置いて置くことのできる move-to-front mappingを提供することで プログラムを簡単にした. それは 歪められたアルファベットでも よく動く. しかし、 まして より記号頻度の区域を 整えられたものより 効率的とは言えない. Moffatは linear-timeですべてのsymbolに到達できる 木の構造を記述した. Jonesは 頻度テーブルを取り扱い、 最適化されたデータ構造を 提供するために splay trees を用いた. この３つのテクニック MTF, HEAP, SPLAYは それぞれ この論文で参照されるでしょう.

全ての場合に置いて 彼らは データ構造の中の 使用されているシンボルの 頻度を保ち続けようとした.

この論文では、 一つの配列のみを頻度を保存するために使う 新しい手法を記述している. しかし、 注意深く選ばれたパターンの中で それらを保存することは indexの要素の中の 1bitの数に比例する. このコストは 更新とテーブルへの問い合わせ の両方に対してである. 他の方法と比較すると 単純でコンパクトであり速い. さらにデータの再編や移動の必要がない.

Principles

基本的なアイデアは, ちょうど整数が 2つの適切な力の合計であるように 累積頻度を 累積するsubfrequenciesの組の合計が適切になるような 代表にすることである. つまり、 もしindexが2bitを含んでいたら 2つの頻度を含み、 もし8bit含んでいたら8つの頻度をもっている. 図1に16サイズのテーブルを示す.

最初の行は単純にindexである. 2行目はテーブルの中身を示している. 例えば4というindexの要素は1から4までの頻度の要素の合計を含んでいる. さらに， indexが6の要素は5~6までの頻度の合計である. 最後の三つの行は, 実際の例を表している. 以下の議論の通り， 保存された値とitem頻度は二つの配列VとFをそれぞれ考慮している.

基本的な操作は 古いindexから 最低で一つのindexを除去することで 新しいindexを計算を起こす. そして このオペレーションをindexが0になるまで繰り返す. 最初の11のindexでは，11, 10, 8, 0の列を算出する. 11番目の累積頻度を読むと 合計はV[11] + V[10] + V[8] + V[0]という計算で成り立っている事がわかる. テーブルの二行目を戻って参照すると， この列がF[11] + F[9..10] + F[1..8] + F[0]という頻度で分けて見る事ができる. 最後の値つまり，F[0..11]は求められた結果である．

indexed methodは 図2で表されているような 部分頻度のテーブルの以内で 木を生成する. それぞれのbarは 配列の要素の 頻度の範囲を表している. 任意のノードからルートまで木を横切る事は必要な頻度の全てを足し合わせれば良いこと は明確である.

代わりに, 従来の形を描く事もできる. 実際にそのテーブルは 二つの異なる木である.