Data Compression: theoretical and practical approaches to the smallest grammar problem

数据压缩：解决最小语法问题的理论和实践方法

• 批准号: 21K11745
• 负责人: 篠原 歩
• 金额: $ 2.75万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K11745/
• 关键词: データ圧縮; 文字列処理; 機械学習; 文法推論; 質問学習; 最小文法問題; 文法圧縮; アルゴリズム

本研究は，可逆的データ圧縮の代表例である文法圧縮に対して，理論と応用の両面から取り組んでいる．今年度は関連する文字列処理に関して様々な進展があった．文字の置換を許容して構造の一致を見つけ出すパラメータ化パターン照合問題に関して2つのアプローチを行った．まず，検索を高速化するために，有向非巡回文字列グラフ(DAWG)を拡張した索引構造を新たに提案し，それをテキストから効率よく構築するアルゴリズムを開発した．このアルゴリズムはテキストの末尾に文字を付加した場合にも索引の更新が容易なオンライン型となっている．またこの索引構造を活用することで，検索の対象となるパターンの前後に新たな文字列を付加した場合にその変更に追随しながら効率よくパラメータ化照合ができることを示した．第2のアプローチとして，可逆的データ圧縮で重要な働きをするBurrow-Wheeler変換(BW変換)について，パラメータ化に拡張したBW変換を効率よく行えるアルゴリズムを開発した．このアルゴリズムもオンライン型である．さらに，パラメータ化照合や順序保存照合を含む，より一般化した枠組みにおいて，高速に検索を行うことのできる汎用の並列照合アルゴリズムを開発することに成功した．一方，通常の文字列照合に用いられる索引構造であるポジションヒープに関して，索引構造から元の文字列を復元する「逆問題」の解析に取り組んだ．索引構造に文字ラベルや頂点番号がすべて付与されている場合だけではなく，それらが隠蔽された種々の設定においても，効率よく復元が行えることを示した．

本研究从理论和实践的角度讨论了语法压缩，这是可逆数据压缩的典型例子。今年，相关字符串处理取得了各种进展。我们采用了两种方法来解决参数化模式匹配问题，允许字符替换并查找结构匹配。首先，为了加快搜索速度，我们提出了一种新的索引结构，它是有向无环字符串图（DAWG）的扩展，并开发了一种算法来有效地从文本构建它。该算法是一种在线类型，即使在文本末尾添加字符，也可以轻松更新索引。我们还表明，通过利用这种索引结构，可以有效地执行参数化匹配，同时跟踪在要搜索的模式之前和之后添加新字符串时的变化。作为第二种方法，我们开发了一种算法，通过将其扩展到参数化，可以有效地执行 Burrow-Wheeler 变换（BW 变换），该变换在可逆数据压缩中发挥着重要作用。这个算法也是在线类型的。此外，我们成功开发了一种通用并行匹配算法，可以在更通用的框架中执行高速搜索，包括参数化匹配和保序匹配。另一方面，对于位置堆这种用于普通字符串匹配的索引结构，我们致力于分析从索引结构恢复原始字符串的“逆问题”。我们表明，不仅当所有字符标签和顶点编号都分配给索引结构时，而且在隐藏它们的各种设置中，都可以有效地执行恢复。

项目成果

ネックレス文字列上の極小単出現と極大反復出現の計算

项链串上最小单次出现和最大重复出现的计算

• 发表时间: 2023
• 作者: 森竹 涼樹;熊谷 滉士郎;ディプタラマ ヘンリアン;吉仲 亮;篠原 歩
• 通讯作者: 篠原 歩

Query Learning Algorithm for Symbolic Weighted Finite Automata

符号加权有限自动机的查询学习算法

• 发表时间: 2021
• 作者: Kaito Suzuki; Diptarama Hendrian; Ryo Yoshinaka; Ayumi Shinohara
• 通讯作者: Ayumi Shinohara

EMOW型ポジションヒープの逆問題

EMOW类型位置堆的逆问题

• 发表时间: 2023
• 作者: 熊谷 滉士郎;ディプタラマ ヘンリアン;吉仲 亮;篠原 歩
• 通讯作者: 篠原 歩

Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations

子串一致等价关系下模式匹配问题的并行算法

• 发表时间: 2022
• 作者: Jargalsaikhan Davaajav; Hendrian Diptarama; Yoshinaka Ryo; Shinohara Ayumi
• 通讯作者: Shinohara Ayumi

Parameterized DAWGs: Efficient constructions and bidirectional pattern searches

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

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