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変換を効率よく行えるアルゴリズムを開発した．このアルゴリズムもオンライン型である．さらに，パラメータ化照合や順序保存照合を含む，より一般化した枠組みにおいて，高速に検索を行うことのできる汎用の並列照合アルゴリズムを開発することに成功した．一方，通常の文字列照合に用いられる索引構造であるポジションヒープに関して，索引構造から元の文字列を復元する「逆問題」の解析に取り組んだ．索引構造に文字ラベルや頂点番号がすべて付与されている場合だけではなく，それらが隠蔽された種々の設定においても，効率よく復元が行えることを示した．

In this study, a representative example of reversible compression is presented. This year's related text processing progress The permutations of characters are allowed to be consistent with the structure of the text. A new index structure is proposed for a non-circulating text column (DAWG). The index can be updated easily when the text is added to the end of the index. The index structure is used to search for the image before and after the new text column is added to the case. Second, reversible compression is important. Burrow-Wheeler conversion (BW conversion) is important. This is the first time I've ever seen you. In addition, the system has been successfully developed by generalizing the combination of sequential storage and combination of high-speed search and common use. In one case, the index structure of the text string is usually used for the combination of the text string and the index structure is used for the combination of the text string and the element. Index structure: text, vertex, sign, assignment, assignment.

项目成果

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

Computing the Parameterized Burrows-Wheeler Transform Online

在线计算参数化 Burrows-Wheeler 变换

• 发表时间: 2022
• 作者: Hashimoto Daiki;Hendrian Diptarama;Koeppl Dominik;Yoshinaka Ryo;Shinohara Ayumi
• 通讯作者: Shinohara Ayumi

Efficient Construction of Cryptarithm Catalogues over Deterministic Finite Automata

确定性有限自动机上密码目录的高效构建

• 发表时间: 2021
• 作者: Koya Watanabe;Diptarama Hendrian;Ryo Yoshinaka;Takashi Horiyama and Ayumi Shinohara
• 通讯作者: Takashi Horiyama and Ayumi Shinohara

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

EMOW类型位置堆的逆问题

• 发表时间: 2023
• 作者: Miyagishi Hiroko;Tsuji Minoru;Miyagawa Kazuya;Kurokawa Kazuhiro;Mochida-Saito Atsumi;Takahashi Kohei;Kosuge Yasuhiro;Ishige Kumiko;Takeda Hiroshi;熊谷 滉士郎，ディプタラマ ヘンリアン，吉仲 亮，篠原 歩
• 通讯作者: 熊谷 滉士郎，ディプタラマ ヘンリアン，吉仲 亮，篠原 歩

Inside-Outside Algorithm for Macro Grammars

宏语法的内部-外部算法

• 发表时间: 2021
• 作者: Ryuta Kambe;Naoki Kobayashi;Ryosuke Sato;Ayumi Shinohara;Ryo Yoshinaka
• 通讯作者: Ryo Yoshinaka