Huffmankódolást

Huffmankódolást, known in English as Huffman coding, is a lossless data compression algorithm developed by David A. Huffman in 1952. It is a method for constructing prefix codes based on the frequencies of the symbols in the input data. The core idea is to assign shorter codes to more frequent symbols and longer codes to less frequent symbols, thereby reducing the overall number of bits required to represent the data.

The algorithm works by building a binary tree, often called a Huffman tree. Initially, each unique symbol is represented as a leaf node in the tree, with its weight corresponding to its frequency. The algorithm then repeatedly merges the two nodes with the lowest weights into a new parent node, whose weight is the sum of its children's weights. This process continues until only one node, the root of the Huffman tree, remains.

Once the tree is constructed, a unique binary code is assigned to each symbol by traversing the path from the root to the symbol's leaf node. Typically, a '0' is assigned for a left branch and a '1' for a right branch, or vice versa. The resulting codes are prefix codes, meaning that no code is a prefix of another code. This property is crucial for unambiguous decoding.

Huffmankódolást is widely used in various data compression applications, including file archiving formats like ZIP and GZIP, and in image and audio compression standards such as JPEG and MP3. Its efficiency depends on the redundancy present in the data; the more predictable the data, the higher the compression ratio achievable. While effective, it requires two passes over the data: one to calculate frequencies and build the tree, and another to encode.