文字列の辞書式順序の組合せ論とその応用

字符串字典顺序组合学及其应用

• 批准号: 20H04141
• 负责人: 坂内 英夫
• 金额: $ 11.23万
• 依托单位: Tokyo Medical and Dental University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20H04141/
• 关键词: 辞書式順序; 繰り返し構造; BWT; Lyndon語; Lyndon 語; 辞書式圧縮; 双方向マクロスキーム; 文字列アトラクタ; 直線的プログラム; 全単射 BWT; Thue-Morse 文字列; 繰り返し指標; Lyndon 木; 原始平方

本年度の主な成果は以下のとおりである。1) 文字列に部分列として含まれる最長の Lyndon 語を求める O(n^3) 時間・O(n) 領域のアルゴリズムを提案した。また、文字列の各接頭辞に対して順にこれを計算するオンラインな設定において、O(n^3σ) 時間・領域のアルゴリズムを提案した。ここで、σ はアルファベットサイズである。また、更に問題を拡張し、二つの文字列に共通して部分列として含まれる最長の Lyndon 語を計算する O(n^4σ) 時間・O(n^3) 領域のアルゴリズムを示した。これらの成果は国際会議 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022) にて発表し、ベストペーパー賞を受賞した。2) 辞書式圧縮に関連する文字列の圧縮性指標のうち、計算が NP-困難であることが知られている最小文字列アトラクタのサイズ γ、最小双方向マクロスキームのサイズ b、及び最小の直線的プログラム（Straight Line Program)のサイズ g それぞれについて、MAX-SAT 問題に帰着し、MAX-SAT ソルバを利用することで、ある程度大きな文字列についても現実的な時間で厳密な値が計算できることを示し、これらの値を計算する初めての非自明な実装を提案した。また、この実装を利用することで γ の圧縮感度の下界を 2 から 2.5 に改善する文字列のクラスを発見した。

The main achievements of this year are as follows: 1)Text column contains the longest Lyndon sentence, O(n^3) time, O(n) field, and O(n) field. For example, if you want to set up a list of all the links in the text string, you can set up a list of all the links in the text string by adding O(n^3σ) to the list.ここで、σ はアルファベットサイズである。The problem is solved in O(n^4σ) time and O(n^3) time. The problem is solved in O(n^3) time. The results of the conference were presented at the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022). 2)Lexicographical compression is related to the compression index of character strings, calculation is NP-difficult, minimum character string is supported by the minimum two-way, and minimum straight Line is supported by the minimum Straight line, MAX-SAT problem is discussed, MAX-SAT problem is utilized, The number of words in the column is not the same as the number of words in the column The lower bound of the compression sensitivity of the word string is 2 to 2.5.

项目成果

Parameterized DAWGs: Efficient constructions and bidirectional pattern searches

参数化 DAWG：高效构造和双向模式搜索

• DOI: 10.1016/j.tcs.2022.09.008
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Katsuhito Nakashima;Noriki Fujisato;Diptarama Hendrian;Yuto Nakashima;Ryo Yoshinaka;Shunsuke Inenaga;Hideo Bannai;Ayumi Shinohara;Masayuki Takeda
• 通讯作者: Masayuki Takeda

The Parameterized Suffix Tray

• DOI: 10.1007/978-3-030-75242-2_18
• 发表时间: 2020-12
• 期刊: ArXiv
• 作者: Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda

Space-Efficient STR-IC-LCS Computation

节省空间的 STR-IC-LCS 计算

• DOI: 10.1007/978-3-031-23101-8_25
• 发表时间: 2023
• 期刊: Lecture Notes in Computer Science
• 作者: Yuuki Yonemoto;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai
• 通讯作者: Hideo Bannai

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

Towards Efficient Interactive Computation of Dynamic Time Warping Distance

动态时间扭曲距离的高效交互式计算

• DOI: 10.1007/978-3-030-59212-7_3
• 发表时间: 2020
• 期刊: Proceedings of 27th International Symposium on String Processing and Information Retrieval
• 作者: Akihiro Nishi;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda