2進数といえば通常{0,1}で数字を表現するが、各桁を{1,2}で表現するゼロなし表現という手法が存在する。 一見しただけでは、特に意味がないこの表現方法だが、「ある種のデータ構造は記数法表現を通して２進数と密接に関連する。」 という事実を通して計算量の削減に応用することができる。
高速にランダムインデックスアクセス可能なデータ構造がほしい。
木全体として2^n個の要素を持つ木のことを完全二分葉木と呼ぶ。（完全二分葉木は、葉にのみ値を持つような完全二分木である。）
単一の葉で構成される木をrank0と呼ぶ。また、rank r(>0)は2つのrank-1な木を子に持つ木とする。ここでrank Nの完全二分葉木について考えると、木が要素として持つ値の個数（= 葉の個数）は2^(N)になる。
完全二分葉木は任意の個数のデータを持つことができない。これを克服するため、完全二分葉木を要素に持つリストを作る。これにより任意の個数のデータを格納することができる。 このときリストには同じrankの木が含まれてはならないこととする。また、リストはランクの昇順でソートされているものとする。
例として、リスト全体で値が５個の場合 rank2の木(葉が4個)が１個, rank1の木が０個 rank0の木(葉が1個)が１個で構成できる。
以下がデータ構造の例
One(rank0Tree), Zero, One(rank2Tree)<- 要素が5個の場合One(rank0Tree), One(rank1Tree), One(rank2Tree)<- 要素が７個の場合
上記のデータ構造は以下のようにランダムインデックスアクセスが可能である。
ランダムインデックスアクセスは二段階で行われる
1. インデックスを2で割りながら、どの木に含まれるか探索
2. 含まれる木を特定したら、その木の中を探索
このようにすると、ランダムインデックスアクセスはO(log n)となる。（リストの先頭からsizeの和を計算しながら対象の木を選ぶ + 対象の木から対象の要素を選ぶ)
ところでリストをよく見ると、各木が2^n個の要素を保持することを踏まえると、これは２進数を逆順で並べたものに等しいことが分かる。
One(rank0Tree), Zero One(rank2Tree)=>101One(rank0Tree), One(rank1Tree), One(rank2Tree)=>111
そのためこのデータ構造は「２進ランダムアクセスリスト」と呼ばれている。
※ この例のように、ある種の自然数の表記法を利用してデータ構造を設計することができる。これは「記数法表現」に基づく設計と呼ばれている。
このリストは、効率的なランダムアクセスをO(log n)で提供するが、逆にシンプルなデータ構造ではO(1)で提供可能なheadなどのリスト用の操作もO(log n)になってしまう。
headが遅くなるケースとしては、 2進数で1000000（リスト形式では0000001)となるような数字のときに先頭から1になるまで探るための操作が必要になる場合が挙げられる。 （木の要素数nに対してリストはlog n個あるはずなのでhead操作はO(log n)になる）
上述の弱点を克服するためには様々な方法が考えられる。 ２進数のようにデータを持つことを諦めるといろいろな手が考えられるが、一方で数とのアナロジーがあると様々なアイディアや性質をそこから導くことができるため、今回は2進数のアナロジーを保持したまま、この弱点に対応することを考える。
前述の問題を考えると先頭に0が連続した場合に操作が遅くなってしまうというのが課題であったため、先頭に0が連続して表れないような表現を考えれば効率的なhead等の操作が提供できる。
この際に使えるのが2進数のZeroless Representation表現方法である。 これはすべての数字を{0,1}ではなく{1,2}で表現する。
例
- 5 (101)_2 -> (21)_2'
- 6 (110)_2 -> (22)_2'
- 16 (10000)_2 -> (1112)_2'
この表現を当てはめると先程の２進ランダムアクセスリストに含まれるリスト以下のようになる。（上記２進数の例と逆順になっていることに注意）
- 要素数5 =>
(One(rank0の木) , Two(rank1の木, rank1の木)) - 要素数6 =>
(Two(rank0の木, rank0の木), Two(rank1の木, rank1の木)) - 要素数16 =>
(Two(rank0の木, rank0の木), One(rank1の木), One(rank2の木), One(rank3の木))
headを取りたい場合はOneならそこにあるrank0の木（要素数1なのでO(1)で取れる）の値を、Twoなら左側のrank0の木から値を取得すれば良い。 これによりhead操作がO(1)となる2進ランダムアクセスリストを提供することができる。
懸命に保持した２進数のアナロジーだが苦労の甲斐あって、この先にもいろいろな展開がある。 例えば1111をインクリメントすると10000となる。このような繰り上げ操作は2進ランダムアクセスリスト上では多数の木の再帰的なマージ操作を意味するため好ましくはない。
そこで{0,1,2}を許可する特殊な２進数を考えると1111をインクリメントした際に2111となる。さらにインクリメントすると1211となる。 要は2の存在によって連鎖する繰り上げ操作を遅延させることができる。
またデクリメントと繰り下げに関しても同様の議論がなりたつ。 （実は単純にストリームにしてもincまたはdec単体では償却計算料O(1)で動作するが、incとdecの繰り返しに対しては定数にならない。）
この遅延２進数と呼ばれるテクニックは、本の最後の方で紹介される暗黙再帰減速にもつながってくるのでさらなる発展がある。
ということがわかって面白いのでPFDSを読みましょう！