ストリーミングモデルにおける文字列処理アルゴリズム基盤

流模型中的字符串处理算法基础

• 批准号: 17H06923
• 负责人: 中島 祐人
• 金额: $ 1.75万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2017
• 资助国家: 日本
• 起止时间: 2017-08-25 至 2019-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-17H06923/
• 关键词: 文字列処理アルゴリズム; ストリーミングモデル; Lyndon文字列; アルゴリズム; 文字列情報学

本研究課題では，ストリームデータ処理に注目した．ストリームデータは記号の列として表現できることから，文字列データとして捉えることが出来る．そのため，ストリーミングモデルにおける文字列処理アルゴリズムの開発は重要な課題である．文字列の組合せ論という文字列に関する深い性質に基づき，ストリーミングモデルにおける文字列処理アルゴリズム基盤の構築を目指した．ストリームデータ処理には，リアルタイムかつ省領域であることが求められており，挑戦的な課題である．効率的なアルゴリズムの開発には，データが持つ深い性質を利用することが必要不可欠であるということから，1.文字列の組合せ的性質の解明，2.ストリーミングモデルにおける文字列処理アルゴリズムの開発の2段階に項目を分け研究を行った．平成29年度では1.を主に取り組んだ．最近注目を集めているLyndon文字列と呼ばれる文字列のクラスについて，その性質を解き明かすべく研究を行った．その成果として，Lyndon文字列に関する計4報の論文が国際学術雑誌及び国際会議に採択されている．この中で，Lyndon文字列に関する組合せ的な新たな知見や，圧縮文字列におけるLyndon文字列の性質に関する知見を得ている．また，その他1報の論文が国際会議に採択されている．2.についても研究を推し進め，本研究におけるストリーミングモデルにおける文字列処理アルゴリズムの第一歩的な成果を国内の研究会で発表している．また，Lyndon文字列に関する研究が注目され，国内の研究会において招待講演を行っている．

The topic of this study is related to the fact that you are paying close attention to the problem of this study. in this study, the following is the topic of this study. in this study, the subject of this study is to pay close attention to the problem of this study. in this study, the subject of this study is to pay attention to the problem. The text column is full of information. The text column is related to a number of important problems. the text column combines the text column to start an important problem. The text column combines the text column. The text column combines the text column. The text column is in-depth. The text column is full of information. Please do not fail to make use of the information in the field. Please do not fail to make use of the information that is necessary to make use of the information. The sexual explanation of the composition of the text column, 2. This is the first time to start a two-stage study of the project segment. Pingcheng 29 Annual report 1. Recently, we have noticed that the Lyndon text column is in full swing, and the text column is in full swing. The results of the study have been reviewed. The Lyndon text list has been published in 4 journals, international academic journals and international conferences. The Lyndon text column contains the latest information and opinions of the international academic journal and international conference. The text column, the Lyndon text column, the text column, the text column The progress of the study is in progress. In this study, the results of the study are listed in the domestic Research Society. The results of the study are in the first place. The results of the domestic Research Society are listed in the table. The Lyndon text list shows that the research is noticeable, and the domestic Research Society is concerned about hospitality and performance.

项目成果

Inferring strings from Lyndon factorization

• DOI: 10.1016/j.tcs.2017.05.038
• 发表时间: 2014-08
• 作者: Yuto Nakashima;T. Okabe;T. I.;Shunsuke Inenaga;H. Bannai;M. Takeda

Shortest Unique Palindromic Substring Queries in Optimal Time

最佳时间的最短唯一回文子串查询

• DOI: 10.1007/978-3-319-78825-8_32
• 发表时间: 2018
• 期刊: Proceedings of the 28th International Workshop on Combinational Algorithms (IWOCA 2017), Lecture Notes in Computer Science
• 作者: Yuto Nakashima;Takuya Takagi;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda

Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings

游程编码字符串中最大重复次数的几乎线性时间计算

• DOI: 10.4230/lipics.isaac.2017.33
• 发表时间: 2017
• 期刊: Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), LIPICS
• 作者: Yuta Fujishige;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda

ストリーミングモデルにおける最長Lyndon文字列

流模型中最长的 Lyndon 弦

• 发表时间: 2018
• 作者: Yuta Fujishige;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda;中島祐人
• 通讯作者: 中島祐人

On Reverse Engineering the Lyndon Tree

关于林登树的逆向工程

• 发表时间: 2017
• 期刊: Proceedings of the Prague Stringology Conference 2017
• 作者: Yuto Nakashima;Takuya Takagi;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda