HuffmanCodierung

Huffman coding is a lossless data compression algorithm. It was developed by David A. Huffman in 1952. The core idea behind Huffman coding is to assign shorter binary codes to more frequent characters and longer binary codes to less frequent characters. This leads to a reduction in the overall number of bits required to represent the data.

The process begins by constructing a Huffman tree. First, a frequency count of each unique symbol in the input data is determined. Then, these symbols are placed into a priority queue, ordered by their frequency. The two symbols with the lowest frequencies are taken from the queue, and a new internal node is created whose frequency is the sum of the frequencies of the two symbols. The two symbols become the children of this new node. This process is repeated until only one node remains, which is the root of the Huffman tree.

Once the tree is built, binary codes are generated by traversing from the root to each leaf node. Typically, a '0' is assigned to a left branch and a '1' to a right branch. The sequence of 0s and 1s encountered along the path from the root to a leaf represents the Huffman code for the symbol at that leaf. Because no code is a prefix of another code (prefix-free property), the original data can be uniquely reconstructed from the encoded bitstream. Huffman coding is widely used in various compression utilities and file formats, such as ZIP and JPEG.