最先端文字列アルゴリズム理論に基づく巨大データ解析技法

基于前沿字符串算法理论的海量数据分析技术

• 批准号: 20J11983
• 负责人: 三重野 琢也
• 金额: $ 1.09万
• 依托单位: Hokkaido University (2021)Kyushu University (2020)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-24 至 2022-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20J11983/
• 关键词: 文字列アルゴリズム; 回文; 文字列圧縮

前から読んでも後ろから読んでも同じ文字列を回文という。文字列から回文構造を発見する問題は特に生物情報科学の分野で重要視され、盛んに研究されている。本研究期間においては、文字列中の回文構造を効率よく検出するためのデータ構造・アルゴリズムの開発を主として行った。他にも文字列圧縮アルゴリズムの性能に関する研究などを行い、以下の６つの成果を得た。１つ目の成果は、入力文字列に対して特定の編集操作が許された設定において、ユニーク回文部分文字列を計算するアルゴリズムの提案である。ユニーク回文部分文字列とは、文字列中にちょうど一度だけ出現する回文である。本成果は国際会議 SPIRE 2021 に採択されており、さらにその結果を応用した研究成果は国際会議 IWOCA 2022 に投稿された。２つ目の成果は、双方向マクロスキームと呼ばれる文字列圧縮形式に対する圧縮性能限界の解明である。３つ目の成果は、LZEnd 圧縮と呼ばれる文字列圧縮手法の圧縮性能に関する新たな結果の証明である。文字列圧縮手法の性能を比較・解析する研究は文字列圧縮研究の分野で近年盛んに行われており、特に２つ目の成果は同分野で注目されていた未解決問題のひとつを解決したものである。２つ目と３つ目の成果は国際会議 SPIRE 2021 に採択されている。４つ目の成果は、RePair という文字列圧縮手法の圧縮性能に関する新たな結果の証明である。５つ目の成果は、デカルト木部分列照合問題と呼ばれる緩和された部分列照合問題に対するアルゴリズムの提案である。６つ目の成果は、圧縮表現された文字列上で、その文字列中に存在しない不在文字列を計算するアルゴリズムの提案である。上記３つの成果はいずれも国際会議 CPM 2022 に採択されている。

Before The problem of palindrome structure in text columns is an important issue in the division of bioinformatics science and is subject to intensive research. During the period of this study, the palindrome structure in the text sequence was mainly developed. The following six results were obtained from his research on the performance of text compression and compression. 1. The results of the project are set up in the context of the entry of text strings for specific compilation operations, and the proposals for the calculation of text strings for the entry of text strings are set up in the context of the entry of text strings.ユニーク回文部分文字列とは、文字列中にちょうど一度だけ出现する回文である。The results of this study were submitted to the International Conference SPIRE 2021 and applied to the International Conference IWOCA 2022 2. The results of this study are as follows: 1. Bidirectional compression; 2. Compression performance limits; 3. 3. The results of LZEnd compression and compression are related to the compression performance of text compression methods. Comparison and analysis of the performance of text compression methods; research on text compression methods; research on text compression methods 2nd International Conference SPIRE 2021 4. The results of this paper are related to the compression performance of the text compression method. 5. The results of the project are as follows: 1. The problem of partial alignment is solved; 2. The problem of partial alignment is solved; 3. The problem of partial alignment is solved. 6. The results of the project are shown in the text column, and the proposal of the project is not calculated in the text column The results of CPM 2022 are listed above.

项目成果

Minimal Absent Words on Run-Length Encoded Strings

游程编码字符串上的最少缺失单词

• 发表时间: 2022
• 作者: Tooru Akagi;Kouta Okabe;Takuya Mieno;Yuto Nakashima;Shunsuke Inenaga
• 通讯作者: Shunsuke Inenaga

A separation of γ and b via Thue－Morse Words

通过 Thue－莫尔斯字分离 γ 和 b

• 发表时间: 2021
• 作者: Hideo Bannai;Mitsuru Funakoshi;Tomohiro I;Dominik Koeppl;Takuya Mieno;Takaaki Nishimoto
• 通讯作者: Takaaki Nishimoto

Palindromic trees for a sliding window and its applications

滑动窗口的回文树及其应用

• DOI: 10.1016/j.ipl.2021.106174
• 发表时间: 2022
• 期刊: Information Processing Letters
• 影响因子: 0.5
• 作者: Takuya Mieno;Kiichi Watanabe;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda

Lyndon Words, the Three Squares Lemma, and Primitive Squares

林登词、三平方引理和原平方

• DOI: 10.1007/978-3-030-59212-7_19
• 发表时间: 2020
• 期刊: Proceedings of 27th International Symposium on String Processing and Information Retrieval
• 作者: Hideo Bannai;Takuya Mieno;Yuto Nakashima
• 通讯作者: Yuto Nakashima

String Sanitization Under Edit Distance: Improved and Generalized

• DOI: 10.4230/lipics.cpm.2021.19
• 发表时间: 2020-07
• 作者: Takuya Mieno;S. Pissis;L. Stougie;Michelle Sweering