Coding of binary AIFV code trees

Binary AIFV codes, which can attain better compression rate than Huffman codes, uses two code trees that may have incomplete internal nodes, and source symbols are assigned to some internal nodes in addition to leaves. Although the code trees of Huffman codes, which are full binary trees, are well studied, the AIFV code trees have not been yet studied in detail. In this paper, we show that there exists a bijection between binary AIFV code trees and Schroder paths, and give two coding schemes to represent Schroder paths. The first one is a fixed length coding scheme, which has O(n2) time-complexity. The second one is a variable length coding scheme using a simple AIFV code. The latter attains O(n) time-complexity, but the coding rate has loss less than 4.1% of the optimal coding rate.