Huffmann Coding


Huffmann Coding Techniques

 Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file)
Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix code (sometimes called "prefix-free codes") (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code.
Although Huffman coding is optimal for a symbol-by-symbol coding (i.e. a stream of unrelated symbols) with a known input probability distribution, its optimality can sometimes accidentally be over-stated. For example, arithmetic coding and LZW coding often have better compression capability.
Given
A set of symbols and their weights (usually proportional to probabilities).
Find
A prefix-free binary code (a set of codewords) with minimum expected codeword length (equivalently, a tree with minimum weighted path length).
Input.
Alphabet , which is the symbol alphabet of size n.
Set , which is the set of the (positive) symbol weights (usually proportional to probabilities), i.e. .

Output.
Code , which is the set of (binary) codewords, where ci is the codeword for .

Goal.
Let be the weighted path length of code C. Condition: for any code .

 
Input (A, W)
Symbol (ai)
a
b
c
d
e
Sum
Weights (wi)
0.10
0.15
0.30
0.16
0.29
= 1
Output C
Codewords (ci)
000
001
10
01
11

Codeword length (in bits)
(li)
3
3
2
2
2
Weighted path length
(li wi )
0.30
0.45
0.60
0.32
0.58
L(C) = 2.25
Optimality
Probability budget
(2-li)
1/8
1/8
1/4
1/4
1/4
= 1.00
Information content (in bits)
(−log2 wi) ≈
3.32
2.74
1.74
2.64
1.79

Entropy
(−wi log2 wi)
0.332
0.411
0.521
0.423
0.518
H(A) = 2.205

For any code that is biunique, meaning that the code is uniquely decodable, the sum of the probability budgets across all symbols is always less than or equal to one. In this example, the sum is strictly equal to one; as a result, the code is termed a complete code. If this is not the case, you can always derive an equivalent code by adding extra symbols (with associated null probabilities), to make the code complete while keeping it biunique.
In general, a Huffman code need not be unique, but it is always one of the codes minimizing L(C).

Comments

Post a Comment

Popular posts from this blog

Handling of Skew

Handling of Skew 􀂄 The distribution of tuples to disks may be skewed — that is, some disks have many tuples, while others may have fewer tuples. 􀂄 Types of skew: 􀃌 Attribute-value skew. 􀂾 Some values appear in the partitioning attributes of many tuples; all the tuples with the same value for the partitioning attribute end up in the same partition. 􀂾 Can occur with range-partitioning and hash-partitioning. 􀃌 Partition skew. 􀂾 With range-partitioning, badly chosen partition vector may assign too many tuples to some partitions and too few to others. 􀂾 Less likely with hash-partitioning if a good hash-function is chosen. Handling Skew in Range-Partitioning 􀂄 To create a balanced partitioning vector (assuming partitioning attribute forms a key of the relation): 􀃌 Sort the relation on the partitioning attribute. 􀃌 Construct the partition vector by scanning the relation in sorted order as follows. 􀂾 After every 1/nth of the relation has been read, the value...
Read more

Fragment-and-Replicate Join

Fragment-and-Replicate Join 􀂄 Partitioning not possible for some join conditions 􀃌 e.g., non-equijoin conditions, such as r.A > s.B. 􀂄 For joins were partitioning is not applicable, parallelization can be accomplished by fragment and replicate technique 􀃌 Depicted on next slide 􀂄 Special case – asymmetric fragment-and-replicate: 􀃌 One of the relations, say r, is partitioned; any partitioning technique can be used. 􀃌 The other relation, s, is replicated across all the processors. 􀃌 Processor Pi then locally computes the join of ri with all of s using any join technique. 􀂄 General case: reduces the sizes of the relations at each processor. 􀃌 r is partitioned into n partitions,r0, r1, ..., r n-1;s is partitioned into m partitions, s0, s1, ..., sm-1. 􀃌 Any partitioning technique may be used. 􀃌 There must be at least m * n processors. 􀃌 Label the processors as 􀃌 P0,0, P0,1, ..., P0,m-1, P1,0, ..., Pn-1m-1. 􀃌 Pi,j computes the join of ri with sj. In ...
Read more

USER INTERFACE DESIGN FOR ANNA UNIVERSITY SYLLABUS

Unit – I Introduction Objective To Understand the definition and importance of User Interface Design To know about the concept, advantages and applications of GUI and Web interface User Interface Design Definition • User interface design is a subset of a field of study called human-computer interaction (HCI). Human-computer interaction is the study, planning, and design of how people and computers work together so that a person’s needs are satisfied in the most effective way. • The user interface is the part of a computer and its software that people can see, hear, touch, talk to, or otherwise understand or direct. The user interface has essentially two components: input and output. • Input is how people communicate his needs to the system using keyboard or any pointing device and output is how the system returns processing result to user through screen or sound. • The best interface is one which has proper design with combination of effective input and output mechanisms. Importance of...
Read more