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

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

基本信息

批准号：
20H04141
负责人：
坂内英夫
金额：
$ 11.23万
依托单位：
Tokyo Medical and Dental University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本年度の主な成果は以下のとおりである。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 に改善する文字列のクラスを発見した。

今年的主要工作成果如下。 1) 我们提出了一种 O(n^3) 时间/O(n) 域算法来查找字符串中作为子字符串包含的最长 Lyndon 单词。我们还在在线设置中提出了一种 O(n^3σ) 时域算法，该算法顺序计算字符串的每个前缀。这里，σ 是字母表大小。此外，我们进一步扩展了该问题，并提出了一种 O(n^4σ) 时间/O(n^3) 域算法，用于计算通常作为子字符串包含在两个字符串中的最长 Lyndon 单词。这些成果在第33届组合算法国际研讨会（IWOCA 2022）上发表，并荣获最佳论文奖。 2）在与字典压缩相关的字符串压缩性度量中，最小字符串吸引子大小γ，最小双向宏方案大小b，以及最小对于直线程序的每个大小g，我们简化为MAX-SAT问题，并且最大卫星通过使用求解器，我们证明了即使对于相当大的字符串，也可以在实际的时间内计算出精确的值，并提出了第一个重要的实现来计算这些值。此外，通过使用此实现，我们发现了一类字符串，可将 γ 压缩灵敏度的下限从 2 提高到 2.5。

项目成果

期刊论文数量（49）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Parameterized Suffix Tray

DOI：
10.1007/978-3-030-75242-2_18
发表时间：
2020-12
期刊：
ArXiv
影响因子：
0
作者：
Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
通讯作者：
Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda

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

Space-Efficient STR-IC-LCS Computation

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

DOI：
10.1007/978-3-031-23101-8_25
发表时间：
2023
期刊：
Lecture Notes in Computer Science
影响因子：
0
作者：
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
影响因子：
0
作者：
Akihiro Nishi;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
通讯作者：
Masayuki Takeda

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

坂内英夫其他文献

Serpentine minerals from Irikura, Oita Prefecture, Japan

产自日本大分县入仓的蛇纹石矿物

DOI：
发表时间：
2016
期刊：
影响因子：
0
作者：
中島祐人;稲永俊介;坂内英夫;竹田正幸;加藤隆文;長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅;延寿　里美
通讯作者：
延寿　里美

日向沖南海トラフ前弧域の浅部活構造

日向附近南海海槽弧前区的浅层活动构造

DOI：
发表时间：
2016
期刊：
影响因子：
0
作者：
中島祐人;稲永俊介;坂内英夫;竹田正幸;加藤隆文;長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅;延寿　里美;加藤隆文;加藤隆文;山口飛鳥・新井和乃・池原研・金松敏也・福地里菜・中村恭之・宇佐美和子・奥津なつみ・清家弘治・芦寿一郎;加藤隆文;山口飛鳥・福地里菜・濱橋真理・清水真由子・江口大賀・金川久一;Takafumi Kato;加藤隆文;芦寿一郎・山口飛鳥・福地里菜・大出晃弘・奥津なつみ・田淵優・池原研
通讯作者：
芦寿一郎・山口飛鳥・福地里菜・大出晃弘・奥津なつみ・田淵優・池原研

習慣的意味仮設説による概念プラグマティズム擁護の試み

基于习惯意义假设来捍卫概念实用主义的尝试

DOI：
发表时间：
2017
期刊：
影响因子：
0
作者：
中島祐人;稲永俊介;坂内英夫;竹田正幸;加藤隆文;長谷川亮太・山口飛鳥・福地里菜・石川剛志・北村有迅;延寿　里美;加藤隆文;加藤隆文;山口飛鳥・新井和乃・池原研・金松敏也・福地里菜・中村恭之・宇佐美和子・奥津なつみ・清家弘治・芦寿一郎;加藤隆文;山口飛鳥・福地里菜・濱橋真理・清水真由子・江口大賀・金川久一;Takafumi Kato;加藤隆文
通讯作者：
加藤隆文