コンピュータサイエンス研究会　講演会の御案内

コンピュータサイエンス研究会
主査篠原　歩

下記のようにコンピュータサイエンス研究会の講演会を開催いたしますので，ご案内申し上げます．

日　時：　2011年2月28日(月)　14:00～16:00
場　所：　電子情報システム・応物系3号館206号室
題　目：　「簡潔木のデータ構造と文法圧縮」
講　師：　定兼邦彦（国立情報学研究所情報学プリンシプル研究系）
要　旨：
簡潔木 (succinct trees) とは木を表現するデータ構造である．サイズは極限まで圧縮されているが，従来のデータ構造と同等の問い合わせ時間を実現する．
文法圧縮 (grammar compression) は文字列をそれを生成する文脈自由文法に置き換える圧縮法であり，Lempel-Ziv, Byte-pair encoding, Sequitor，Re-Pairなどの圧縮法を含む広い枠組みである．文法圧縮は文字列だけではなく，木構造の圧縮にも用いられる．本講演ではこれらについて解説する．