Average-sense optimality and competitive optimality for almost instantaneous VF codes

One-shot coding and repeated coding are considered for the class of almost instantaneous variable-to-fixed length (AIVF) codes, C_AIVF, which includes some nonproper VF codes in addition to the class of proper VF codes, C_PVF. An algorithm is given to construct the average-sense optimal (a-optimal) AIVF code in one-shot coding that attains the maximum average parse length in C_AIVF. The algorithm can also be used to obtain an AIVF code with multiple parse trees, which can attain good performance for repeated coding. Generally, the a-optimal code for one-shot coding and the good code for repeated coding are more efficient than the Tunstall (1967) code in A-ary cases if A⩾3 although they coincide with the Tunstall code in the binary case. The competitively optimal (c-optimal) VF code is also considered for one-shot coding, and it is shown that the c-optimal code does not always exist in C_PVF and in C_AIVF. Furthermore, whenever the c-optimal code exists, the Tunstall code is c-optimal in C_PVF and the a-optimal code obtained by our algorithm is c-optimal in C_AIVF if A=2 or 3, but the a-optimal code is not always c-optimal in C_AIVF if A⩾4