Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
2進数のゼロなし表現 (Zeroless Representation)の応用

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

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

tl;dr;

  • 2^n個の要素をリストで持つと便利だし、そうすると2進数みたいな{0,1}表現になる。
  • {0,1}でデータを持つと000000001みたいなリストが生成されることがあって、先頭要素を取得するのにO(log n)かかることがあるよ
  • 2進数のゼロ無し表現をデータ構造に当てはめると、上記のO(log n)をO(1)に削減できるよ
  • PFDS面白いから読もう! https://www.amazon.co.jp/dp/4048930567

モチベーション

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

解決方法

「2^n個の値を持つ木(ex: 完全二分葉木)」のリストを持つと任意の個数を格納した上でランダムインデックスアクセスが可能になる。リストには同じ個数の木が含まれてはならない。= rank違いであることが必要になる。また、リストはランクの昇順でソートされている必要がある。

※完全二分葉木は、葉にのみ値を持つような完全二分木 ※rankについて、rank0は単一の葉で構成される木。rank r(>0)は2つのrank-1な木を子に持つ木。完全二分葉木の値の個数(= 葉の個数)は2^(rank)になる

note:
リストではなく二分葉木だけでデータを持とうとするとインデックスアクセスができない
(どこに欠損があるか不明なので要素の探索は出来てもインデックスアクセスはできない)

ランダムインデックスアクセスは二段階で行われる

  1. インデックスを2で割りながら、どの木に含まれるか探索
  2. 含まれる木を特定したら、その木の中を探索

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

以下が例だ。

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

計算量

このようにすると、ランダムインデックスアクセスは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情報を明示しない疎表現の場合、完全二分葉木では先頭要素の左端を取得する必要があるためO(1)とならない。(先頭要素がrank0とは限らない)その場合は二項木、ペナントなど、他のデータ構造を使うこと。なお、以下で紹介する方法は上記手法に比べhead以外にもlookup, updateなどもわずかに高速化するというメリットがある。

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となる。これはランダムアクセスリスト上では多数の木の再帰的なマージ操作を意味するため好ましくはない。

そこで{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