### Algorithm Analysis

Huffman compression is based on huffman coding technique. The huffman coding creates an optimal binary tree that is constructed based on frequency of an item/character in a file.

character     frequency
A             20
B              2
C              7
D              7
F              2
G              1


The above following data will generate a binary tree starting from the characters having the lowest frequency, and construct till we use all the characters as follows:

Pass 1:
(A, 20) (C, 7) (D, 7) (B, 2) (F, 2) (G, 1)                      (A, 20) (C, 7) (D, 7) (**, 3)  (B, 2)
=>                                  /   \
/     \
(F, 2) (G, 1)

Pass 2:
(A, 20) (C, 7) (D, 7) (**, 3)  (B, 2)                           (A, 20) (C, 7) (D, 7) (**, 5)
/   \                                                           /   \
/     \                                                         /     \
(F, 2) (G, 1)                   =>                              (**, 3) (B, 2)
/   \
/     \
(F, 2) (G, 1)

Pass 3:
(A, 20) (C, 7) (D, 7) (**, 5)                                    (A, 20) (C, 7) (**, 12)
/   \                                                     /   \
/     \                                                   /     \
(**, 3) (B, 2)                  =>                        (D, 7) (**, 5)
/   \                                                            /   \
/     \                                                          /     \
(F, 2) (G, 1)                                                   (**, 3) (B, 2)
/   \
/     \
(F, 2) (G, 1)

Pass 4:
(A, 20) (**, 12) (C, 7)                                           (A, 20) (**, 19)
/   \                                                             /   \
/     \                                                           /     \
(D, 7) (**, 5)                                                   (**, 12) (C, 7)
/   \                                                      /   \
/     \                               =>                   /     \
(**, 3) (B, 2)                                            (D, 7) (**, 5)
/   \                                                            /   \
/     \                                                          /     \
(F, 2) (G, 1)                                                    (**, 3) (B, 2)
/   \
/     \
(F, 2) (G, 1)

Pass 5 (Final), with huffman code:

Left Branch denoting 0 and right 1

(A, 20) (**, 19)                                                         (**, 39)
/   \                                                           /   \
/     \                                                      (0)/     \(1)
(**, 12) (C, 7)                                           <= (A, 20) (**, 19)
/   \                                                                 /   \
/     \                                                            (0)/     \(1)
(D, 7) (**, 5)                                    =>                  (**, 12) (C, 7) => 
/   \                                                          /   \
/     \                                                     (0)/     \(1)
(**, 3) (B, 2)                                         <= (D, 7) (**, 5)
/   \                                                                 /   \
/     \                                                               /     \(1)
(F, 2) (G, 1)                                                        (**, 3) (B, 2) => 
/   \
(0)/     \(1)
 <= (F, 2) (G, 1) => 

Final Huffman Codes:
character     frequency       Huffman Codes       Actual Binary
A             20                  0             01000001
B              2               1011             01000010
C              7                 11             01000011
D              7                100             01000100
F              2              10100             01000110
G              1              10101             01000111
__________________________________________________________________
39                 75                  312


Hence the resultant data is stored as binary written as ‘000101110110001001001010010100000010011111110000100100100000111010100011011000000’, which has 75 bits plus 5 digits appended to round off the remaining bits while storing in the file.

Source code is available on Github.

### To Run

g++ huffman.cpp
[a.exe | ./a.out] -c|-dc [filename_to_be_compressed]
(The order must be same: first: option to compress/decompress and then second: filename)


The file to be compressed will generate a file with extension ‘.abiz’, which is the compressed file and the output file which will be the uncompressed version of ‘.abiz’ file.

N.B. When using this program for compressing files other than ASCII based text files (e.g., audio (.mp3), video (.mp4), pdfs, document (.doc/.docx), etc.) may not result in any reduced size as this compresses files assuming that the file consists of ASCII character streams and not binary data. Images and videos are usually already compressed files using specialized algorithms.