巨大データからの知識発見を可能にする圧縮文字列処理基盤技術

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

LZ77圧縮に着目し, LZ77圧縮を省領域で計算するアルゴリズムの開発を行った. LZ77圧縮は理論的にも実用的にも圧縮率の良い圧縮法であることが知られており, 圧縮用途以外にも, 連の解析や周期の発見など文字列解析に幅広く応用される, 汎用かつ知識発見において重要な位置づけにある圧縮データ構造である. そのような応用を考える上でボトルネックとなるのがLZ77圧縮の計算にかかる時間と領域であり, 省領域で動作する線形時間アルゴリズムの開発が求められている. LZ77圧縮は入力テキスト全体に渡る繰り返し構造を計算する必用があるため, 線形時間アルゴリズムの開発にはテキストの索引構造とその補助データ構造を使うことが一般的であり, より省領域なアルゴリズムの開発はこれらのデータ構造の領域を如何に削減するかが課題であった. 筆者は計算に必要な使用領域の削減に取り組み, NlogN+0(σlog N) bits領域を使用する線形時間アルゴリズムを提案した, ここでNは入力テキストサイズ, σはアルファベットサイズである. 先行研究で最も省領域な2N log Nbitsを使用する線形時間アルゴリズムKKP2と比較すると, アルファベットサイズが小さい場合, 提案手法はKKP2に比べほぼ半分の領域で動作し, 大きな改善に成功している. 計算機実験によりKKP2と新手法の実行時間を比較した場合, 新手法は領域を半分程度に抑えた事による計算の複雑さが増したにも関わらず, 実行時間はKKP2の2倍ほどの実行時間の増加に留まっているとの結果が得られた.