編集操作に対応した動的な文字列処理アルゴリズムの開発

开发支持编辑操作的动态字符串处理算法

• 批准号: 20J21147
• 负责人: 舩越 満
• 金额: $ 1.98万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-24 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20J21147/
• 关键词: 動的文字列処理; アルゴリズム; 組合せ論

動的データにおける組合せ的構造の解析およびアルゴリズムの開発を目的として研究を行った．第一に，スライド窓や1文字置換操作といった準動的な設定における，クエリ区間に対する最小非反復回文を求める問題に取り組んだ．スライド窓モデルに対してクエリ応答を O(loglog W) 時間，更新をならし O(log σ) 時間で行えるデータ構造を提案し，1文字置換モデルに対して O(n) 時間の前処理でクエリ応答を O(log n loglog n) 時間で行えるアルゴリズムを提案した．ここで W は窓のサイズ，σ はアルファベットサイズ，n は文字列長である．この成果は国際会議 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022) に採択されている．第二に，文字列が1文字編集された際に圧縮サイズや反復性指標がどれだけ変化しうるかについて理論的な解析を行った．zip や png に用いられる圧縮手法である LZ77 を含む複数の主要な圧縮手法/反復性指標について，サイズの変化量の上下界を与えた．この成果は国際雑誌 Information and Computation に採択されている．また，動的なデータにおける組合せ的構造の解析およびアルゴリズムの開発を行うための基盤/準備として，静的なデータを対象に以下の2つに取り組んだ．1つは，トライ上の極大回文・異なる回文をそれぞれ最適な計算量で計算できるアルゴリズムの提案，もう1つは， LZ-End と呼ばれる辞書式圧縮について，圧縮サイズが最小となる最適な LZ-End の計算が NP 完全であることの証明である．これらの成果はそれぞれ，国際会議 33rd International Symposium on Algorithms and Computation (ISAAC 2022) および国際会議 34th Annual Symposium on Combinatorial Pattern Matching (CPM2023) に採択されている．他にも動的文字列を対象として複数の成果が得られており，投稿中・投稿準備中である．

The structure analysis and development of the dynamic structure of the composite are studied. The first problem is to find the minimum non-repeating palindrome in the interval of time. A word substitution is performed in O (log σ) time before processing in O (log n) time. A word substitution is performed in O(log σ) time.ここで W は窓のサイズ，σ はアルファベットサイズ，n は文字列长である. The results of this work were presented at the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022). Second, the text column 1 text compilation The results of this research are published in the International Journal of Information and Computation. The analysis of the structure of the combination of dynamic and static characters is based on the following 2 groups: 1. the maximum palindrome on the scale of the maximum palindrome. The calculation of the minimum and optimum LZ-End is NP complete. 33rd International Symposium on Algorithms and Computation (ISAAC 2022) and 34th Annual Symposium on Combinatorial Pattern Matching (CPM2023). He moved the text column to the image, and the results were obtained. In the submission, in the preparation.

项目成果

Minimal unique palindromic substrings after single-character substitution

单字符替换后的最小唯一回文子串

• 发表时间: 2021
• 作者: Mitsuru Funakoshi;Takuya Mieno
• 通讯作者: Takuya Mieno

部分文字列編集時における最長回文の計算

编辑子串时计算最长回文

• 发表时间: 2021
• 作者: 長谷川葉月;田中寛;舩越 満
• 通讯作者: 舩越 満

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

Computing longest palindromic substring after single-character or block-wise edits

在单字符或按块编辑后计算最长的回文子串

• DOI: 10.1016/j.tcs.2021.01.014
• 发表时间: 2021
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Funakoshi Mitsuru;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki
• 通讯作者: Takeda Masayuki

Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings

半动态设置中的最短唯一回文子串查询

• 发表时间: 2022
• 作者: Hoshino Fumi;Sakane Fumio;Yuma Uematsu;Takuya Mieno
• 通讯作者: Takuya Mieno