Worst-case Redundancy of Optimal Binary AIFV Codes and their Extended Codes

Weihua Hu, Hirosuke Yamamoto, Junya Honda

Introduction

In the realm of lossless data compression, Huffman codes have long been considered the standard for instantaneous fixed-to-variable (FV) length coding. While optimal within the class of prefix-free codes, Huffman coding suffers from a significant theoretical drawback: its redundancy—the difference between the average codeword length and the source entropy—can be as high as 1 bit per symbol. To mitigate this, practitioners often resort to block coding (coding sequences of symbols), which reduces redundancy at the cost of an exponential increase in the code tree's memory footprint.

Almost Instantaneous Fixed-to-Variable (AIFV) codes offer a compelling alternative. By utilizing multiple code trees and allowing symbols to be assigned to internal nodes, AIFV codes achieve better compression than Huffman codes with only a linear increase in memory. This paper provides the first tight theoretical bounds on the redundancy of binary AIFV codes, proving a worst-case redundancy of $1/2$ bits, and extends these results to $m$-tree variants.

The AIFV Coding Framework

AIFV codes generalize instantaneous codes by employing a set of code trees. In a binary AIFV code, two trees, $T_0$ and $T_1$, are typically used. Unlike Huffman trees, where symbols are restricted to leaves, AIFV trees can assign symbols to "master nodes"—incomplete internal nodes that have only one child.

Example of AIFV code trees $T_0$ and $T_1$ for a four-symbol alphabet. Square nodes represent master nodes where symbols can be assigned, introducing a controlled decoding delay.

When a symbol is decoded at a master node, the decoder experiences a one-bit delay before the symbol can be fully output, and the coding process transitions to a different tree. This mechanism allows for shorter codewords for high-probability symbols, effectively "breaking" the prefix-free constraint of standard Huffman codes while maintaining decodability.

Theoretical Redundancy Bounds

Prior to this work, the redundancy of optimal binary AIFV codes was only known to be bounded by 1, the same as Huffman codes. Through a rigorous analysis involving tree transformations and Markov chain modeling of tree transitions, the authors demonstrate that the worst-case redundancy is exactly $1/2$.

The proof leverages the "sibling property" of Huffman trees to construct AIFV trees that guaranteed performance improvements. By modeling the tree-switching process as a Markov chain, the authors calculated the stationary probabilities of being in each tree state, allowing for a precise determination of the average codeword length. This $1/2$ bit bound matches the redundancy achieved by Huffman coding on pairs of symbols ($\mathcal{X}^2$) but requires significantly less memory.

Extended AIFV Codes and the $1/m$ Conjecture

The paper further generalizes the AIFV framework to $m$ trees (AIFV-$m$), where the maximum decoding delay is $m-1$ bits. The authors prove that for $m = 2, 3,$ and $4$, the worst-case redundancy is $1/m$.

This result is particularly significant for memory-constrained applications. To achieve $1/m$ redundancy with Huffman coding, one must code blocks of $m$ symbols, leading to a tree size of $O(K^m)$ for an alphabet of size $K$. In contrast, an AIFV-$m$ code achieves the same redundancy with a memory footprint of only $O(mK)$. The authors conjecture that this $1/m$ bound holds for all $m$, suggesting a fundamental relationship between the number of trees (and thus the allowed delay) and the achievable compression efficiency.

Conclusion

This research establishes a firm theoretical foundation for AIFV codes, proving they are twice as efficient as Huffman codes in the worst case for the binary 2-tree setting. The introduction of extended AIFV codes provides a scalable path toward entropy, offering a memory-efficient alternative to block-based Huffman coding. Future work remains to prove the $1/m$ redundancy conjecture for $m \ge 5$ and to refine construction algorithms for large-scale practical applications.

Summary updated

Abstract

Binary AIFV codes are lossless codes that generalize the class of instantaneous FV codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived in terms of $p_{\max}\geq$1/2, where $p_{\max}$ is the probability of the most likely source symbol. Additionally, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$-bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4.$
BibTeX
@article{hu2017worst,
  author = {Weihua Hu and Hirosuke Yamamoto and Junya Honda},
  title = {{Worst-case Redundancy of Optimal Binary AIFV Codes and their Extended Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=Gdx_eCRMYe},
}
Figure