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