動的文字列処理に対するアルゴリズム技法の開発と計算限界の解明

动态字符串处理算法技术的开发和计算限制的阐明

• 批准号: 22K21273
• 负责人: 三重野 琢也
• 金额: $ 1.83万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-08-31 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K21273/
• 关键词: 文字列アルゴリズム; ユニーク部分文字列; 回文; 動的文字列; 動的文字列データ処理; 文字列組合せ論; データ構造

本研究は、動的に変化する文字列データを効率的に処理するのためのアルゴリズム技法を開発すること、およびそれに資する文字列構造の数理的性質を解明することが目的である。文字列中にちょうど一度だけ出現する部分文字列をユニーク部分文字列と呼ぶ。今年度は、動的に変化する文字列におけるユニーク部分文字列の変化に関する研究を主として行った。まず、ユニーク部分文字列でありかつ回文構造でもある、ユニーク回文部分文字列に着目をした。そして、文字列中の任意の一文字を別の文字に置換したときのユニーク回文部分文字列の変化についての研究に取り組み、組合せ的性質に関する新たな知見を発見し、それに基づく効率的な文字列処理アルゴリズムを開発した。得られた成果を論文にまとめ、国際論文誌 Algorithmica へ投稿した。なお、投稿した論文の査読結果は年度末時点で未達である。さらに、回文部分文字列の研究に関連して、動的文字列上での最長回文計算のために利用できる部分問題の高速解法の探求および一般化に取り組んだ。このテーマについては、既存結果からの改善と、一般化した問題の定式化および効率的な解法の開発をすでに実施しており、現在はその成果を国際論文誌 Theoretical Computer Science へ投稿する準備を行っている。次年度の序盤に、まずこちらの論文投稿作業を完了させる予定である。また、12月にソウル（韓国）で開催された国際会議 ISAAC 2022 へ参加し、計算機科学分野全般の最新動向や各種アルゴリズム技術に関する情報収集を実施した。

这项研究的目的是开发算法技术，以有效地处理动态变化的字符串数据，并阐明对其有效的字符串结构的数学特性。精确出现在字符串中的一个子字符串称为唯一子字符串。今年，我们主要对动态变化字符串中独特子字符串的变化进行了研究。首先，我们专注于独特的全文substring，既是独特的子字符串又是全文结构。然后，当弦乐中的任意单个字符被另一个字符中替换为组合属性上的新发现并基于此开发了有效的弦乐处理算法时，我们研究了独特的palindromic子字符串的变化。将获得的结果汇编成论文，并提交给国际杂志算法。截至财政年度末，尚未达到提交论文的同行评审结果。此外，与对所有人的底带的研究有关，我们已经解决了对可用于动态字符串最长的全滴定计算的快速解决方案的探索和概括。关于这个主题，我们已经从现有结果中实施了改进，提出了广义问题并开发了有效的解决方案，目前正准备将结果提交给国际杂志的理论计算机科学。我们计划在明年年初完成本文的提交。他还参加了12月在韩国首尔举行的国际会议ISAAC 2022，在那里他收集了有关计算机科学领域和各种算法技术的最新趋势的信息。