A Post-Processing Mechanism for Sequential Use of Static and Dynamic Enumerative Code

摘要

A bijection between a complete set of source words and a complete set of codewords defines a variable-to-variable length (W) source code. Such code is used to parse sequentially a source sequence into codewords, In a naive parsing of a finite source sequence, the last incomplete source word requires a separate post-processing. However, if the sizes of the source and the code alphabet are the same and an end-offile is available, we show that there is an abstract and compact method for the post-processing. Furthermore, when a W code is a concatenation of VF (variable-to-fixed length) source code and a complete FV (fixed-to-variable length) integer code, we propose a simple enumerative code implementation, which can be used for processing the last word before the end-offile. This reduces the programming complexities compared with a naive post-processing. Furthermore, we apply the implementation to a dictionary trie based method for lossless data compressions, in particular, to the Ziv-Lempel incremental parsing algorithm. Finally, we extend the description in the binary alphabet to the one in a non-binary alphabet.