Koike's Lemma

ITやビジネスに関する雑記

簡潔データ構造の第一歩

簡潔データ構造は多くの応用を持つ有益なデータ構造である.簡潔データ構造を用いることで,データサイズを小さくしながらも,多くの処理を高速化することができる.身近な例では,Google日本語入力の辞書のデータ構造にLOUDSと呼ばれる簡潔データ構造が使用されている.
しかし,簡潔データ構造に関する初心者向けの解説資料は少ない気がするので,今回は入門的な説明を書いてみたい.

データ構造とは?

そもそもデータ構造とは何か?データ構造とはデータを保持する際の保持の仕方である.例えば,トランプで自分のカードを保持する場合,通常分かりやすいようにカードを並べ替える.また,ゲームにより異なった並べ方をする.七並べなら絵柄(マーク)ごとにカードをまとめるだろうし,大富豪なら強い順に並べ替えるだろう.この並べ方のルールがデータ構造である.この例から分かる通り,何をしたいかによって適切なデータ構造は変わる.例えば大富豪では,カードを強い順に並び変えておくことにより,「場に出されているカードよりも強いカードの一覧を取得する」という操作を高速に行うことができる.なので,データ構造を議論するときは,何の操作のためのデータ構造かをきちんと意識する必要がある.

補助データについて

簡潔データ構造の話をする前に補助データについて説明しておく.
例として,本の中から特定の単語の出現場所を知りたい場合を考える.このような場合,どうすれば高速に出現場所を知ることができるであろうか?有効な手段の一つはあらかじめ索引を作っておくことである.実際,多くの本では巻末に索引が付いている.索引を利用することによって指定の単語の検索操作を高速に行うことができる.索引のように,操作の高速化のために元データとは別に作成されるデータを補助データと呼ぶことにする.あらかじめ(前処理により)補助データを作成しておくことにより,操作を高速化することができる.

簡潔データ構造とは?

補助データのうちデータサイズが"十分に小さい"ものを簡潔データ構造と呼ぶ."十分に小さい"とは,もう少しだけ正確に述べると,補助データのデータサイズが「元データに対し最適な圧縮をかけたもの」のサイズと同程度になるという意味である.正確な定義については下記のリファレンスを参照のこと.

簡潔データ構造についてのセールストーク

簡潔データ構造について正しく説明するのであれば,データサイズの議論から始めないといけない.しかし,ここでは「簡潔データ構造を使うと何ができるのか」に重点を置くために,本来の流れを無視してセールストーク的な話し方をしたい.
例えば100円ショップの説明なら,本来はこう説明すべきである.

  1. すべての商品は100円です.
  2. 扱っている商品の例としてこれらがあります.

でも,メリットを強調するために正確さを犠牲にするのであれば,こんな説明の仕方もできる.

  1. こんな商品やあんな商品を売っているところが100円ショップです.
  2. しかも値段はすべて100円!

こんな商品やあんな商品を売ってるというのは100円ショップの定義ではない,という突っ込みもきそうだが,まぁ気にするなということで,十分に言い訳をしたところで,簡潔データ構造のセールストークを書いてみることにする.

  • 簡潔データ構造とは(セールストーク)
    1. 多くの操作がテーブルへの定数回アクセスだけで完了するようなデータ構造.
    2. しかもテーブルの合計サイズは「元データに対し最適な圧縮をかけたもの」と同程度!

定数回とはデータサイズに関係なく決まった回数という意味である.後述するランク簡潔索引では常に3回のテーブルアクセス(+1回の元データへのアクセス)で答えを得る事ができる.定数回の処理で操作が完了する時,処理時間は定数時間であるという.もちろん,定数回のテーブルアクセスでは答えが求まらない場合もたくさんあるが,セールストークということで大げさに書いておいた.

簡潔データ構造の例:ランク簡潔索引

最も単純な場合を考えたいので,元データは0と1だけからなるビット列であるとし,ビット列に対する操作を考える.今回は,最も基本的な操作の一つであるランク操作のための簡潔データ構造について説明する.

