Compressed Suffix Arrayの解説(4) -unary記法-

計算機科学

< Compressed Suffix Arrayの解説(3) -圧縮の方針- < | > Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- >

================================================

まずは下準備。数値列をunary記法でbit列に変換する方法を説明。
unary(ユナリィ)記法というのは数値の数だけの0を並べて、最後に1を置くというもの。具体例を挙げると

数値	unary
0	1
1	01
2	001
3	0001
4	00001
5	000001

となる。


unary記法では1が数値間の境界を表すために各数値毎のbitサイズを固定長にする必要がない。例えば数値列

1 1 2 2 1 2

は各数値をそれぞれ1byteで表したとすると全体で48bit(6byte)必要になる。一方でunary記法に変換すると

010100100101001

の15bitで済む。これは元の数値列の約1/3になるため大きな圧縮ができていることがわかる。
一方で数値列

10 10 20 20 10 20

は同様にそれぞれ1byteで表すと全体で48bitと先ほどと変わらない。これをunary記法に変換すると

000000000010000000000100000000000000000000100000000000000000000100000000001000000000000000000001

となり96bitもかかり元の数値列の2倍になってしまい圧縮されていないことがわかる。つまり小さい数値ほど短いbit列に、大きな数値ほど長いbit列になる。

前回の復習を少々。Compressed Suffix Arrayではインデックスを表す数値列を操作して昇順にインデックスが並ぶ箇所の多い数値列を意図的に作り出し、昇順の箇所についてその差分を保持することで小さい数値列(Ψ Vectorという)に変換する。つまりΨ Vectorは小さい数値列なのでunary記法でbit列を保持するのが効率が良いというわけ。
具体的なΨ Vectorの導出方法はおいおい説明予定。次回はbit列にrank、selectという基本操作を追加したSuccinct Bit Vector(簡素なビットベクトル)というデータ構造について説明する。

================================================< Compressed Suffix Arrayの解説(3) -圧縮の方針- < | > Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- >