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
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500006/
• 关键词: 情報数理; 情報理論; データ圧縮; 符号化; ユニバーサル符号; 情報基礎; 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.

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

项目成果

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

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

• 发表时间: 2013
• 作者: 津久井香奈;横尾英俊
• 通讯作者: 横尾英俊

The universality and linearity of compression by substring enumeration

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

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

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

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

• 发表时间: 2012
• 作者: Naotake Tsuboi;Kazuhiro Furuhashi;Seiichi Matsuo;Shoichi Maruyama;T. Shirakawa and R. Uehara;横尾英俊
• 通讯作者: 横尾英俊

Asymptotic optimal compression via the CSE technique

通过 CSE 技术进行渐近最优压缩

• 发表时间: 2011
• 作者: 阿部 智子;堀之内 明日花;金 恒秀;古橋 和拡;秋山 真一;勝野 敬之;安田 香;尾崎 武徳;坪井 直毅;松尾 清一;丸山 彰一;Hidetoshi Yokoo
• 通讯作者: Hidetoshi Yokoo

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

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

• 发表时间: 2012
• 作者: T. Hibi;T. Fujito;横尾英俊
• 通讯作者: 横尾英俊