- 主題
- 数千万オーダーの文字列集合(およびマップ)を如何にサイズ効率良く表現するか、の話
- 諸事情で集合をメモリ上に保持したいことがあるが、サイズは節約したい
- 実際にはサイズのみを追求するのではなく、諸々のトレードオフを加味しつつバランスを取る
- 今回はそれを実現するための方法の一つである 簡潔データ構造 について説明する:
- どういったデータ構造(のクラス)であるかの紹介
- 一言でいうなら「木構造を情報理論的な下界に近いサイズで表現するためのデータ構造」
- 性能特性の提示
- 簡潔データ構造の一つであるBalancedParenthesesについては、ある程度掘り下げて説明する
- 静的構築前提
- 亜種や類似手法の紹介(余裕があれば)
- どういったデータ構造(のクラス)であるかの紹介
- ポインタの重さを知って貰う
- 注意
筆者はこの分野に特に精通している訳ではなく、用語や細部はいろいろと怪しいので、 興味を持った人は、ここに書かれていることを鵜呑みにせずに、自分でちゃんと調べることをお勧めします。
- 自己紹介を兼ねた経緯説明
一時期(六年前くらい?)、形態素解析器の実装にハマっていたことがあった(以下、作成物):
辞書はMeCabのものを使わせて貰っている:
- igo等が行っているのは、既に構築済みの辞書を引いて、テキストを形態素に分解することのみ
- そのため「辞書引きを如何に効率良く行うか」が処理効率を上げるために最重要となる
- MeCabの辞書(i.g., IPA辞書)の登録単語数は、だいたい数十万オーダー
その関係で、今回紹介する簡潔データ構造も含めて、類似のデータ構造をいろいろと調べたり実装していたりしていた (後でそれぞれについて少しだけ触れる。時間が余れば):
- Double Array:
- トライ木の効率的な表現方法の一つ (消費メモリと処理速度のバランスが良い)
- 「木構造をどう物理的に表現するか」に関わってくるので、簡潔データ構造と競合する立ち位置
- 実装物: https://osdn.jp/projects/doar/ (初めての公開ライブラリ!)
- DAWG:
- "Directed Acyclic Word Graph"の略
- 論理的な木の構造に関わってくる
- 乱暴に云ってしまえば「末尾部分も共有可能にしたトライ木」
- 木を表現する際に必要なノードの数を大幅に減らせるので、上手く使えばサイズを節約できる
- 実装物: https://github.com/sile/cl-dawg
- 簡潔データ構造:
- 今回の主対象
LOUDSとBalanced Parentheses(およびこれらの亜種)がメジャーっぽい- 前者は幅優先探索、後者は深さ優先探索に基づく
- 実装物:
- https://github.com/sile/louds (LOUDS++. 中途半端)
- https://github.com/sile/succ (Balanced Parentheses. 開発中)
- Minimal Perfect Hash Function:
- 有界な集合の各要素に、連番かつ一意なID(整数値)の割り当てを可能にするハッシュ関数
- 実装物: https://github.com/sile/mphf
- Suffix Array:
- 文字列の全文検索用のインデックス構造
- 実装物: https://github.com/sile/sais
- etc:
- その他いろいろあるらしい
ただ、当時は、集合サイズがそれほど巨大ではないこともあり、結局速度を優先して簡潔データ構造ではなく、 DoubleArray(+ DAWG)を採用した。
それからしばらくはこの分野からは離れていたが、 最近「数千万オーダーの文字列集合をオンメモリで保持したい」という用途が出てきて、 かつ、以前には触れなかったBalancedParenthesesを調べてみたら、いろいろと面白い特徴もあったので、 この場を借りて紹介させて貰うこととした。
- 簡単な性能紹介・比較
本題に入る前に簡潔データ構造の性能特徴を軽く紹介 (実装に大きく依存するものではあるので、参考程度に)。
入力データ:
- Wikiepdiaのタイトル群;
- タイトル数: 29,495,185 (約三千万)
- ファイルサイズ: 672MB
- タイトル(キー)群は事前にソートされてファイルに保存されているものとする
- 取得スクリプト: download-wikipedia-titiles.sh
比較のために以下の３つの方法で集合を表現し、各々の構築時間および必要メモリ量を計測した:
- a) 入力データを走査するだけ
- 集合は構築せずに、単に深さ優先探索順に走査するだけ
- NOTE: ソート済み文字列集合に対する深さ優先探索、が何かは後述
- 一番軽いケースとして、他との比較用に使用する
- 集合は構築せずに、単に深さ優先探索順に走査するだけ
- b) ハッシュテーブル:
- 単純にハッシュテーブルに各キーを格納するだけ
- 実装にはRustが標準で提供しているHashSetを使用
- c) 入力データそのまま + 各キーの先頭位置(32bit)をソート順に保持した配列
- キーの検索は二分探索で可能
- ソートは(手抜きで)汎用ソートを使っているので、実際にはもっと高速化可能
- 後から気づいたけど、既に入力がソートされている前提なので、この処理は不要だった
- => 実質的なコストは「改行位置の探索」と「各キーの先頭位置の保持」くらい
- 参考図
- d) 簡潔データ構造
- Balanced Parenthesesで表現したトライ木を用いる
- 詳しいことは後述
計測手順の詳細はset_build.shを参照のこと。
| 所要時間 | 使用メモリ | 備考 | |
|---|---|---|---|
| a) 深さ優先探索のみ | 5.13秒 | 48MB | |
| b) ハッシュテーブル | 25.15秒 | 2,030MB | |
| c) 入力データ+先頭位置の配列 | 3.34秒 | 1,054MB | 使用メモリ(おおよそ): 入力文字列 + 32bit * キー数 |
| d) Balanced Parentheses | 9.80秒 | 628MB | 構築完了後に必要な領域は402MB |
Balanced Parenthesesは、メモリ効率に優れているのが結果から見て取れる。 (入力データサイズよりも必要なメモリ領域が小さくて済む)
また、単なる深さ優先探索だけの場合に比べて、二倍程度の時間しか要していないのも注目に値する。 (i.e., 入力データサイズに対して線形時間での構築が可能)
上のb,c,dに対して、入力データの各キーの検索(先頭10万キー分)を行い、その平均時間を取った値:
| 平均検索時間 | 備考 | |
|---|---|---|
| b) ハッシュテーブル | 437ナノ秒 | |
| c) 入力データ+先頭位置の配列 | 419ナノ秒 | 要するに二分探索の性能 |
| d) Balanced Parentheses | 65,059ナノ秒 | 未最適化 (ちゃんと実装すれば一桁くらいは速くなりそう?) |
検索速度は明らかにBalanced Parenthesesが遅い。
- 簡潔データ構造の説明
注意: 以下、不正確かもしれないので (略)
Succinct Data Structure:
- "Succinct"は情報理論の用語
- あるデータの表現に必要な(理論的な)ビット数を
Nとした場合に、ある表現が実際に消費するビット数が、N + big-O(1)ビットなら"implicit"N + small-o(N)ビットなら"簡潔(succict)"big-O(N)ビットなら"compact"
- つまりあるデータを、情報理論的な下界に近いサイズ(ビット数)で表現可能な構造、のこと
なお、今回は簡単のために、対象を二分木のみに限定する:多分木の場合にも、二分木として表現して扱うようにする下記の図を参照 (左の子=最初の子、右の子=次の兄弟、と解釈することで、二分木で任意の木構造が表現可能)- => 訂正: むしろ多分木ベースだった
図1:
引用元: Left-child right-sibling binary tree - Wikipedia
具体的には:
- ノード数がNの木構造は、理論的には2Nビット(くらい)で表現可能(らしい)
- MEMO:
- 各ノードが取り得る状態は
{子なし、左の子のみ、右の子のみ、両方あり}の四つ. つまり2bit必要。 - ノード数はNなので
2 * Nビットが全体で必要
- 各ノードが取り得る状態は
- あくまでも木の構造のみに関する話で、各ノードのラベル(値)は別枠 (後述)
- MEMO:
- 今回取り上げる簡潔データ構造では
2n + small-o(n)で木構造が表現可能 - また、ノードの探索用の各種操作は
O(1)で可能なように設計されている:- e.g., 親・子・兄弟ノードへの移動、子孫ノードの数の取得
- 木構造を2Nビットで表現するだけなら簡単だが、それのみではこの定数操作の要件が満たせない
- => ビットベクタ、と呼ばれるデータ構造を用いることで解決 (ある意味ここが肝)
要するに、
- a) 論理的には、木構造を2Nビットで表現する
- 実用上は、それとは別に各ノードのラベル配列を別に保持する必要があることがほとんど
- b) 実際の性能上の課題はビットベクタを工夫する (ここで
small-o(n)分のサイズオーバヘッドが加わる)
以下の操作をO(1)で実行可能なビット列を__ビットベクタ__と呼ぶ:
rank1(index):index、または、それよりも前方にある1bitの数を返す- 定義によっては(?)、indexの位置自体はカウントに含めない
- 0bit版の
rank0もある
select1(rank):- 先頭から
rank番目の1bitの位置を返す - 0bit版の
select0もある
- 先頭から
BalancedParentheses(の論文の一つ)では、さらに以下を備えたNND(Nearest Neighnour Dictionary)を要求している:
pred1(index):index、または、それよりも前方にある最初の1bitの位置を返す- "predecessor"の略
succ1(index):index、または、それよりも後方にある最初の1bitの位置を返す- "successor"の略
- とはいえ上記操作は
rankとselectが利用可能なら(最適化を考えないなら)どちらも機械的に定義可能なので、そこまで重要ではないかもしれない- e.g.,
pred1(index) = select1(rank1(index))
- e.g.,
図2:
引用元: A x86-optimized rank&select dictionary for bit sequences
(rankの範囲がexclusiveになっていそうだけど説明上大きな問題はない)
TODO: 実現アイディアとしてよく見かけるのは云々
なお、サイズを小さく抑えつつ実際の効率良く(特にselectで)O(1)を達成するのは結構難しかったりするので、
実装上は「0.5倍程度の(追加)オーバヘッド + selectは対数オーダーで妥協」という方法を取ることもある。
(今回紹介するのもそれ。ちゃんと実装を追求してすらいないので、単にサボっているだけとも云える。いつかちゃんと実装する)
論文では、(少なくとも理論上は)サイズを抑えつつO(1)が達成可能な方法が提示されている。
代表的っぽいのは"LOUDS"と"Balanced Parentheses"の二つ(のような気がする):
- 前者は幅優先探索に、後者は深さ優先探索に基づいた表現方法
- 亜種はいろいろだが、今回はベーシックなもののみを取り上げる
- どちらも(論理上は)一ノード辺り2bitの領域で表現可能:
- ポインタを使った素直な表現に比べるとだいぶ軽い
- 素直な表現: 64ビット環境なら、左右の子に一つずつポインタを割り当て、一ノードで128bit消費
- => 簡潔データ構造とでは64倍の差
- NOTE: 公正な("論理上"の)比較にするなら"ポインタサイズ = log2(要素数) bit"とすべきかも
Balanced Parentheses(BP)との比較用に軽く紹介。
- "Level-Order Unary Degree Sequence"の略
- BPよりも表現力(提供する操作の種類)は劣るが、構造的にはより単純 (主観)
- 参考論文: 『Enginnering the LOUDS Succinct Tree Representaion』
- NOTE: この論文自体は、LOUDSの亜種(発展形)であるLOUDS++の提案が主目的
以下のルールに従って、木(多分木)を幅優先探索しつつビット列を生成する:
- ノードを訪問した際に、
-
- 子供の数だけ1bitを追加する
-
- 最後に0bitを付与する
- => 各ノードにつき2bit必要
-
- なお、木には仮想的なルートノードが存在するものとする
- => 合計サイズ:
2 + 2*nビット (wheren=木に含まれるノード数)
- => 合計サイズ:
- ノード数に対して線形時間で構築可能
図3:
引用元: vsmirov / memoria / wiki / LabeledTree
主要な操作(の一例)のみ紹介:
- 最初の子の取得:
-
node_id = rank1(current_index); first_child = select0(node_id) + 1
-
bits[first_child] == 1なら子がいる
-
- 次の兄弟の取得:
-
next_sibling = current_index+1
-
bits[next_sibling] == 1なら兄弟がいる
-
- ラベルの取得:
node_id = rank1(index); labels[node_id]
その他に、前の兄弟に戻ったり、親に戻ったりも可能。
これらの木の探索操作と、ラベルの取得を組み合わせることで、 たいていの(?)の木を用いたデータ構造が表現可能。
- LOUDSとは異なり深さ優先探索ベースのデータ構造
- 木の各ノードを、対応の取れた括弧、と見做して表現する
- 「この開き括弧に対応する閉じ括弧を取得」とかを使って、木の探索を実現する
- メリット(LOUDS比):
- 深さ優先探索便利 (特にノード数が膨大な場合には):
- 構築時のメモリ消費量が少なくて済む (ことが多い)
- 元のキー群の走査が効率的に行える (後述?)
- 表現力がより高い:
- 「あるノードの子孫の数」を定数時間で取れたりする:
- 検索ヒット数の表示等で使えるとか
- 後述する各キーに一意なIDを割り当てたい(i.e., マップを表現したい)場合にも有用な特性
- 「あるノードの子孫の数」を定数時間で取れたりする:
- 深さ優先探索便利 (特にノード数が膨大な場合には):
- デメリット(LOUDS比):
- より複雑(主観)
- ビットベクタ層への要求がより多い (NNDが必要。ただし逆に
select0は不要なので云々) - (参考にした論文では)木の探索時に、再帰的な処理が必要になってくる
- ビットベクタ層への要求がより多い (NNDが必要。ただし逆に
- より複雑(主観)
- 参考論文: 『A Simple Optimal Representation for Balanced Parentheses』
以下のルールに従って、木を高さ優先探索しつつ、対応するビット列を生成する:
- ルール:
-
- ノードを訪問した際には、開き括弧(1bit)を追加する
-
- ノードを離れる際には、閉じ括弧(0bit)を追加する
- => 各ノードにつき2bit必要
-
- なお、木には仮想的なルートノードが存在するものとする
- => 合計サイズ:
2 + 2*nビット (wheren=木に含まれるノード数)
- => 合計サイズ:
- ノード数に対して線形時間で構築可能
図4:
引用元: Introduction to Ultra-succinct representation of ordered trees with applications
主要な操作(の一例)のみ紹介:
- 前提:
rank等に加えて、対応する括弧の位置の取得操作が利用可能なものとする- "加えて"というか、BPではrankやselectは(最上位レベルでは)直接は使用しない
get_close/get_open- 今回は割愛するが"自分を包含する括弧"を取得するための操作もある (親ノードに遷移するために必要)
- 実現方法は後述
- 最初の子の取得:
-
node_id = current_index + 1
-
bits[first_child] == 1なら子がいる
-
- 次の兄弟の取得:
-
next_sibling = get_close(current_index) + 1
-
bits[next_sibling] == 1なら兄弟がいる
-
- 子孫ノード数の取得:
(get_close(current_index) - current_indec) / 2
- ラベルの取得:
- 若干手間
- 案1)
label_id = rank1(index) - rank0(index)rankを定数時間で実現するための追加データが必要になるのが難点
- 案2) 各ノード探索時にラベルIDをメンテする
- 子に移る際には1を加算、次の兄弟に移る際には子孫数を加算
- => 任意のノードから探索を開始できないのが難点 (ルートからのみ)
論理レベルでは、括弧の操作のみで、木の探索が実現可能。
- Balanced Parenthesesの実現方法
上で説明したBPを実際に効率良く実現するにはどうすれば良いか。
具体的にはget_close操作の実現方法についての話となる。
注意: sile/succの実装ベースの説明で、論文のものとはだいぶ異なる(と思う)
TODO: オーダーについて
新しい定義とか概念とか:
- ビット(括弧)列を固定長のブロック群に分割する:
- sile/succでは64bit固定 (論文では、入力データサイズに応じて変わる)
- 以下の性質を満たす括弧を"far parenthesis"と呼ぶ:
- 同じブロック内に対応する括弧を含まないもの
- 反対は"near parenthesis"
- 各ブロックで以下の性質のどちらか満たす括弧を"pioneer"と呼ぶ:
- a) ブロック内で最初に出現した"far"な開き括弧 (and それに対応する閉じ括弧)
- b) ブロック内で最後に出現した"far"な閉じ括弧 (and それに対応する開き括弧)
- 詳細は割愛するが、pioneerの数の上界は(おおよそ)
入力ビット列サイズ / ブロックサイズ * 2となる- 注意: 若干不正確かもしれないので、正確に知りたい場合には論文を参照のこと
- sile/succの場合には、おおよそ
入力ビット列サイズ / 32となる
図5:
引用元: Succinct Data Structure Library
追加で必要となるデータ:
- a) ある括弧が"pioneer"かどうか、を識別するためのフラグ群
- "pioneer family"と呼称
- 論理的なサイズは入力ビット列と同じとなるが、実際にはもっと節約可能(詳細は後述)
- 表現能力的にはNNDであり"rank1/select1/pred1/succ1"の操作が利用可能
- b) "pioneer family"に属する括弧のみを抽出して作った括弧木
- 再帰的な木であり、サイズが異なるだけでオリジナル同様の構造・操作を備える
- 便宜上"pf{レベル}括弧木"と呼称することがある
- ただし、"pioneer family"のサイズが一定を下回った場合には、それ以降は作らない (ベースケース)
- 必要なサイズの概要(sile/succの場合):
N / 32 + N / 32 / 32 + N / 32 / 32 / 32 + ...(where `N = オリジナルの括弧木のビット数)- =>
O(N)(?) - 論文中では各レベルのブロックサイズをよしなにすることで
o(N)を達成している (若干怪しい)
- 再帰的な木であり、サイズが異なるだけでオリジナル同様の構造・操作を備える
TOOD: 余裕があれば図をのせる
簡単のために今回はget_closeのみを取り上げる。
以下の手順でiの位置の開き括弧に対応する閉じ括弧が取得可能:
- 前提:
- 各ブロック内では
O(1)で各種操作が実行可能
- 各ブロック内では
-
iの括弧が属するブロックbを取得
-
b.get_close(i % ブロックサイズ)で結果が得られた場合には、そこで終了 (near括弧)
-
- そうではない場合には、pioneer family(pf)に対して
pi = pf.pred(i)を実行
- =>
iと同じブロック内に最初に出現するfar開き括弧、が得られる
- そうではない場合には、pioneer family(pf)に対して
-
pi1 = pf.rank(pi)で"pf{1}括弧木"内でのpiのインデックスを取得
-
pi1' = pf1.get_close(pi1)を呼び出してpi1に対応する閉じ括弧を取得する
- => 以下、結果が得られるまで手順1から再帰的に繰り返す
- =>
pi' = pf.select(pi1')で、piに対応する閉じ括弧の(level0での)位置が取得可能
-
d = piの深さ - iの深さとする (i.e., "iはpiのd番目の孫")
-
pi'のd番目の孫であるfarな閉じ括弧が、iに対応する閉じ括弧、となる (最終的に結果が得られた)
TOOD: 余裕があれば図を使って説明
時間的に厳しいので正しさの証明は省略。
処理ステップ的には「各レベルでの処理数はO(1)」かつ「再起の数も一定」なので定数時間、といった感じ。
(sile/succの様に、ブロック長を各レベルで等しくしてしまうと、後者の条件が達成できないので定数オーダーではない)
ここが論文と実装とで異なる主たる箇所。 (とりあえず適当に実装したものなので、その内に変更する可能性は高そう)
pioneer familyが素な集合(i.e., 1bit/0bitの比率は概ね1/32)なことを利用している。
以下の三つから構成される
-
- small配列(8bit要素配列):
- 4ブロック毎に一つのグループが対応する
- レイアウト:
small[0 + グループオフセット] = グループ内の1bitの数small[rank + グループオフセット] = グループ内でrank番目に出現する1bitの位置(相対)
- サイズ的な話:
- 入力が素な集合であり、一つのグループ内に存在する1bitの平均数の期待値は8個
- => グループ辺り
(1 + 8) * 8 = 72bitを平均で消費する - => 4ブロック(i.e., 256bit)の範囲を、72bitで表現できている (元の28%くらいの消費量)
-
- middle配列(16bit要素配列):
- smallだけだと(各グループの要素数が可変なので)線形走査が必要になるので、ランダムアクセス可能にするための補助構造
- レイアウト:
middle[index / (4ブロック * 8)].rank = この地点までの累積ランク数middle[index / (4ブロック * 8)].small = この地点までに対応するsmall配列の添字- NOTE: 添字がオーバフローしないように、適宜large配列を差し挟む
-
- large配列(32bit要素配列):
- middleの大きい板
TODO: 図
MEMO: 必要な領域は入力ビット数 * 0.5bitくらい
後は、上の三つの配列を使って各種操作を実現する (省略)。
実装は sparse_one_nnd.rs。
selectは明らかに対数オーダー。
上の実装の出来はともかくとして「一定区間毎にインデックス構造を差し込むことで定数時間のアクセスを達成する」という方法自体は、 ビットベクタの実現方法としては一般的なもの(のように思う)。
任意の木構造が簡潔データ構造(BP)で効率的に表現可能となった。
残りは、これを利用しての各種データ構造の実装の話とか。
- セット(集合)の実現
これまでの材料で、どう集合を実現するか。
基本的には利用者側がどのような木を構築するか、の話に過ぎない。
文字列集合(セット)は、トライ木を使えば素直に表現可能:
- トライ木自体の説明は省略
- 入力群の先頭部分が共有可能なので、入力サイズよりも結果サイズが小さくなることが多い
- ノードのラベルは各文字
- キーの検索は TODO:
- "Left-child right-sibling binary tree"の木で"AEKP"を検索する例を口頭で説明
- ステップ数は木の形に依存する(最短でキーの長さ、最長でTODO)
- ただし、各文字列の終端判定用に、以下のどちらかの対応が必要:
- a) 文字列間で包含関係が生じないようにする
- 葉ノードに到達 == 文字列の終端
- 各文字列をNULL文字終端にすること等で機械的に対応可能
- => その場合には、ノード数が、キー数分だけ増える
- b) 各ノードに「終端かどうか」を識別するためのフラグを付与する
- ノード数bit分だけ、追加領域が必要となる
- より柔軟なので、個人的にはこちらを採用することが多い
- a) 文字列間で包含関係が生じないようにする
トライ木を用いた場合は「木の末尾部分は共有不可」および「ラベル用の領域が大きくなる」といった点が、 最終的に得られるデータ構造のサイズを縮める上での妨げとなることが多い (また後で触れる)。
- 入力がソート済みなら
O(入力データサイズ = バイト数)で、それを木構造と見做して、深さ優先探索が可能 - つまりBPが直接構築できる
- 中間データ構造的なものがほぼ不要 and BPも線形構築可能なので、全体として線形時間で作成できる
- ! 後者に関しての説明がこれまでになかった気がする...
MEMO: もし詳細を説明するなら http://sile.hatenablog.jp/entry/20110807/1312731007 を使う
- セットからマップに
- 各文字列(キー)に一意かつ連番のIDをどう付与するか、といった話
- IDさえ付与できれば、後は値用の配列を別に用意すれば、マップが完成する
- いくつか方法がある: 例えば...
- a)
rank1を備えたビットベクタを別に用意する - b) ID割り当て用の
O(2 * キー数)ノードの木構造を別に用意する- パトリシアから、ラベルを取り除いたようなもの
- ラベルが不要なので、簡潔データ構造を使って
2 * 2 * キー数 + αビットくらいで表現可能
- c) MinimalPerfectHashFunctionを使う
- a)
- NOTE: 集合内の要素であるということが保証されているなら
キー数 * cビットくらいでID割当が可能
TODO
トライ木と組み合わせるならこれが一番簡単。
各終端ノードが既に保持している素なIDを、密なIDにマッピングする。
終端ノードを示すフラグ群を保持しているなら、それにrank1を備えさせるだけで良い。
TODO
DAWGのように末尾部分を共有している場合(i.e., 各終端ノードが一意な素なIDを保持していない)に有用。
NOTE: 亜種として(?)、各ノードが自分の子孫に含まれる終端ノード数を把握していればIDが算出可能
TODO
木に限らず汎用的に利用可能なID割り当て方法。
- サイズをもっと節約したい
コスト高な要因:
- 共有されない末尾のノード群
- ラベル:
- 各ノードが
2bit + αで表現できてもラベルで8bit必要なら、お得感が減る
- 各ノードが
パトリシア木の特殊ケースのようなものなので、口頭で軽く触れるだけ省略(おそらく)。
TODO: 図 TODO: ノード数がどう変わるか TODO: 最終的なサイズ
TODO: いろいろ
方式:
- 木はパトリシアで表現:
- ノード数は最大で
キー数 * 2になる
- ノード数は最大で
- 各ノードのラベルをまとめて、簡潔データ構造を使ってIDを付与する
- パトリシアの各ノードのラベルには、上記のIDを使用する
- => ノードラベルが8bitに収まる保証がなくなる (今回は24bitで表現)
入力データ:
- 4節と同様 (キー数は三千万程度、サイズは672MB)
| ノード数 | ラベル部分のサイズ | 全体サイズ | |
|---|---|---|---|
| トライ(BP) | 283,832,153 | 270MB | 402MB |
| パトリシア(BP) | 50,579,914 | 77MB | 252MB |
TODO: いろいろ
- "Directed Acyclic Word Graph"の略
- トライ木の末尾部分も共有可能にしたもの
- https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton
- https://qph.ec.quoracdn.net/main-qimg-24e80ac9505e183072a2d825ce26e188?convert_to_webp=true
方式:
- DAWGからジャンプ部分を取り除けば、通常のトライ木が得られるので、それをBPで表現
- ジャンプ用に、各ノードに
log2(ノード数)サイズのポインタを保持する必要あり (素直な実装なら)- => ノード数が減る代わりにラベルサイズは増える
- マップを実現するにはひと手間必要
入力データ:
- 4節と同様 (キー数は三千万程度、サイズは672MB)
| ノード数 | 全体サイズ | |
|---|---|---|
| トライ(BP) | 283,832,153 | 402MB |
| DAWG(BP) | 78,543,662 | 337MB |
- ノード数を減らす事自体は比較的容易 (簡単に数分の一になる)
- ただし、そうするとポインタ的なランダムアクセス用の情報を別途保持する必要がでてきて、実際にはそこまでの恩恵はない
- 構築時に(たいてい入力データサイズに比例した)作業領域が必要になるのも難点
- 所要時間も伸びる
- 経験的には、単純に実装して減るサイズは数割程度
- 入力データに応じて、どの方式が効果的かは変わってくる:
- e.g., wikipediaのタイトルのように無分岐ノードが多いならパトリシア
- e.g., 電話番号のように無分岐が少なく末尾共有が大きならDAWG
圧縮前の各要素に定数時間でアクセス可能な方法があるらしい。 ラベル配列に適用できれば、かなりサイズが減りそう(ただ、計算量の定数項がかなり大きそう)。
TODO:
- http://hillbig.cocolog-nifty.com/do/2008/09/post-3087.html
- http://www-or.amp.i.kyoto-u.ac.jp/ramp2006/paper/1-1.pdf
- 要素の探索速度を上げたい
TODO:
- 『Structuring labeled trees for optimal succinctness, and beyond』
- 従来の簡潔データ構造は純粋な木構造のみに着目して、ラベルは完全に別枠で考えることが多いが、レベルも考慮に入れよう、といった話
- "ラベルxを持つ子"を定数時間で取得可能になる
- => キー検索が
O(キーの長さ)で可能になる
- TODO: 説明
O(キーの長さ)での検索が可能- 検索速度を最重視しつつ、サイズも節約したいなら、DAWGをDoubleArrayで表現するのが個人的にはお勧め
- 動的に要素を更新したい
- いろいろあるらしいけど未調査
- 「どうせオーバヘッドが大きい(実用には向かない)のだろう」という勝手な思い込み
- BPなら、深さ優先探索が効率的(単にビット列を端から順に操作するだけでOK)なので、償却データ構造的に、定期的にマージを繰り返して大きくしていく、でも良いかと思っている
- 感想的なもの?
- 基本的な考え方自体は結構単純 (最適化を突き詰めようとすると複雑)
- メリット:
- サイズが小さくできる
- (BPは)構築時に必要なメモリも小さくできる
- (BPは)構築時間も結構早いので、割とバランスが良く使いやすいと思う
- ポインタが無いので外部への保存や転送が簡単
- ポインタ = 毎回値が変わる = ロード時に何らかの再構築・調整が必要
- サイズが小さくできる
- デメリット:
- 動的更新面倒
- 検索速度遅い
- 今後調べたいこととか:
- 動的更新は一度ちゃんと調べたい (実はそこまでオーバヘッドがない方法があるかもしれない)
- 圧縮周りも
- ビットベクタのちゃんとした実装も
