言語処理学会年次大会で文法圧縮チュートリアル講義をしてきました

まるまるです。春がきてますね。東京はだいぶ暖かくなってきました。

先週（3/17〜3/20）行われた言語処理学会第２０回年次大会（NLP2014）において「文法圧縮入門：超高速テキスト処理のためのデータ圧縮」というタイトルでチュートリアル講義をさせて頂きました。

講義資料はSlideShareで公開しています。

文法圧縮とは、文字列を木構造に変換し、その木構造に含まれる冗長部分を文脈自由文法の生成規則として集約させて表現する圧縮法です。この圧縮法は近年の文字列アルゴリズム業界で注目を集めており、主に以下の様な特徴があります。

• 冗長度の高いデータ（例えばゲノム集合、バージョン管理文書、ウェブアーカイブなど）を効果的に圧縮できる。
• 圧縮したまま高速に検索処理などを行える（圧縮文字列処理）。
• 木構造などのデータ構造の圧縮にも使われる（圧縮データ構造）。

NLPとは直接結びつかない内容ですが、文字列アルゴリズム分野外の人が文法圧縮について知る機会がほとんどない、また、NLPの技術と親和性が高いだろうということで今回紹介させて頂きました。会場まで聴講に来て頂いた皆さまには大変感謝しております。

当日は以下の内容を解説してきました。
1. 文法圧縮についての概要
2. 文法変換アルゴリズムと符号化

• Re-PairとOLCAと呼ばれる二種類の文法変換アルゴリズムの概要、および文法圧縮の符号化方法についての解説しました。また、様々な圧縮法との比較実験結果を見ながらそれぞれの利点・欠点を説明しました。

3. 文法圧縮テキスト上のパターン検索

• 圧縮パターン照合と呼ばれる、圧縮テキスト上で照合型検索（検索パターンが固定で、検索対象テキストが動的な場合に有効）する手法について解説しました。文法圧縮における圧縮パターン照合の場合は理論・実験ともに元テキスト上で行うパターン照合よりも高速に検索できることが示されています。また、文法圧縮に基づく代表的な圧縮文字列索引構造のアイデアを簡単に解説しました。文法圧縮に基づく索引構造は最近提案されたばかりで、まだまだ改善の余地の多いテーマです。

4. 文法圧縮に基づく圧縮データ構造

• データ構造を情報理論的下限のサイズでコンパクトに表現して扱う研究（簡潔データ構造）は以前からありましたが、そのような表現の中にもデータ特有の冗長性が含まれています。文法圧縮はそのような冗長部分をうまく集約して扱うことができます。ここでは文法圧縮テキスト上で元の文字列にランダムアクセスする手法と完備索引付辞書（Rank/Select辞書）の簡単なアイデアを説明しました。

興味のある方は上記の講義資料をご参照ください。

# 北海道は海産物がおいしかったです　まる