Research on Coding Trees for Data Compression and Tree Search

关于数据压缩算法和搜索算法中的编码树和搜索树，得到了如下结果. 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码中最优的。

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.