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

这项研究的重点集中在(A)实用和动态的Trie数据结构，(B)小空间中语法压缩对的计算，以及(C)双射Burrow-Wheeler变换(BBWT)的改进，BBWT是Burrow-Wheeler变换(BWT)的变种，在理论和实践中都很受欢迎。(A)我们设计了一种新的紧凑散列方法，在处理有界域的大量整数键时，这是实践中最节省内存的方法。基于这种方法，我们提出了使用路径分解或TRIE压缩的动态TRIE数据结构。(B)Re-Pair是一种高压缩比的文法，在有限的内存中很难计算。在这里，我们可以找到一个几乎不需要额外空间的二次时间算法计算再配对。我们还设计了一个基于表示Lyndon树的语法的索引数据结构。该索引利用Lyndon词的一些性质，将当前最快的文法索引的运行时间从模式长度上的二次因子改进为线性索引。(C)最后，我们可以在BBWT的基础上建立索引数据结构，在BBWT上进行就地计算或将BWT转换为BBWT，最终在线性时间内建立BBWT，并在此基础上找到解决非重叠LZ77分解和LZ78子串压缩问题的空间高效的因式分解算法。这些算法工作在近线性时间内，空间渐近于输入文本长度(以位为单位)。

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.