Analysis of Multiplexed Parse Trees for Almost Instantaneous VF Codes

Almost Instantaneous VF code proposed by Yamamoto and Yokoo in 2001, which is one of the variable-length to-fixed-length codes, uses a set of parse trees and achieves a good compression ratio. However, it needs much time and space for both encoding and decoding than a conventional VF code. Yoshida and Kida showed in 2010 that the set of trees can be multiplexed into a compact single tree and the original encoding and decoding procedures can be simulated on the single tree. They also showed a lower bound of the number of nodes reduced from the original multiple parse trees. In this paper we give a lower bound of the number of nodes in the multiplexed parse tree and an upper bound of the number of nodes reduced from the original trees.