DSIRNLP という勉強会でダブル配列の発表をする予定

partake.in でダブル配列に関する発表をすることが決まったので，どのような内容にするか検討中です．ダブル配列の概要についてはブログや書籍などで説明されているので，もう少し踏み込んだ内容にしようと思っています．

候補としては以下のようなものがあります．

  • 基本
    • BASE, CHECK
      • 二本の配列にわけたとき
      • 一本の配列にまとめたとき
    • 演算方法
  • 構築
    • 効率化
      • 未使用要素の連結リスト化
      • 未使用要素をブロック単位で管理
      • ラベルによる連結リスト化
    • 静的構築
      • 深さ優先と幅優先
  • 圧縮
    • TAIL のマージ
      • 完全一致のみ
      • 終端文字があるとき
      • 終端文字がないとき
    • CHECK のラベル化
      • BASE の重複回避
      • グラフ化の可能性
    • 相対オフセットと拡張フラグ
      • 小さい要素を使って大きなダブル配列を実現する方法
    • DAWG
      • Darts-clone

発表時間は 15 分なので，広く浅く説明することになりそうです．