Development of novel transform-based lossless compression schemes

新型基于变换的无损压缩方案的开发

基本信息

批准号：
23500006
负责人：
YOKOO Hidetoshi
金额：
$ 2.5万
依托单位：
Gunma University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2011
资助国家：
日本
起止时间：
2011 至 2013
项目状态：
已结题

项目摘要

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.

我们已经开发并分析了两种无损压缩的转换：广义放射线置换（GRP）和通过底带枚举（CSE）压缩。提出了GRP变换为块状数据压缩算法的BWT的参数概括。我们所提出的扩展名可以应用于任意参数值，并可以在字符串长度中变换字符串。然后，我们分析CSE算法，并提出编码模型，这些模型可为固定的厄神经源和任何顺序的马尔可夫源实现渐近最佳性。我们还建立了有效实施CSE的具体方式。 CSE通常会产生更多的代码字。为了减少这种冗余，我们提出了一种计算应在CSE中列举的基因的最大长度以唯一识别输入字符串的方法。至于这些转换的应用，我们为字符串数据提出了一个实用的秘密共享方案。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

記号列に対する変換に基づく秘密分散法

基于符号串变换的秘密共享方法

DOI：
发表时间：
2013
期刊：
影响因子：
0
作者：
津久井香奈;横尾英俊
通讯作者：
横尾英俊

The universality and linearity of compression by substring enumeration

子串枚举压缩的普适性和线性性

DOI：
发表时间：
2011
期刊：
影响因子：
0
作者：
前田　麻友子;小杉　智規;長屋　啓;前田　佳哉輔;佐藤　由香;小島　博;尾崎　武徳;佐藤　和一;丸山　彰一;松尾　清一;R. Uehara;Danny Dúbe and Hidetoshi Yokoo
通讯作者：
Danny Dúbe and Hidetoshi Yokoo

CSE 無ひずみデータ圧縮法の情報理論的解釈

CSE无失真数据压缩方法的信息论解释