文字列圧縮と組合せ論による大規模データ管理・処理技法の開発

使用字符串压缩和组合学开发大规模数据管理和处理技术

• 批准号: 18F18120
• 负责人: 稲永 俊介
• 金额: $ 0.9万
• 依托单位: Tokyo Medical and Dental University (2020)Kyushu University (2018-2019)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-10-12 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18F18120/
• 关键词: data structures; algorithms; lossless compression; hashing; アルゴリズム; データ構造; 文字列データ処理; tries; text indexing

The focus of this research was set on (a) practical and dynamic trie data structures, (b) the computation of the grammar compression Re-Pair in small space, and (c) advancements for the bijective Burrows-Wheeler transform (BBWT), a variant of the Burrows-Wheeler transform (BWT) well received in theory as well as in practice for indexing string data.(a) We have devised a novel approach for compact hashing, which is the most memory-efficient approach in practice when working with a huge number of integer keys of a bounded domain. Based on this approach, we have proposed dynamic trie data structures working with path-decomposition or with trie compaction.(b) Re-Pair, a grammar with high compression ratios, is difficult to compute within limited amount of memory. Here, we could find a quadratic time algorithm computing Re-Pair with almost no additional space. We also devised an index data structure build upon a grammar representing the Lyndon tree. This index exploits several properties of the Lyndon words to improve the running time of the currently fastest grammar index from a quadratic factor on the pattern length to a linear one.(c) Finally, we could build an indexing data structure on top of the BBWT, compute the BBWT in-place or transform the BWT into the BBWT, and finally build the BBWT in linear time.Asides from that, we could find space-efficient factorization algorithms for the non-overlapping LZ77 factorization and the LZ78 substring compression problem. These algorithms work in near-linear time with space asymptotic to the input text length in bits.

这项研究的重点放在（a）实用和动态的TRIE数据结构上，（b）在较小空间中进行语法压缩重新编写的计算，以及（c）在Burrows-wheeler Transform（BWT）中，在理论中构成了一定的数据（a Excisting for Index for Data），burrows-wheeler转换（BBWT）的变化是一定的一范围的一项and-nex contrest（bbwt），以及一定的数据（a）。哈希（Hashing），这是使用有限域的大量整数键时，这是实践中最有效的方法。基于这种方法，我们提出了与路径分解或Trie压实一起工作的动态TRIE数据结构。（b）重新分配是一种具有高压缩比的语法，很难在有限的内存范围内计算。在这里，我们可以找到一个二次时间算法计算重新测序，几乎没有其他空间。我们还设计了一个索引数据结构，建立在代表Lyndon树的语法上。该指数利用了林登单词的几个属性，以改善当前最快的语法指数的运行时间，从图案长度上的二次因素到线性。（c）最后，我们可以在BBWT上建立一个索引数据结构非重叠LZ77分解和LZ78底带压缩问题的空间有效分解算法。这些算法在接近线性的时间内起作用，空间渐近造成了对输入文本长度的位。

项目成果

Re-Pair in Small Space

小空间重新配对

• DOI: 10.3390/a14010005
• 发表时间: 2020
• 期刊: Algorithms
• 影响因子: 2.3
• 作者: Dominik Koeppl;Tomohiro I;Isamu Furuya;Yoshimasa Takabatake;Kensuke Sakai;Keisuke Goto,
• 通讯作者: Keisuke Goto,

Nicolaus Copernicus University(ポーランド)

尼古拉斯·哥白尼大学（波兰）

Dynamic Path-Decomposed Tries

动态路径分解尝试

• DOI: 10.1145/3418033
• 发表时间: 2020
• 期刊: ACM JEA
• 作者: Tsuruta Kazuya;Koppl Dominik;Kanda Shunsuke;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki;Shunsuke Kanda and Dominik Koeppl and Yasuo Tabei and Kazuhiro Morita and Masao Fuketa
• 通讯作者: Shunsuke Kanda and Dominik Koeppl and Yasuo Tabei and Kazuhiro Morita and Masao Fuketa

University of Helsinki(フィンランド)

赫尔辛基大学（芬兰）

Bidirectional Text Compression in External Memory

外部存储器中的双向文本压缩

• 发表时间: 2019
• 期刊: Proceedings of the 27th Annual European Symposium on Algorithms - ESA 2019
• 作者: Patrick Dinklage;Jonas Ellert;Johannes Fischer;Dominik Koeppl;Manuel Penschuck
• 通讯作者: Manuel Penschuck