Research on Coding Trees for Data Compression and Tree Search

点击翻译按钮获取中文摘要

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.