Sıkıştırma - Huffman Coding

Giriş
Açıklaması şöyle. Bu yöntem bir çok unix komutunda kullanılmış.

This method is named after D.A. Huffman, who developed the procedure in the 1950s.

Temel olarak iki çeşit Huffman Coding var.
1. Klasik Huffman Coding. Bu yöntem önceden hesaplanmış bir encoding table kullanılır.
2. Adaptive Huffman Coding. Bu yöntemde encoding table çalışma esnasında hesaplanır ve veri ile birlikte gönderilir.

1. Klasik Huffman Coding
Açıklaması şöyle.

To implement Huffman or arithmetic encoding, the compression and uncompression algorithms must agree on the binary codes used to represent each character (or groups of characters). This can be handled in one of two ways. The simplest is to use a predefined encoding table that is always the same, regardless of the information being compressed. More complex schemes use encoding optimized for the particular data being used. This requires that the encoding table be included in the compressed file for use by the uncompression program. Both methods are common.

Eğer encoding table veri ile gönderilecekse veri ilk halinden daha büyük olabilir. Açıklaması şöyle

Huffman coding is a nearly optimal prefix code. It uses shorter bit patterns for more commonly occurring symbols, thus minimizing the amount of space required. Of course, you need to transmit the Huffman tree separately, so Huffman coding does not always compress your data.

2. Adaptive Huffman Coding
Açıklaması şöyle.

Adaptive Huffman coding may be a better fit for the description, as it avoids the need to precompute and share the code tree

3. Arithmetic Encoding
Açıklaması şöyle.

A more sophisticated version of the Huffman approach is called arithmetic encoding. In this scheme, sequences of characters are represented by individual codes, according to their probability of occurrence. This has the advantage of better data compression, say 5-10%. Run-length encoding followed by either Huffman or arithmetic encoding is also a common strategy. As you might expect, these types of algorithms are very complicated, and usually left to data compression specialists.

Kayıp
Huffman kayıpsızdır. Açıklaması şöyle

Huffman code is a particular type of optimal prefix code for characters. It is commonly used for lossless data compression. It is a variable-length code derived from frequency of occurrence.

Prefix Yapısı
Huffman binary tree kullanarak bir prefix code yapısı kurar. Bu binary tree'de en sık görülen elemanlar en üste doğrudur. Böylece bunların kullandıkları bit sayısı azalır. Binary tree'nin kurulması ile ilgili açıklama şöyle

A binary tree will help us to derive our variable-length codes. At each step, we take the two letters with the lowest frequency, merge them under a parent node and assign their total frequency to their parent (a priority queue may help us do that). We will continue doing this until all letters are merged under a single root. 

Prefix Code yapısında hiç bir eleman bir diğerinin kodu ile başlamaz. Yani şöyle bir yapı görülmez.

a=0, b=1, c=10, d=01, e=11

Eğer görülseydi 1001 gelince 1001=cab, 1001=bad ayrımı yapılamazdı.

Huffman Tree oluştururken hangi dalın 0 hangisinin 1 olduğunu bilmek gerekir.

Örnek

Elimizde "do it or not" için bir binary tree olsun

Her karakter için encoding şöyle olur