こんにちは。レトリバのリサーチャーの木村@big_wingです。COVID-19の影響でテレワークが推進されていますが、現在私も奈良県の生駒市からフルリモートで業務を行っています。 今回は簡潔データ構造について2回目の記事で、あらゆる簡潔データ構造の基本となるビットベクトルに対する簡潔データ構造を紹介します。 1回目の記事はこちらです。
簡潔データ構造をさらに詳しく知りたい方向けの紹介として、Navarro氏の本、日本語で書かれたものとしては定兼氏の本と岡野原氏の本があります。
ビットベクトルに対する簡潔データ構造
最初にビットベクトルに対する簡潔データ構造を扱うモチベーションについて簡単に説明します。 簡潔データ構造の枠組みにおいて文字列、木、グラフなど様々な離散データ構造はまず、0,1のビットベクトルとしてエンコードされます。 その後エンコードされたビットベクトル上で演算を行うことで、例えば木であれば親ノードにアクセスしたり、子ノードにアクセスしたりといった演算を実現します。 このように複雑な離散構造やそれに対する演算もビットベクトル上の演算に還元されるため、ビットベクトルに対する簡潔データ構造はあらゆる簡潔データ構造の基本となっており、とても重要です。
ビットベクトルに対する演算
今、, を長さのビットベクトルとします。このビットベクトルに対して、
- access: を返す
- rank: の中に含まれるの数を返す
- select: の先頭から見て番目に出現するの位置を返す
といった演算を定義します。添字が多くてぱっと見理解しにくいので、具体例で確認してみましょう。 下の図において、上段がビットベクトルの位置を表すインデックスで、下段がビットベクトルの要素です。
i: 1 2 3 4 5 6 7 8 9 B: 0 1 1 1 0 1 0 0 1
accessの例
まず最も簡単なaccessについて見てみましょう。accessは位置に対応するビットベクトルの要素を返す演算なので上の図においては、access、accessとなります。
rankの例
次にrankです。今、rankという演算について見てみましょう。 これはrankの定義からの中に含まれる1の数となります。 においては、、が1となり、の中に含まれる1の数は3個です。よって rankとなります。
同様にrankという演算について見てみましょう。これはrankの定義からの中に含まれる0の数となります。 においては、が0となり、の中に含まれる0の数は2個です。よって rankとなります。
また少し考えてみるとrankとrankの間にはrankrankの関係が成り立っていることがわかります。これによってrankとrankのうち片方の値が得られればもう一方の値も直ちに得ることができます。
selectの例
最後にselectです。今、selectという演算について見てみましょう。 これはselectの定義から の先頭から見て2番目に出現する1の位置です。図を見てみると の先頭から見て2番目に出現する1の位置は3となるので、selectとなります。同様にselectとなります。
ビットベクトルの情報理論的下限
1回目の記事の復習となりますが、簡潔データ構造を定量的に定義するにあたって必要な情報理論的下限をビットベクトルに対して考えてみましょう。 今、要素数がである集合に対して情報理論的下限は ビットと定義されます()。
長さのビットベクトルは各要素が2通りの値を取るため、この集合の要素数はです。 そのため情報理論的下限はビットとなります。
よって上記に漸近するビットの空間領域でaccess、rank、selectの演算を高速に行うデータ構造を得ることが目標です。
ビットベクトルに対する簡潔データ構造の実現
最初に結論を述べると、長さのビットベクトルに対してビットの空間領域で、access、rank、selectの演算を定数時間で実現するデータ構造が存在します(論文)。
accessはビットのビットベクトルそのものを保持すれば自明に定数時間で行うことができます。残りはrankとselectですが、selectはrankに比べてデータ構造が非常に複雑となるため、今回はrankのみ扱います。また先に述べたようにrankrankの関係が成り立つため、 以降ではビットの空間領域でrank演算を定数時間で実現するデータ構造について紹介します。
rankの実現: 着想
具体的なデータ構造の説明の前に、以下のような2つの極端な状況を考えてみましょう。
- ビットベクトル以外に補助的なデータ構造を何も持たない
- ビットベクトルのすべての位置に対してrankの値を保存する
まず1. の状況です。この場合ビットベクトル以外に何も持たないことから、データ構造のサイズは全体でビットです。しかし補助的な情報が何もないため、rankを計算する際にはビットベクトルを先頭から番目まで読み込む必要があり、時間計算量はとなってしまい、定数時間で演算を行うことができません。
次に2. の状況です。この場合はすべての位置に対してrankの値を保持しているので、rankの値は定数時間で得ることができます。一方でrankであることから、一つのrankの値を表現するにはビットが必要となります。そのため2. の場合に補助的に必要となる空間計算量は ビットとなってしまい、情報理論的下限を大きく超えるメモリを必要とします。
つまりrankの値を全く保持しない方針や全て保持する極端な方針では、時間計算量と空間計算量のいずれかで問題が発生します。 そこでrankの値をほどほどに保持すればよいのではないか?という気持ちになり、実際にそのような方針で所望のデータ構造が実現できます。
rankの実現: 2種類のブロックによる分割
rankの値をほどほどに保持するために、大ブロックとそれをさらに分割した小ブロックの2つを用いてビットベクトルを分割します。
- 大ブロック: 長さ 、番目()の大ブロックはに対応
- 小ブロック: 長さ 、を含む小ブロックの番号はで、に対応
ここで具体的なの値はひとまずおいておきます。このの設定が空間計算量に大きな影響を与えますが、説明の都合上具体的な値は最後の方で述べます。 文字で見るとぱっと見よくわかりませんので具体例で見てみましょう。
上の図はビットベクトルをとして分割した例になります。まず全体をの長さで大ブロックに分割し、各大ブロックをの長さで小ブロックに分割します。
次にrankの値の計算のために、分割した大ブロックと小ブロックに付随した2つの配列 とを用意します。
- : 先頭から番目までの大ブロックに含まれる1の数を保持する
- : 番目の小ブロックが属する大ブロックにおいて、属する大ブロックの先頭から番目の小ブロックまでに含まれる1の数を保持する
こちらも具体例を見てみましょう。
上の図は先程の例において具体的に とを求めたものになります。
は0番目の大ブロックまでに含まれる1の数ですが、0番目のブロックは存在しないのでとなります。は番目の大ブロックまでに含まれる1の数です。1番目の大ブロックの中の1の数を数えると5個なのでとなります。
についても確認してみましょう。は1番目の大ブロックに属します。1番目の大ブロックの先頭から番目の小ブロックまでに含まれる1の数は3個なのでとなります。また同様には2番目の大ブロックに属します。2番目の大ブロックの先頭から番目の小ブロックまでに含まれる1の数は2個なのでとなります。
さてこれら2つの配列とを用いることでrankを定数時間かつビットの空間領域で求めることができます。 計算の方針は
rank = 自身の属する大ブロックまでの累積和 + 大ブロックの先頭から自身の属する直前の小ブロックまでの累積和 + 自身の属する小ブロックの先頭からの残り
です。ここで自身の属する大ブロックまでの累積和がに、直前の小ブロックまでの累積和がに対応しています。 また自身の属する小ブロックは、自身の属する大ブロックはで求めることができ、上の計算式は、
rank 自身の属する小ブロックの先頭からの残り
と書くことができます。今、図のビットベクトルにおいてrankを上記の式で求めてみましょう。 図において位置17は番目の小ブロック、番目の大ブロック、6番目の小ブロックの先頭から2ビット目に該当します。 まず2番目の大ブロックまでの累積和はの定義からです。次に2番目の大ブロックの先頭から直前の番目の小ブロックまでの累積和はの定義からです。最後に自身の属する6番目の小ブロックの先頭から位置17までの1の数は1個です。以上から、
rank
と計算することができます。これでなんとなくrankを定数時間で計算できる気持ちになってもらえたでしょうか? 具体的な計算を優先したため、計算式の残りの部分の計算が定数時間で実行できるのか?といったところや、との空間計算量が ビットなのか?というところはあやふやにしてきました。 そこで最後に途中お茶を濁した大ブロックと小ブロックの長さを具体的に設定することにより、上記の方針でrankを定数時間かつビットの空間領域で計算できることを示します。
rankの実現: 時間計算量と空間計算量
いきなり天下り的ですが、
と設定して解析を行います。
最初に時間計算量です。rankの計算式の自身の属する小ブロックの先頭からの残りの部分の時間計算量ですが、これは定数時間で行うことができます。 なぜならば今と設定したため、小ブロックの先頭からの残りの長さは高々です。これはWord RAMモデルの仮定から定数時間で読み込むことができ、かつビット演算も定数時間で実行でき、POPCOUNTというCPU命令を使うことで高速に定数時間で残りの1の数を計算できます。よっての加算と合わせてrankは定数時間で計算することができます。
次に空間計算量です。まずについて考えます。今であることから、各を表現するにはビットが必要となります。またと設定したことから配列の要素数はとなり、の空間計算量はビットです。
次にについて考えます。今であることから、各を表現するにはビットが必要となります。また配列の要素数はとなり、設定したとを代入することによりの空間計算量はビットです。
したがってとを合わせた空間計算量にはビットです。 以上からビットの空間領域でrank演算を定数時間で実現するデータ構造を実現することができました、お疲れさまでした。
まとめ
簡潔データ構造の紹介の2回目である今回は、ビットベクトルに対する簡潔データ構造について紹介しました。 ビットベクトルに対する簡潔データ構造はあらゆる簡潔データ構造の基本となり、とても重要です。 今回はrank演算についてのみ紹介しましたが、select演算を実現するためのデータ構造や、あるいはビットベクトルが非常にスパースな場合のより効率的なデータ構造の話など奥深い話はまだまだたくさんあります。また今回は理論的な側面を紹介しましたが実際の実装になると注意すべき点や工夫すべき点が様々あります。実装の一つとして様々な種類の簡潔データ構造が実装されているライブラリを紹介します。興味のある方は最初に紹介した本や、最後に紹介した実装などに触れてみてください!次回はビットベクトルの拡張となる一般の文字列に対する簡潔データ構造について紹介する予定です。