Google Searching

Info

Jumat, 09 Maret 2012

Huffman Coding in a Tree Diagram

Huffman code is basically Initialize_model code prefix (prefix code) which is a set that contains a set of binary code. Prefix code is represented as a labeled binary tree where each side is labeled 0 (left branch) or 1 (right branch). Series of bits that form on each path from the root to leaf is a prefix code for the character that matched.
This code also has a wide variety including:

1. Adaptive Huffman coding
2. Length-Limited Huffman Coding
3. N-Ary Huffman Template Algorithm
4. Huffman With Unequal Letter Costs

1. Variations various Huffman Code

A. Adaptive Huffman Coding
Adaptive methods are used at the time of renewal (update) the new algorithm models both the process of compression and decompression
Basic Concept:
Encoder:
Initialize_model
Repeat for each character
(
Encode character
Update_model
)
Decoder
Initialize_model
Repeat for each character
(
Decode character
Update_model
)
 
The problem is how to update the model consists of algorithms that increase the number and update the Huffman tree. The trick is to update the tree where it is the compression / nirmampat. Huffman tree initialized with a single node, known as Not-Yet-Transmitted (NYT) Code that is sent each time a new character is found. The algorithm works with a unique numbering on the nodes with different number of leaves.

Lawyer steps update the model
1. If the code was first discovered NYT, then add the two nodes at node NYT. One node as a node NYT and other node as a leaf. Add the number of leaves. If not the NYT, straight to the leaves.

2. If the block does not have the highest rates, exchange with the highest number of blocks.

3. Add the number of node.

4. Check whether the node is the root node. If not go to the parent node.

B. Length-Limited Huffman Coding

Huffman variation is used to obtain the depth of the smallest distance from a symbol, with the restriction that the length of each of which included no less than a given constant value. This method is usually used with GNU gzip.
The steps in Method Length-Limited Huffman are:

1. Selecting two or more symbols to be compressed

2. Combine these symbols and replace them with pseudo-symbol and its frequency.

3. Perform the above steps are iterative until all the nodes that have a single root node.

4. If these nodes have the same frequency, then choose the node with the shortest depth.

C. Binary Huffman Template Algorima

This algorithm is similar to the ordinary Huffman algorithm. The difference, Huffman tree used in this algorithm has more than two roots (0 and 1). While the Huffman template algorithm, allowing to use non-numerical size (the size and frequency in addition to costs).

D. Huffman With Unequal Letter Costs
In this method there is a problem where a set of code that consists of several letters by frequency of occurrence and cost (cost) is different. This method is intended to find a prefix code (prefix code) and calculate the minimum cost (minimum cost). Prefix code is a set of prefix code-free. Cost (cost) of these is the amount of the cost of each letter in the code.
General steps method of Huffman codes with Unequal Letter Cost:

1. Looking for K-prefix code is optimal.

2. Changing K-prefix code into the optimal prefix code.

3. Having obtained the code and then calculate the cost (cost) of his.

Conclusion
Huffman codes proved to have many variations, among them the Adaptive Huffman Code, Code Length-limited Huffman, n-ary Huffman template algorithm, and Huffman codes with unequal letter costs. Various techniques can be used in applications different, but generally used for data compression. This naturally happens because the essence of all the variations of this technique is similar to Huffman codes, namely solving the optimization problem data.


LinkWithin

Related Posts Plugin for WordPress, Blogger...

Mobi Info

...

Lazada Promo