ストリームデータ圧縮の理論と知識発見への応用

点击翻译按钮获取中文摘要

近年，繰り返し構造を多く含む文書データが世代管理システム(Dropbox，GithubやWikipediaなど)やゲノムデータベース(1000人ゲノム計画など)の普及により，TBを超えて，今尚，増加の一途を辿っている．これらのデータは，世代の復元，文書やソースコードの検索，ゲノムの解析と再利用される．したがって，本研究では，アップロードされ，増え続けるこのようなストリームデータを省領域かつ高速に小さく圧縮し，圧縮した瞬間からその圧縮データ上で高速検索可能な索引を開発することによりこれらのデータからのリアルタイムかつ圧縮領域での知識発見を目指した．この問題に有効な文法圧縮索引は繰り返しの多いデータを小さく圧縮し，その圧縮データ上で高速にキーワード検索可能である．しかし，既存の文法圧縮索引はテキスト長の領域が必要でかつオフラインアルゴリズムであるため，ストリームデータのようにデータを追加する場合には，それまで圧縮したデータを破棄し，再圧縮し直さなければならず，計算時間と領域の両方のコストが高い．そこで前年度の研究では，圧縮領域でかつ理論上は高速に新たなデータを追加可能なオンライン文法圧縮索引を開発した．本年度はその文法圧縮索引の検索技術を剽窃の発見に有効な移動付き編集距離に基づく曖昧検索に拡張した(Algorithms)．また，オンライン文法圧縮索引を応用した頻出パターンを近似的に発見する技術も開発した(ICGI2016)．これは既存手法ではテキスト長必要な領域を圧縮領域に削減し，より巨大な文書を扱うことが可能となる．これらの技術は速度の面で問題は残るが，そこを改善することにより，これまででは不可能なサイズのアップロードされる文書やソースコードの剽窃の発見，シーケンサから出力されるゲノムやスポーツのセンサデータの解析といった知識発見をリアルタイムに行うことが期待できる．