Skip to content

Instantly share code, notes, and snippets.

@matsu-chara
Last active June 15, 2023 09:13
Show Gist options
  • Save matsu-chara/03fef6b59f60fefd5d052704cd578ac7 to your computer and use it in GitHub Desktop.
Save matsu-chara/03fef6b59f60fefd5d052704cd578ac7 to your computer and use it in GitHub Desktop.
2進数のゼロなし表現 (Zeroless Representation)の応用

2進数のゼロなし表現 (Zeroless Representation)の応用

2進数といえば通常{0,1}で数字を表現するが、各桁を{1,2}で表現するゼロなし表現という手法が存在する。 一見しただけでは、特に意味がないこの表現方法だが、「ある種のデータ構造は記数法表現を通して2進数と密接に関連する。」 という事実を通して計算量の削減に応用することができる。

モチベーション

高速にランダムインデックスアクセス可能なデータ構造がほしい。

解決方法

木全体として2^n個の要素を持つ木のことを完全二分葉木と呼ぶ。(完全二分葉木は、葉にのみ値を持つような完全二分木である。)

単一の葉で構成される木をrank0と呼ぶ。また、rank r(>0)は2つのrank-1な木を子に持つ木とする。ここでrank Nの完全二分葉木について考えると、木が要素として持つ値の個数(= 葉の個数)は2^(N)になる。

完全二分葉木は任意の個数のデータを持つことができない。これを克服するため、完全二分葉木を要素に持つリストを作る。これにより任意の個数のデータを格納することができる。 このときリストには同じrankの木が含まれてはならないこととする。また、リストはランクの昇順でソートされているものとする。

例として、リスト全体で値が5個の場合 rank2の木(葉が4個)が1個, rank1の木が0個 rank0の木(葉が1個)が1個で構成できる。

以下がデータ構造の例

  • One(rank0Tree), Zero, One(rank2Tree) <- 要素が5個の場合
  • One(rank0Tree), One(rank1Tree), One(rank2Tree) <- 要素が7個の場合

ランダムインデックスの方法

上記のデータ構造は以下のようにランダムインデックスアクセスが可能である。

ランダムインデックスアクセスは二段階で行われる
1. インデックスを2で割りながら、どの木に含まれるか探索
2. 含まれる木を特定したら、その木の中を探索

計算量

このようにすると、ランダムインデックスアクセスはO(log n)となる。(リストの先頭からsizeの和を計算しながら対象の木を選ぶ + 対象の木から対象の要素を選ぶ)

考察

ところでリストをよく見ると、各木が2^n個の要素を保持することを踏まえると、これは2進数を逆順で並べたものに等しいことが分かる。

  • One(rank0Tree), Zero One(rank2Tree) => 101
  • One(rank0Tree), One(rank1Tree), One(rank2Tree) => 111

そのためこのデータ構造は「2進ランダムアクセスリスト」と呼ばれている。

※ この例のように、ある種の自然数の表記法を利用してデータ構造を設計することができる。これは「記数法表現」に基づく設計と呼ばれている。

このリストは、効率的なランダムアクセスをO(log n)で提供するが、逆にシンプルなデータ構造ではO(1)で提供可能なheadなどのリスト用の操作もO(log n)になってしまう。

headが遅くなるケースとしては、 2進数で1000000(リスト形式では0000001)となるような数字のときに先頭から1になるまで探るための操作が必要になる場合が挙げられる。 (木の要素数nに対してリストはlog n個あるはずなのでhead操作はO(log n)になる)

2進数のゼロなし表現 (Zeroless Representation)

上述の弱点を克服するためには様々な方法が考えられる。 2進数のようにデータを持つことを諦めるといろいろな手が考えられるが、一方で数とのアナロジーがあると様々なアイディアや性質をそこから導くことができるため、今回は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'

この表現を当てはめると先程の2進ランダムアクセスリストに含まれるリスト以下のようになる。(上記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進ランダムアクセスリストを提供することができる。

その先

懸命に保持した2進数のアナロジーだが苦労の甲斐あって、この先にもいろいろな展開がある。 例えば1111をインクリメントすると10000となる。このような繰り上げ操作は2進ランダムアクセスリスト上では多数の木の再帰的なマージ操作を意味するため好ましくはない。

そこで{0,1,2}を許可する特殊な2進数を考えると1111をインクリメントした際に2111となる。さらにインクリメントすると1211となる。 要は2の存在によって連鎖する繰り上げ操作を遅延させることができる。

またデクリメントと繰り下げに関しても同様の議論がなりたつ。 (実は単純にストリームにしてもincまたはdec単体では償却計算料O(1)で動作するが、incとdecの繰り返しに対しては定数にならない。)

この遅延2進数と呼ばれるテクニックは、本の最後の方で紹介される暗黙再帰減速にもつながってくるのでさらなる発展がある。

ということがわかって面白いのでPFDSを読みましょう!

参考

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment