Enumeration and Coding of Compact Code Trees for Binary AIFV Codes
Kengo Hashimoto, Ken‐ichi Iwata, H. Yamamoto · 2019
We extend the concept of compact code trees, i.e., canonical code trees, of Huffman codes to the case of binary AIFV (almost instantaneous fixed-to-variable length) codes. We give an algorithm to enumerate the number of all compact AIFV code trees by using a bijection between the compact AIFV code trees and the proper sequences defined in this paper. Based on the enumeration of compact AIFV code trees, we give an efficient coding scheme to describe the compact AIFV code trees, which is required when we send a decoder the information of code trees used in the encoding of source sequences.