Development of novel transform-based lossless compression schemes

提出并分析了两种无损压缩变换：广义基数置换(GRP)和子串枚举压缩(CSE)。GRP变换是块排序数据压缩算法中BWT的参数推广。我们提出的扩展可以应用于任意参数值，并且可以将字符串在时间上与字符串长度线性变换。然后，我们分析了CSE算法，并提出了对平稳遍历源和任意阶马尔可夫源实现渐近最优的编码模型。我们还建立了有效实施CSE的具体方法。CSE经常产生比所需的更多的码字。为了减少这种冗余，我们提出了一种计算CSE中应该枚举的子串的最大长度的方法，以唯一地标识输入字符串。作为这些变换的一个应用，我们提出了一个实用的字符串数据秘密共享方案。

We have developed and analyzed two transformations for lossless compression: generalized radix permutation (GRP) and compression by substring enumeration (CSE). The GRP transform was proposed as a parametric generalization of the BWT of the block-sorting data compression algorithm. Our proposed extension can be applied to arbitrary parameter values and can transform a string in time linear in the string length. We then analyze the CSE algorithm, and propose encoding models that achieve asymptotic optimality for stationary ergodic sources and Markov sources of any order. We also establish a concrete way for efficient implementation of CSE. CSE often produces more codewords than necessary. In order to reduce such redundancy, we propose a method for computing the maximum length of the substrings that should be enumerated in CSE to uniquely identify the input string. As for an application of these transformations, we propose a practical secret sharing scheme for string data.