Bounding the Compression Loss of the FGK Algorithm

Faller, 1973, An adaptive system for data compression Gallager, 1978, Variations on a theme by Huffman, IEEE Trans. Inform. Theory, IT-24, 668, 10.1109/TIT.1978.1055959 Knuth, 1985, Dynamic Huffman coding, J. Algorithms, 6, 163, 10.1016/0196-6774(85)90036-7 Katajainen, 1995, Inplace calculation of minimum-redundancy codes Huffman, 1952, A method for the construction of the minimum redundancy codes, Proc. Inst. Radio Eng., 40, 1098 J. van Leeuwen, On the construction of Huffman trees, inProc. 3rd Int. Coll On Automata, Languages, and Programming, 1976, pp. 382–410. Moffat, 1998, Efficient construction of minimum-redundancy codes for large alphabets, IEEE Trans. Inform. Theory, 44, 1650, 10.1109/18.681345 Tarjan, 1985, Amortized computational complexity, SIAM J. Appl. Discrete Methods, 6, 306, 10.1137/0606031 Vitter, 1987, Design and analysis of dynamic Huffman codes, J Assoc. Comput. Mach., 34, 10.1145/31846.42227 Vitter, 1989, Algorithm 673: Dynamic Huffman coding, ACM Trans. Math. Software, 15, 158, 10.1145/63522.214390