Lyndon文字列による反復性指標解析

使用 Lyndon 弦进行重复性指标分析

• 批准号: 21K17705
• 负责人: 中島 祐人
• 金额: $ 3万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K17705/
• 关键词: 文字列組合せ論; 文字列アルゴリズム; 文字列圧縮; 文字列処理アルゴリズム

文字列データの圧縮や，圧縮された文字列データを圧縮サイズに依存した計算量で何らかの処理を行う技術は，重要な文字列処理技術の一つであり，これまでに非常に多く研究がなされている．特に，繰り返し構造を多く含む文字列に対して有用な辞書式圧縮や関連する様々な圧縮法が，どの程度文字列中の繰り返し構造を捉えているかを明らかにするため，様々な圧縮法に基づいた反復性指標に関する理論的な解析が注目を集めている．本研究課題は，文字列の圧縮と直接的に関係のない Lyndon 文字列や関連する文字列構造との関係を導入および明らかにすることで，文字列の反復性をどのように捉えることができるかという問いに挑戦する課題である．また，これらの知見を利用することで様々な問題に対する文字列アルゴリズムの開発を推し進める．2年目にあたる2022年度では，査読付き国際ジャーナルに4報，査読付き国際会議に2報の研究成果を発表済みである．うち3報が文字列組合せ論に関する成果であり，うち4報が文字列アルゴリズムおよびデータ構造に関する成果をまとめたものである．本研究課題に最も深く関係する成果として，反復分解のアルゴリズムおよび組合せ的性質に関する成果が挙げられる．ここでの反復とは，テキスト中の部分文字列のうち，ある文字列の2回以上の有理数回の繰り返しで表される文字列のことを指す．本成果では，テキストの最大および最小サイズの反復分解を高速に計算するアルゴリズムに加え，そのような反復分解に関する組合せ的性質についてフィボナッチ文字列を用いて議論を行っている．特に後者の成果については，文字列の反復性について追求する本研究課題において有用な知見を与えていると考えられる．

The text column is full of information, the text column is dependent on the amount of calculation, and the important text column is very important in terms of technology, technology, In the level of text column, you can see that the text column is full of information. The basic theory of the anti-sexual theory is the analysis of the theory. This study focuses on the topic, the text column, the Lyndon text column, the text column. The text column tells you that you need to know that you can use the information you need to know that the text column will start to make progress in the first two years, and that you will pay for the international financial year 2022 in the second year. This is the most profound part of this research project. This is the most profound part of this research project. In response to the analysis of the results of the combination of the data, some of the text columns in the text column are in the middle of the column, and the text column is more than 2 times in a rational number back table. The text column refers to this result. In this paper, we use the text column to discuss the results of the high-speed calculation, the calculation of the high-speed calculation, the increase of the maximum and the minimum, the maximum and the lowest, the maximum and the lowest. The text lists "anti-sexual information" in pursuit of this research project "useful knowledge" and "knowledge".

项目成果

Factorizing Strings into Repetitions

将字符串分解为重复项

• DOI: 10.1007/s00224-022-10070-3
• 发表时间: 2022
• 期刊: Theory of Computing Systems
• 影响因子: 0.5
• 作者: Hiroe Inoue;Yoshiaki Matsuoka;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda

Position Heaps for Cartesian-Tree Matching on Strings and Tries

字符串和尝试上笛卡尔树匹配的位置堆

• DOI: 10.1007/978-3-030-86692-1_20
• 发表时间: 2021
• 期刊: Proceedings of 28th International Symposium on String Processing and Information Retrieval
• 作者: Akio Nishimoto;Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga
• 通讯作者: Shunsuke Inenaga

省領域なSTR-IC-LCSアルゴリズム

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

• 发表时间: 2022
• 作者: 米本 優生;中島 祐人;稲永 俊介;坂内 英夫
• 通讯作者: 坂内 英夫

Combinatorics of minimal absent words for a sliding window

滑动窗口的最小缺失词的组合

• DOI: 10.1016/j.tcs.2022.06.002
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Tooru Akagi;Yuki Kuhara;Takuya Mieno;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda

On the Approximation Ratio of LZ-End to LZ77

关于LZ-End与LZ77的近似比

• DOI: 10.1007/978-3-030-86692-1_10
• 发表时间: 2021
• 期刊: Proceedings of 28th International Symposium on String Processing and Information Retrieval
• 作者: Takumi Ideue;Takuya Mieno;Mitsuru Funakoshi;Yuto Nakashima;Shunsuke Inenaga;Masayuki Takeda
• 通讯作者: Masayuki Takeda