Research on Coding Trees for Data Compression and Tree Search

用于数据压缩和树搜索的编码树研究

• 批准号: 12650364
• 负责人: YAMAMOTO Hirosuke
• 金额: $ 0.7万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12650364/
• 关键词: Source coding; Coding tree; Search tree; Competitive optimality; Avarage-sense optinality; FV code; VF code; Alphabetic code; アルファベッティック符号

Concerning coding trees and search trees in data compression algorithms and search algorithms, the following results are obtained.1. FV (fixed-to-Variable length) codes : (1) In previous researches, we have given a necessary condition for the Huffman code to be competitively optimal. In this study, we proved by introducing an index of competitive dominance that the condition is also sufficient.(2) It is shown that in the class of alphabetic codes, the competitive optimal code does not always exist. Furthermore, if the competitively optimal alphabetic code exists, then it is also optimal in the average-sense.2. VF (variable-to-Fixed length codes : (1) The AIVF (Almost Instantaneous VF) code are newly defined as a class of VF codes.(2) For one-shot coding, it is shown how to construct the optinal AIVF code in the average-sense.(3) It is shown that in one-shot codin, the competitively optimal proper VF code is always average-sense optimal in the class of proper VF codes, but the competitively optimal AIVF code does not always optimal in the average-sense.(4) In repeated coding, AIVF codes with multiple code trees can atain better compression performanece than the Tustall code that is optimal in the class of the proper VF codes.

关于数据压缩算法和搜索算法中的编码树和搜索树，得到了如下结果. FV（Fixed-to-Variable Length）码：（1）在以往的研究中，我们给出了霍夫曼码竞争最优的一个必要条件。在这项研究中，我们通过引入竞争优势指数证明了该条件也是充分的。(2)结果表明，在字母码类中，竞争最优码并不总是存在。此外，如果存在竞争最优字母码，那么它也是平均意义下的最优字母码。VF（Variable-to-Fixed Length Codes）：（1）AIVF（Almost Instantaneous VF）码是新定义的一类VF码。(2)对于单次编码，给出了如何构造平均意义下的最优AIVF码。(3)结果表明，在单次编码中，竞争最优的真VF码在真VF码类中总是平均意义上最优的，而竞争最优的AIVF码并不总是平均意义上最优的. (4)在重复编码中，多码树AIVF码比Tustall码具有更好的压缩性能，Tustall码是同类VF码中最优的。

项目成果

Hirosuke Yamamoto, and Hidetoshi Yokoo: "Average-Sense Optinality and Competitive Optimality for Almost Instantaneous VF Codes"IEEE Trans. Information Theory. vol. 47, no. 6. 2174-2184 (2001)

Hirosuke Yamamoto 和 Hidetoshi Yokoo：“几乎瞬时 VF 代码的平均感知最优性和竞争最优性”IEEE Trans。

H.Yamamoto, H.Yokoo: "Average-Sense Optimality and Competitive Optimality for Almost Instantaneous VF Codes"IEEE Trans. on Information Theory. 47・6. 2171-2181 (2001)

H. Yamamoto、H. Yokoo：“几乎瞬时 VF 代码的平均感知最优性和竞争最优性”IEEE Trans 信息论 47・6 (2001)。

H.Yamamoto, H.Yokoo: "Average-Sense Optimality and Competitive Optimality for Almost Instantaneous VF Codes"IEEE Trans on Information Theory. 47. 2174-2184 (2001)

H.Yamamoto、H.Yokoo：“几乎瞬时 VF 代码的平均感知最优性和竞争最优性”IEEE Trans on Information Theory。