Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

See optional textbook for how to do this.

Step 1: Frequency Counting

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Counts of each character:

• 我: 35
• 刚: 15
• 是: 17
• 爸: 17
• 李: 16�

Step 1: Frequency Counting

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Relative frequency of each character:

• 我: 35 / 100 = 0.35
• 刚: 15 / 100 = 0.15
• 是: 17 / 100 = 0.17
• 爸: 17 / 100 = 0.17
• 李: 16 / 100 = 0.16�

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

See optional textbook for how to do this.

Step 2: Building the Decoding Trie and Encoding Array

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我�

我

爸

是

李

刚

0.35

0.17

0.17

0.16

0.15

我

爸

是

李

刚

0

1

0

1

1

0

0

1

Step 2: Building the Decoding Trie and Encoding Array

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我�

我

爸

是

李

刚

0

1

0

1

1

0

0

1

Decoding Trie

Encoding Map

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…

See optional textbook for how to do this.

我

爸

是

李

刚

0

1

0

1

1

0

0

1

0.35

0.17

0.17

0.16

0.15

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…0

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…00

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…00111

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…00111111

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…00111111111

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…00111111111101

Decoding Trie

Huffman Compression Example Demo

Given input text: 我我刚刚刚是我是我刚李刚我李是爸李爸李是李我我李刚是我是刚爸是刚我爸我李是是李是我我刚爸是李我我我是爸我是我爸是我爸是我是刚我是爸刚爸我刚我我刚爸我我爸我刚爸爸李李李李我我爸李我我刚爸李我我李我爸我我

​

Step 1: Count frequencies.

Step 2: Build encoding array and decoding trie.

Step 3: Write decoding trie to output.huf.

Step 4: Write codeword for each symbol to output.huf.

​

Output bits: 010101010101001…00111111111101…

Decoding Trie

Codewords

我

爸

是

李

刚

0

1

0

1

1

0

0

1

0.35

0.17

0.17

0.16

0.15

Decoding Trie