簡潔データ構造
n + o ( n ) {\displaystyle n+o(n)} の領域のアプローチは、 [ n ) {\displaystyle [n)} のなかには異なる m {\displaystyle m} -部分集合が(言い換えるなら、長さ n {\displaystyle n} でちょうど m {\displaystyle m} 個の1があるビット列が) ( n m ) {\displaystyle \textstyle {\binom {n}{m}}} 個あることに注意すると、さらに改善できる。このとき、 B {\displaystyle B} を保持するのに必要なビット数の情報理論的下界は、 B ( m , n ) = ⌈ lg  ( n m ) ⌉ {\displaystyle \textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil } である。
実用上は、ルックアップ表 R p {\displaystyle R_{p}} をビット命令とより小さい表で置き換え、小ブロックで立っているビットの数を調べるようにすることができる。多くの場合、こうすることで大きなデータセットで簡潔データ構造を用いる際の、キャッシュミスの増大とそれによって起こるルックアップ表がキャッシュから追い出されるという問題に対処できる。select質問は、rankに用いたものと同じ補助データ構造と二分探索とを合わせることで容易にサポートできるが、そのやり方では最悪の場合 O ( lg  n ) {\displaystyle O(\lg n)} の時間がかかる。 3 n / lg  lg  n + O ( n lg  n lg  lg  n ) = o ( n ) {\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)} ビットの追加領域を用いる、より複雑なデータ構造により、selectは定数時間でサポートできる。こうした解決法の多くでは、実用上、漸近的な特長が効果を発揮する至らない場合、 O ( ⋅ ) {\displaystyle O(\cdot )} 記法に隠れた定数が支配的となる。その場合、長ワード命令とワードサイズに揃えたブロックを利用した実装のほうが効率的であることが多い。
簡潔索引つき辞書(簡潔ビットベクトル、完備辞書とも呼ぶ)は、rank/select 辞書とも呼ばれ、二分木、 k {\displaystyle k} 分木、多重集合や、接尾辞木、接尾辞配列などの多数の簡潔表現手法の基礎をなしている。基本的な問題設定は、 U = [ 0 ... n ) = { 0 , 1 , ... , n − 1 } {\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}} の空間中で部分集合 S {\displaystyle S} を保持するというものであり、通常 B [ i ] = 1 {\displaystyle B[i]=1} iff i ∈ S {\displaystyle i\in S} とするビット配列として部分集合を表現する。索引つき辞書は通常の辞書の操作(参照、および動的辞書の場合は挿入と削除)に加えて、次の二つの操作をサポートする。
r a n k q ( x ) = | { k ∈ [ 0 ... x ) : B [ k ] = q } | {\displaystyle \mathbf {rank} _{q}(x)=|\{k\in [0\dots x):B[k]=q\}|}
s e l e c t q ( x ) = min { k ∈ [ 0 ...