ランク (rank)とは?

文書に対する操作として,指定した文字(パターン)の指定範囲での出現回数を求めるという操作を考える.これは文書を解析するための最も基本的な操作であり,出現回数を知る事で文書から多くの知見を得る事ができる.例えば,「計算時間」という単語を多く含む文書はコンピュータに関連している推定することができる.指定範囲でのパターンの出現回数を求めるための操作としてランクがある.

ランクとはデータの先頭から指定した位置までの所定パターンの出現回数のことである.今回はビット列に対する1の出現回数を考える.例として,以下のようなビット列を考える.

f:id:koikezlemma:20131122025752p:plain:w330

上の図において,index 0 から 5までの1の出現回数は3回である.それを
Rank_1(B,5) = 3
と書く.ランク操作を用いることで,index 4から5までに存在する1の数は下記のように求めることができる.
Rank_1(B,5)-Rank_1(B,3) = 2

また,ビット列の各indexの値もランクから計算できる.

f:id:koikezlemma:20131122030112p:plain:w400

上記の図から分かるように,B[5]は
B[5] = Rank(B,5)-Rank(B,4) = 1
であり,B[7]は
B[7] = Rank(B,7)-Rank(B,6) = 0
である.

ランクのための簡潔でない索引

補助データを使用してランクを高速に求めることを考える.まずは,補助データのサイズにこだわらない場合を考えてみる.最も簡単な方法は,下図のようにすべての答えをテーブルに格納しておくことである.

f:id:koikezlemma:20131122023955p:plain:w300

このようにすることで常に1回のテーブルアクセスで答えを求める事ができる.なので,このような方法でも計算速度としては問題ないのだが,問題は補助データのテーブルのサイズが元のビット列のサイズよりも大きくなってしまうことである.やや詳細に述べると,データサイズは以下のようになる.ビット列の要素数をnとすると,ビット列のサイズが1(ビット) × n = n(ビット)なのに対し,補助データのサイズは log n (ビット) × n = n log n (ビット)となる.

それでは,テーブルのサイズを小さくすることはできるだろうか?実は,テーブルを3つ使うようにする事でそれぞれのテーブルのサイズを十分小さくすることができるのである.

ランク簡潔索引

ランク操作のための簡潔なデータ構造について概要を述べる.本データ構造ではテーブルを3つ使用する.ランクの値は元データへの1回のアクセスと3つのテーブルへの1回ずつのアクセスにより求めることができる.そして、3つのテーブルのサイズはそれぞれ十分に小さくすることができる.このデータ構造はランク簡潔索引と呼ばれる.

詳細については,長くなるので別記事で説明することにする.

データ圧縮としての簡潔データ構造

元データ(ビット列)の1と0の出現確率が偏っている時,そのビット列を圧縮することができる.上記のランク簡潔索引では元データに1回,テーブルに3回アクセスしていたが,元データをうまく圧縮すると,圧縮データとテーブルに定数回アクセスすることでランクを算出できるようになる.これは完備辞書(FID: Fully Indexable Dictionary)と呼ばれている.完備辞書では,ランク操作やセレクト操作(今回は説明しない)を定数時間で行える.その際,未圧縮の元データにアクセスする必要はない.

このように,完備辞書は元データに対する圧縮データになっているにも関わらず,様々な操作を高速に行える(解凍して元データを得ることもできる).

簡潔データ構造の利用

簡潔データ構造のセールストークのところで,「多くの操作がテーブルへの定数回アクセスだけで完了する」と書いたが,テーブルの代わりに完備辞書を用いてもよい.ある操作が完備辞書を用いて定数時間で処理可能であれば,その操作を定数回行うような操作もまた,定数時間で完了すると言える.

このように既存の簡潔データ構造を用いて,新たな簡潔データ構造を設計することができる.実際,多くの簡潔データ構造が内部に完備辞書を有している.