ダブル配列の豆知识
- 1. ダブル配列 の 豆知識 矢田 晋 @s5yata 2013/9/1 1 ダブル配列の豆知识 #DSIRNLP
- 2. 自己紹介 ? 経緯 ? 大学ではダブル配列の研究をしていた ? ダブル配列は 10 回以上実装した ? 実績 ? Darts-clone ? Darts（Double-ARray Trie System）のクローン ? トライだったりトライじゃなかったり 2013/9/1 ダブル配列の豆知识 #DSIRNLP 2
- 3. あらすじ ? トライとダブル配列 ? トライ ＝ 抽象データ構造 ? ダブル配列 ＝ トライの実装 ? ダブル配列の豆知识 ? 実装の基本 ? 更新時間の短縮 ? 検索速度の向上 ? 空間効率の向上 2013/9/1 3 ダブル配列の豆知识 #DSIRNLP
- 4. トライとダブル配列 ? トライ ? 文字列をキーとする連想配列の実装 ? キーの一部をラベルとする木構造 ? 情報検索や自然言語処理における用途 ? 基礎語彙やキーワードの辞書化 ? ダブル配列 ? 配列ベースのトライ実装 ? 配列 BASE, CHECK ［, TAIL］ 2013/9/1 ダブル配列の豆知识 #DSIRNLP 4
- 5. トライ ? ラベル付きの木構造 ? ラベルは節点もしくは枝に貼り付ける ? 経路上のラベルをつなげると文字列になる ? 終端ラベル（‘$’）を入れると実装しやすい 2013/9/1 ダブル配列の豆知识 #DSIRNLP 5 N U M A L L P T R O T R $ $ $ $ $
- 6. ダブル配列 ? 配列によるトライの実装 ? BASE = 子ノード番号へのオフセット ? 子ノード番号 = オフセット ＋ ラベル ? CHECK = 親ノード番号 2013/9/1 ダブル配列の豆知识 #DSIRNLP 6 0 1 2 3 4 5 6 7 … BASE 3 … CHECK 1 1 … オフセット ＋ ラベル
- 8. 内部データ構造 ? 理論的構成 ? Array<BASE>, Array<CHECK> ? BASE, CHECK の参照で個別にキャッシュミス ? 現実的構成 ? Node = { BASE, CHECK } ? Array<Node> ? Node がキャッシュラインに収まる ? キャッシュミスを半減できる 2013/9/1 ダブル配列の豆知识 #DSIRNLP 8
- 9. 演算方法 ? 排他的論理和の方が実装しやすい ? BASE = 子ノード番号へのオフセット ? 子ノード番号 = オフセット ⊕ ラベル ? 排他的論理和の利点 ? オーバーフローとアンダーフローの不安がない ? ダブル配列をブロック単位で管理できる ? ラベルが 8-bit のときブロックの大きさは 256 2013/9/1 ダブル配列の豆知识 #DSIRNLP 9
- 10. 末尾文字列の圧縮 ? TAIL ? 根から直近の分岐までの文字列をまとめる ? ノードの削減によりメモリ使用量が減る ? 動的なダブル配列では隙間が気になる 2013/9/1 ダブル配列の豆知识 #DSIRNLP 10 N U M L L P O T R $ $ $ A$ TR$
- 12. 使いまーす 入ってまーす 更新の手順 ? 入力文字列に対する経路を確認 ? なければ追加する ? 使おうとした Node が使えないとき（衝突） 2013/9/1 ダブル配列の豆知识 #DSIRNLP 12 0 1 2 3 4 5 6 7 … Node … 0 1 2 3 4 5 6 7 … Node …
- 13. 入ってまーす 衝突の解決 ? 動かしやすい方を選択する ? 兄弟の数が少ないノードを選択する ? 兄弟の数が多いほど動かしにくいため ? 動かしやすい方を退避する ? 退避先として使える隙間を探す 2013/9/1 ダブル配列の豆知识 #DSIRNLP 13 使いまーす Node … …
- 14. 隙間探しの効率化 ? 未使用ノードの双方向連結リスト化 ? BASE に次の未使用ノード ? CHECK に前の未使用ノード 2013/9/1 ダブル配列の豆知识 #DSIRNLP 14 0 1 2 3 4 5 6 7 … BASE –3 –7 –1 … CHECK –7 –1 1 –3 …
- 15. 隙間探しの効率化 ? 隙間探しのポイント ? 常に先頭から探索するのは危険 ? 理由：前の方に使いにくい隙間がたまる可能性 ? 対処 1：前回の探索位置から再開する ? 対処 2：探索ノード数を制限する ? 静的な構築では後半だけの探索で十分 ? 理由：衝突は完全に回避できる ? 対処：探索範囲を後半 N ノードのみにする 2013/9/1 ダブル配列の豆知识 #DSIRNLP 15
- 16. 兄弟探しの効率化 ? 連結リストベースのトライに歩み寄り ? 先頭の子ノードのラベルを保持 ? 次の兄弟ノードのラベルを保持 ? ノード番号はオフセットを使って求める ? 利点 1：兄弟探しにおいて総当りしなくてよい ? 利点 2：文字列補完も効率化できる（おまけ） ? 欠点：サイズが大きくなる 2013/9/1 ダブル配列の豆知识 #DSIRNLP 16
- 17. ブロック単位の管理 ? ブロックについて ? ブロック内にある未使用ノードの数 ? 隙間探しにおける探索条件として使う ? 隙間探しに失敗した回数 ? 失敗しやすいブロックは探索しない ? 未使用ノードの管理 ? 未使用ノードはブロック内で双方向連結リスト化 ? ブロックはブロック同士で双方向連結リスト化 2013/9/1 ダブル配列の豆知识 #DSIRNLP 17
- 19. 前半部分文字列の検索 ? 例 ? 入力： “ANDROID” ? 出力： “A”, “AN”, “AND”, “ANDROID” ? 終端ラベル ? 終端ノードかどうか ? 終端ラベルを持つ子ノードが存在するかどうか ? 使い方 ? 経路上の各ノードが終端ノードかどうかを確認する 2013/9/1 ダブル配列の豆知识 #DSIRNLP 19
- 20. 静的な構築 ? 動的に構築したダブル配列 ? ノードがばらばらに配置された状態 ? 根付近以外ではキャッシュミスが起きにくい（共通） ? 静的に構築したダブル配列 ? ノードが深さ優先に配置された状態 ? 根付近以外ではキャッシュミスが起きにくい（共通） ? 葉付近でもキャッシュミスが起きにくい 2013/9/1 ダブル配列の豆知识 #DSIRNLP 20
- 22. TAIL のマージ ? 同じ文字列なら共有可能 ? 更新のあるタスクでは難しい ? 同じ文字列を探すのに時間がかかる ? 探すためのデータ構造を使うと余計に大きくなる ? 後半部分列も共有可能 ? たとえば， “DROID” は “ANDROID” の後半が使える ? おまけ ? キャッシュミスを減らせる 2013/9/1 ダブル配列の豆知识 #DSIRNLP 22
- 23. CHECK のラベル化 ? 親ノード番号の代わりにラベルを使う ? 基本的にノード番号は 32-bit でラベルは 8-bit ? BASE を 24-bit にすれば Node を 32-bit にできる ? 更新のあるタスクでは難しい ? 衝突したときに親ノードがわからない ? 動かしやすい方を選択するのは難しい ? BASE が重複するとおかしくなる ? 親ノードが複数になってしまう 2013/9/1 ダブル配列の豆知识 #DSIRNLP 23
- 24. 相対オフセットと拡張ビット ? 24-bit BASE で大規模なダブル配列を実現 ? BASE に拡張用のビットを加える ? 拡張時はオフセットを 256 倍にする ? オフセットを相対値にする ? 拡張時に粒度が粗くなる問題への対処 ? 拡張ビットによる分岐はなくせる ? (Node >> 10) << ((Node & (1U << 9)) >> 6) ? Darts-clone より抜粋（拡張ビットは 1U << 9） 2013/9/1 ダブル配列の豆知识 #DSIRNLP 24
- 25. グラフ化 ? 同じ部分木なら共有可能 ? CHECK をラベル化して BASE を重複させる ? トライ（木構造）ではなく DAWG（グラフ）になる ? グラフを構築してからダブル配列を構築する ? 静的な構築であれば，意外に時間がかからない ? Darts と Darts-clone の比較 ? http://code.google.com/p/darts-clone/wiki/Evaluation 2013/9/1 ダブル配列の豆知识 #DSIRNLP 25
- 27. まとめ ? ダブル配列について ? 単純に実装するだけならそれなりの難易度 ? ただし，バグが潜みやすい上にデバッグが困難 ? 実装前に考えるべきことは意外に多い ? TAIL の有無，静的?動的，更新時間の短縮方法など ? トライとは限らない ? CHECK をラベル化すればグラフも表現可能 2013/9/1 ダブル配列の豆知识 #DSIRNLP 27