簡潔データ構造
可変長のアイテムの列を符号化する必要がある場合は、単に個々のアイテムを区切り記号なしで順に並べればよい。それと別に、アイテムの始まりの位置に1を、それ以外の位置に0を置いた二値配列を符号化する。この補助ビット列で s e l e c t {\displaystyle select} 関数を用いるとあるインデクス値のアイテムの開始位置を高速に求めることができる。
別の例として二分木の表現がある。ノード数 n {\displaystyle n} のあらゆる二分木は、親の参照、左右の子の参照、部分木のサイズの取得など、各ノードに対する多数の操作を定数時間でサポートしながら 2 n + o ( n ) {\displaystyle 2n+o(n)} ビットで表現できる。 ノード数 n {\displaystyle n} の異なる二分木の数は ( 2 n n ) {\displaystyle {\tbinom {2n}{n}}} / ( n + 1 ) {\displaystyle /(n+1)} である。大きな n {\displaystyle n} に対しては、これはおよそ 4 n {\displaystyle 4^{n}} にしたがう。このため、符号化には少なくともおよそ log 2  ( 4 n ) = 2 n {\displaystyle \log _{2}(4^{n})=2n} ビットが必要である。したがって簡潔二分木に必要な領域量はノードごとに 2 {\displaystyle 2} ビットである。