A Compression Cryptosystem is a single coding process, the output of which is both reduced in space and secure against unauthorized decoding. Considering Huffman coding, this pa-per proposes to apply repeatedly minor changes to the compression model, with negligible deterioration of its optimality. The cumulative impact of a large number of such changes leads to completely different ciphertexts, which can be decoded only if a given secret key is known. The security of the system is based on the NP-completeness of a problem related to breaking the code. Several variants are suggested, and their results are tested in various settings, including for security against chosen plaintext attacks.

Unlike the uniform treatment of symbols in different locations of an input file, a new approach is taken in the weighted dynamic compression method suggested in [1], which assigns higher priority to closer to be encoded symbols by means of an increasing weight function. The weighted method is especially suited for the encoding of files with locally skewed distributions. Empirical results have shown that weighted techniques can improve beyond the lower bound given by the entropy for static encoding.

Extending recently suggested methods, a new dynamic compression algorithm is proposed, which assigns larger weights to characters that have just been coded by means of an increasing weight function. Empirical results present its efficient compression performance, which, for input files with locally skewed distributions, can improve beyond the lower bound given by the entropy for static encoding, at the price of slower running times for compression, and comparable time for decompression.

Huffman coding is known to be optimal in case the alphabet is known in advance, the set of codewords is fixed and each codeword consists of an integral number of bits. If one of these conditions is violated, optimality is not guaranteed. In the dynamic variant of Huffman coding the encoder and decoder maintain identical copies of the model; at each position, the model consists of the frequencies of the elements processed so far. After each processed element σ, the model is updated by incrementing the frequency of σ by 1, while the other frequencies remain the same. An enhanced dynamic Huffman coding named forward looking coding [2] starts with the full frequencies, similar to the static variant, and then decreases them progressively. For this method, after each processed element σ, the model is altered by decrementing the frequency of σ by 1, while the other frequencies remain the same. Forward looking Huffman coding has been shown to be always better by at least m-1 bits than static Huffman coding. A hybrid method, exploiting both the classical backward and the new forward approaches is proposed in FKS, and has been shown to be always at least as good as the forward looking Huffman coding. If the model is learned adaptively, as in the traditional backward looking codings, no description of the model is needed, since the model is updated by the encoder and the decoder in synchronization. However, in the other mentioned versions, the details of the chosen model on which the method relies, are needed for the decoding and should be adjoined to the compressed file, for example, as an header. The contribution of this work is as follows: we first define a new generic coding method which we call weighted coding, encompassing all mentioned variants (static, forward and backward) as special cases. Second, a new special case called positional is suggested, and shown to be always at least as good as the forward looking coding. Third, we present empirical results that show practical improvements of the proposed method, even when the encoded file includes the model description. It is important to stress that all the methods can in fact be applied to every adaptive coding technique, in particular to arithmetic coding or PPM.