Devising a coding mechanism for compression algorithms

Canonical Huffman Coding is a data compression algorithm still widely used in many applications. Originally, to produce canonical Huffman codes, first, the code tree is created, then from the leaves to the root, code lengths are obtained. Canonical codes are then calculated from these lengths. Instead of this multi-stage process, Algebraic Canonical Huffman Coding (ACHC), which calculates the code lengths in one stage through direct calculation, is proposed in this thesis. After the calculation of the lengths, the codewords corresponding to each length are calculated by binary addition. Time complexity is O(n) for ACHC and is O(n(logn+l)) for classical canonical Huffman coding. Space complexity is O(5n) standard for Huffman coding and O(n) for ACHC. This means memory saving is 80%. However, the average bit length per symbol is not usually optimal but is much closer to the optimal than similar methods. Therefore, the second algorithm (ES_ACHC) that optimizes the ACHC algorithm with the Evolutionary Strategies algorithm, is also proposed in this thesis. With this algorithm, optimum canonical codes were obtained with shorter loops. The adaptive application of the ACHC algorithm (A_ACHC) is the third contribution of this thesis to the existing literature. With the A_ACHC algorithm, 80% of memory savings have been achieved with the same compression ratio compared to the well-known Vitter algorithm. Keywords: Canonical Huffman, Adaptive Huffman, Encoding, Evolution Strategies, Data Compression