簡潔データ構造

Summarize Timeline Top Qs Fact Check

簡潔索引つき辞書(簡潔ビットベクトル、完備辞書とも呼ぶ)は、rank/select 辞書とも呼ばれ、二分木、${\displaystyle k}$分木、多重集合^[2]や、接尾辞木、接尾辞配列などの多数の簡潔表現手法の基礎をなしている^[3]。基本的な問題設定は、 ${\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}}$の空間中で部分集合${\displaystyle S}$を保持するというものであり、通常 ${\displaystyle B[i]=1}$ iff ${\displaystyle i\in S}$ とするビット配列として部分集合を表現する。索引つき辞書は通常の辞書の操作（参照、および動的辞書の場合は挿入と削除）に加えて、次の二つの操作をサポートする。

• ${\displaystyle \mathbf {rank} _{q}(x)=|\{k\in [0\dots x):B[k]=q\}|}$
• ${\displaystyle \mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}}$

ただし、${\displaystyle q\in \{0,1\}}$とする。

ある単純な表現方法 ^[4] では ${\displaystyle n+o(n)}$ ビットの領域（元のビット配列と、${\displaystyle o(n)}$ の補助データ構造）を使って rank と select を定数時間でサポートできる。この方法はRange Minimum Query（英語版）と似た考え方に基づいており、固定サイズの部分問題に行き着くまでに定数回数の再帰呼び出しだけで済む。ビット配列 ${\displaystyle B}$ はサイズ ${\displaystyle l=\lg ^{2}n}$ の大ブロックとサイズ${\displaystyle s=\lg n/2}$の小ブロックに分割される。大ブロック一つごとに、最初のビットのrankが別の表 ${\displaystyle R_{l}[0\dots n/l)}$ に保持される。この表の各エントリには ${\displaystyle \lg n}$ ビットが必要で、合計 ${\displaystyle (n/l)\lg n=n/\lg n}$ ビットの領域を使う。大ブロックの中では、もう一つの表 ${\displaystyle R_{s}[0\dots l/s)}$ を使って、そのブロックに含まれる ${\displaystyle l/s=2\lg n}$ 個の小ブロックのrankを保持する。ここでの違いは、各エントリで、そのエントリが入っている大ブロックの最初のビットのrankからの差分だけを保持すればよいので、 ${\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n}$ ビットだけが必要になることである。このため、この表は合計 ${\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n}$ ビットになる。そして、小ブロック内の ${\displaystyle i\in [0,s)}$ ビットに対しては、${\displaystyle s}$ ビットの全てのビット列に対するrank質問の答えを保持するルックアップ表 ${\displaystyle R_{p}}$ を使うことができる。このテーブルには ${\displaystyle 2^{s}\lg s=O({\sqrt {n}}\lg \lg n)}$ ビットの領域を必要とする。 これらの補助表は ${\displaystyle o(n)}$ の領域だけを使うため、このデータ構造はrank質問を ${\displaystyle O(1)}$ 時間と ${\displaystyle n+o(n)}$ ビットの領域でサポートする。

次の定数時間アルゴリズムを用いると、${\displaystyle \mathbf {rank} _{1}(x)}$の質問に定数時間で答えることができる。

${\displaystyle \mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]}$

実用上は、ルックアップ表 ${\displaystyle R_{p}}$ をビット命令とより小さい表で置き換え、小ブロックで立っているビットの数を調べるようにすることができる。多くの場合、こうすることで大きなデータセットで簡潔データ構造を用いる際の、キャッシュミスの増大とそれによって起こるルックアップ表がキャッシュから追い出されるという問題に対処できる^[5]。select質問は、rankに用いたものと同じ補助データ構造と二分探索とを合わせることで容易にサポートできるが、そのやり方では最悪の場合 ${\displaystyle O(\lg n)}$ の時間がかかる。${\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)}$ ビットの追加領域を用いる、より複雑なデータ構造により、selectは定数時間でサポートできる^[6]。こうした解決法の多くでは、実用上、漸近的な特長が効果を発揮する至らない場合、${\displaystyle O(\cdot )}$記法に隠れた定数が支配的となる。その場合、長ワード命令とワードサイズに揃えたブロックを利用した実装のほうが効率的であることが多い^[7]。

${\displaystyle n+o(n)}$ の領域のアプローチは、 ${\displaystyle [n)}$ のなかには異なる ${\displaystyle m}$-部分集合が（言い換えるなら、長さ${\displaystyle n}$でちょうど${\displaystyle m}$個の1があるビット列が）${\displaystyle \textstyle {\binom {n}{m}}}$ 個あることに注意すると、さらに改善できる。このとき、${\displaystyle B}$を保持するのに必要なビット数の情報理論的下界は、${\displaystyle \textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil }$である。この下界を達成する（静的な）簡潔辞書は存在し、 必要とする領域は${\displaystyle {\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))}$ である^[8]。そのデータ構造はさらに、${\displaystyle {\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)}$の領域量でrankとselectをサポートするように拡張することができる^[2]。この下界は、辞書を保持する領域を ${\displaystyle {\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})}$ とし、質問に必要な時間を ${\displaystyle O(t)}$ とすることで領域と時間のトレードオフに帰着させることができる^[9]。