簡潔データ構造やBalancedParenthesesの紹介資料メモ0_succ_bp.md 発表資料メモ: 簡潔データ構造について 主題 数千万オーダーの文字列集合(およびマップ)を如何にサイズ効率良く表現するか、の話 諸事情で集合をメモリ上に保持したいことがあるが、サイズは節約したい 実際にはサイズのみを追求するのではなく、諸々のトレードオフを加味しつつバランスを取る 今回はそれを実現するための方法の一つである 簡潔データ構造 について説明する: どういったデータ構造(のクラス)であるかの紹介 一言でいうなら「木構造を情報理論的な下界に近いサイズで表現するためのデータ構造」 性能特性の提示 簡潔データ構造の一つであるBalancedParenthesesについては、ある程度掘り下げて説明する 静的構築前提 亜種や類似手法の紹介(余裕があれば) ポインタの重さを知って貰う 注意 筆者はこの分野に特に精通している訳ではなく、用語や細部はいろいろと怪しいので
