こんにちは。レトリバのリサーチャーの木村@big_wingです。レトリバでは学習アルゴリズムの高速化や低リソース化に取り組んでいます。今回から何回かに分けて簡潔データ構造について紹介していく予定です。 初回である今回は簡潔データ構造の概念について紹介します。
簡潔データ構造の書籍としてはNavarro氏の本、日本語で書かれたものとしては定兼氏の本と岡野原氏の本があります。
簡潔データ構造
簡潔データ構造(succinct data structure)は1989年にJacobsonによって初めて提唱され、以降多くの研究者によってビットベクトル、文字列、グラフなど様々な種類のデータに対して提案されてきました。 簡潔データ構造を大雑把に定義すると、
- データ構造のサイズが小さい。
- 高速なクエリ処理が可能である。
といった2つの特徴を兼ね備えたデータ構造です。 一般的にデータを圧縮してデータサイズを小さくすると、データの復元が必要となりクエリ処理に時間がかかってしまいます。一方で高速なクエリ処理を行うためには追加で補助的なデータ構造が必要となり、データサイズが大きくなってしまいます。簡潔データ構造はこれら計算時間とデータサイズのいいとこ取りをしよう！というデータ構造です。
次に簡潔データ構造を定量的に、もう少し厳密に定義するために必要な概念として、 「Word RAMモデル」と「情報理論的下限」を紹介します。またこれ以降とします。
Word RAMモデル
簡潔データ構造を扱う際には、空間計算量をより厳密に解析するためにWord RAMと呼ばれる計算モデルを用いることが多いです。Word RAMモデルとは以下の仮定が成り立つ計算モデルです。
- メモリは
ビットのワードの配列から成る。問題の入力のサイズ
に対して
である。
- 連続する
初見で１つ目の仮定のを見ると、ワード長が入力サイズに依存しているように見えて違和感を覚えるかもしれません。この仮定があると何が嬉しいのかというと、入力データに対してのランダムアクセスが可能となるという点です。
個のデータにランダムアクセスするためには
ビットからなるインデックスが必要となるため、1つ目の仮定は自然な仮定となっています。
2つ目の仮定で定数時間で行うことができる演算を定義しており、これを用いて簡潔データ構造の時間計算量を評価します。
情報理論的下限
簡潔データ構造を定量的に定義するにあたって情報理論的下限(information-theoretic lower bound)というものがあります。データ構造のサイズが小さいことが簡潔データ構造において重要な特徴であり、データ構造におけるサイズの理論的限界として情報理論的下限を定義します。
今、要素数がである集合に対して情報理論的下限
は
ビットと定義されます。
これは対象の集合の各要素が当確率で出現する時に、一つの要素を表現するのに必要なビット数に対応しています。出現に偏りがまったくないため、データ圧縮の観点から見ると最もデータを圧縮しにくい状態です。
このような最悪ケースにおいてこれ以上小さくすることができないというmin maxの意味で情報理論的下限という名前がついているのだと私は認識しています。
いくつか例を見てみましょう。
各要素が0または1の値をとる長さ
です。よって情報理論的下限は
ビットとなります。
ノード数が
を用いて
と表現することができます。 よって情報理論的下限は
ビットとなります。(興味がある人は順序木の個数がカタラン数で表現できることを導出してみてください。順序木を深さ優先探索でトラバースし、入る時に-1、出る時に+1と対応付けるとランダムウォークのある条件を満たすパスの数え上げ問題に帰着されます。)
簡潔データ構造のもう少し厳密な定義
ここでは簡潔データ構造をもう少し厳密に定義します。最初に簡潔データ構造は、データ構造のサイズが小さく高速なクエリ処理が可能であるデータ構造であると述べましたが、これらをWord RAMモデルと情報理論的下限を用いて定義します。簡潔データ構造とは、
- データ構造のサイズが情報理論的下限に漸近する。つまりデータ構造のサイズが
ビット。
- データに対するクエリの時間計算量が、Word RAMモデル上で従来のデータ構造と等しい。
の2つを満たすデータ構造であると定義します。ここで１つ目の条件のという表記は、
が十分に大きい時に
と比べて無視できるほど小さいことを意味します。
データ構造のサイズが、最悪ケースの場合これ以上小さくすることができない情報理論的下限に漸近するということと、その上でクエリの時間計算量は従来のデータ構造と等しいということから簡潔データ構造が高速かつ省メモリであるということがわかります。
ここのタイトルでもう少し厳密な定義という煮え切らない表現をした理由は、2つ目の条件において、データに対するクエリの時間計算量がWord RAMモデル上で従来のデータ構造と等しいという曖昧な表現を用いているためです。例えば順序木であれば、従来のデータ構造とはポインタを用いた木構造の表現を想定していますが、従来のデータ構造を厳密に定義することはできません。
また、定義に述べた2つを満たさないデータ構造も簡潔データ構造とする場合もあります。例えば、従来のデータ構造ではクエリの時間計算量が定数時間であったものを入力サイズに依存したまで遅くなるものを許容したり、データ構造のサイズが
であるものを許容するといったものです。
まとめ
簡潔データ構造の紹介の初回である今回は、簡潔データ構造の定義について紹介しました。定義については図を用いた直感的な説明を行うことが困難で、文字列の量が多くなってしまい申し訳ありません。今回のブログを読んでおもしろい！と感じられた方はぜひ最初に紹介した本を読んでみてください。定義だけを読んで興味を持たれた方はプロフェッショナルになれる素養があると思います。
次回以降では、ビットベクトル、文字列、木構造など具体的な簡潔データ構造を紹介していく予定です。
