文字列組合せ論に基づく大規模データ処理基盤技術

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

文字列の新たな組合せ的性質の究明および，それを用いたアルゴリズムの開発を目標に，文字列データ構造に着目して研究を行った．本研究では特に文字列パタン列挙のための索引構造の省領域化に取り組んだ．一つ目の成果は頻出部分文字列パタン列挙問題の変種のための索引構造の省領域化に成功した．頻出部分文字列パタン列挙問題とは，文書(文字列)の有限集合 D と正整数 d が与えられて， d 個以上の文書に生起する文字列をすべて列挙する問題である．本研究では，その変種として，クエリ文字列 p を部分文字列として含み，かつ，文字列の包含関係に関して極大な文字列のみを列挙する問題に取り組み，O(nlog|D|) 領域・O(|p| + o loglog|D|) クエリ応答時間の索引構造を開発した．ここで，n は D 中の文字列長の総和，o は解のサイズであり，この結果は，Nishimoto らの先行研究を，領域・クエリ応答時間ともに大幅に改善している．この内容はISSAC2019に採択され，発表済みである．またMFCS2016に採択されたDAWGの線形時間構築アルゴリズム及びSPIRE2019に採択されたtruncated DAWGの内容に関して，新たに得られた知見を加筆した論文をそれぞれ国際論文誌に投稿中である．