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

基于串组合学的大规模数据处理平台技术

• 批准号: 18J10967
• 负责人: 藤重 雄大
• 金额: $ 0.96万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-25 至 2020-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18J10967/
• 关键词: データ構造; アルゴリズム; 文字列処理

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

The research on the properties of the new combination of text columns is carried out in the field of text column structure. In this paper, we study the index structure and domain selection of text columns. The results of a series of frequent partial text column problems and the variety of index structure and provincial domain success. The problem of frequent partial character string is that the finite set D of documents (character string) is positive integer d and the problem of character string generated by more than d documents is negative integer d. In this study, we found that the problem of text string inclusion is related to maximum text string inclusion, O(nlog).| D| The field O(|p| + o loglog| D| The index structure of time is developed.ここで，n は D 中の文字列长の総和，o は解のサイズであり，この结果は，Nishimoto らの先行研究を，领域·クエリ応答时间ともに大幅に改善している. The content of this article is ISSAC2019. MFCS2016 was selected for the linear time structure of DAWG and SPIRE2019 was selected for the content of truncated DAWG.

项目成果

Truncated DAWGs and their application to minimal absent word problem

截断的 DAWG 及其在最小缺席单词问题中的应用

• 发表时间: 2018
• 作者: Yuta Fujishige;藤重雄大;藤重雄大;Yuta Fujishige
• 通讯作者: Yuta Fujishige

ヘルシンキ大学(フィンランド)

赫尔辛基大学（芬兰）

左右極大共通文字列の列挙アルゴリズム

左右最大公共字符串枚举算法

• 发表时间: 2018
• 作者: Yuta Fujishige;藤重雄大;藤重雄大
• 通讯作者: 藤重雄大

Improving an upper bound on suffix tree breadth

提高后缀树宽度的上限

• 发表时间: 2019
• 作者: Yuta Fujishige;藤重雄大
• 通讯作者: 藤重雄大

An improved data structure for left-right maximal generic words problem

左右最大通用词问题的改进数据结构

• 发表时间: 2019
• 期刊: Proceedings of the 30th International Symposium on Algorithms and Computation, LIPIcs
• 作者: Yuta Fujishige;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda