ストリームデータのための圧縮索引と知識発見への応用

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

本研究ではネットワークやセンサデータからとめどなく流れてきて増え続けるデータであるストリーム型のテキストデータを圧縮領域の作業領域で圧縮しながら，その圧縮データ上で圧縮された瞬間からリアルタイムにキーワード検索可能な索引を構築することを目的としている．この問題は①ストリームデータを流れてきた瞬間に高速に圧縮領域の作業領域で小さく圧縮することと②その圧縮されたデータ構造上でリアルタイムにキーワード検索することに分けられ，以下の成果を得られた．①に関して，①の要件を満たしかつ世界最小の作業領域で動作する文法圧縮であるSOLCAを開発し，ESA2017という国際会議にて研究発表をした．実用的にSOLCAは従来の圧縮領域の作業領域で構築可能な文法圧縮の速度を保ったまま，30%程度のメモリ使用量で動作することを可能としている．さらに①の要件を満たす圧縮領域で構築可能なOnline RLBWTと呼ばれるテキストデータ圧縮の高速化をして，IWOCA2017という国際会議にて研究発表した．従来手法より作業領域が1.3から8.7倍かかってしまったが，約60倍の速度で圧縮可能にしており，実用的である．②に関してはキーワード検索ではないが，SOLCAの圧縮法を応用した入力テキスト中に2度以上出現する部分文字列の一部分を高速に圧縮領域で発見する方法を論文誌（IEICE Transactions on Information and Systems）に採択されました．また，以前開発したESP-index-Iという圧縮索引の短いキーワードの検索手法の高速化を行い，DCC2018にて研究発表しました．SOLCAとOnline RLBWTの構築の効率化によって，これらの圧縮法を②の要件を満たす圧縮索引に発展させることが今後の課題である．