Speeding Up AIFV-m Dynamic Programs by m–1 Orders of Magnitude
Mordecai J. Golin, Albert John Lalim Patupat · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
AIFV-m coding is a method for constructing lossless codes for memoryless sources that provide better worst-case redundancy than Huffman codes. It achieves this by using m code trees instead of one and also by allowing some bounded delay in the decoding process. The process for constructing optimal AIFV-m on n source symbols is based on multiple calls to a local optimization subroutine. Local optimization was originally performed using Integer Linear Programming, which was later replaced by an O(mn2m+1)-time Dynamic Program. The running time for m = 2 was further improved to O(n3), but the speedup technique was not applicable to m > 2. This paper introduces a new dynamic programming approach that yields a general O(mnm+2)-time algorithm.