際際滷

際際滷Share a Scribd company logo

Huffman Code Decoding

?
?
R
Rex Yuan

This document summarizes Huffman code decoding. It takes a sequence to be decoded and a character probability table as input. A binary tree is built from the probabilities, with left branches representing 1 and right 0. The time complexity is O(n^2) where n is the sequence length, as building the tree can resemble an unbalanced tree. Sample run times are provided for sequences of different lengths on 10 possible characters. Pseudocode provides an algorithm to traverse the tree and decode the sequence.

1 of 2
Hu?man Code Decoding Rex Yuan May 13, 2015 Hu?man Code Decoding We take a sequence to be decoded and a table of corresponding characters and their probabilities as input. Using the given characters and probabilities, this algorithm build a binary tree by always selecting the two characters with lowest probabilities and make them a subtree with the sum of their probabilities. When going from the root, each traversal to the left subtree represents a ￣1￣ and right a ￣0￣. Time Complexity Suppose we have a total of m possible character to be encoded and a sequence with length n to be decoded, the time complexity would be linear with regards to m and n, n2 + m, i.e., O(n2 ) because in worst case we will iterate through all characters and perform a tree- building operation which in worst case would resemble a completely un-balanced tree, and thus produce a recursion tree containing n levels, and the operations required for each level increments from 1 to n ? 1, in turn yielding O(n2 ) which dominates over the operations needed for decoding, m. Run Time Stats I created the following table using UNIX POSIX time function and round the mean time of 10 trials to ?ve digits after decimal point to calculate the time past. All samples have the ten possible characters to be encoded, that is 0 9. Variable input length implies the length of the sequence to be decoded. Run Time Stats Sample Input Length Hu?man Decoding 1 35 0.00031 2 37 0.00858 3 368 0.00902 1
Pseudo Code Algorithm 1 Hu?man Code Decoding Algorithm procedure DECODE(prob table, seq) tree = a key-value associating array, with each item¨s key the node in that subtree and value its current sum probability, according to probtable. code table = an array, with length of the how many characters in prob table, which maps each code to its corresponding decoded character with each code initialised as empty strings. while more than one node in tree do sml sub nodes = key of node with smallest probability in tree sec sub nodes = key of node with second smallest probability in tree for node in sml sub nodes do code table[node].key = ￣1￣ + code table[node].key end for for node in sec sub nodes do code table[node].key = ￣0￣ + code table[node].key end for tree[sml sub nodes + sec sub nodes] = tree[sml sub nodes] + tree[sec sub nodes] delete tree[sml sub nodes] delete tree[sec sub nodes] end while temp = ￣￣ result = ￣￣ for code in seq do temp = temp + code if temp in code table then result = result + code table[temp] temp = ￣￣ end if end for return result end procedure 2

More Related Content

Huffman Code Decoding

  • 1. Hu?man Code Decoding Rex Yuan May 13, 2015 Hu?man Code Decoding We take a sequence to be decoded and a table of corresponding characters and their probabilities as input. Using the given characters and probabilities, this algorithm build a binary tree by always selecting the two characters with lowest probabilities and make them a subtree with the sum of their probabilities. When going from the root, each traversal to the left subtree represents a ￣1￣ and right a ￣0￣. Time Complexity Suppose we have a total of m possible character to be encoded and a sequence with length n to be decoded, the time complexity would be linear with regards to m and n, n2 + m, i.e., O(n2 ) because in worst case we will iterate through all characters and perform a tree- building operation which in worst case would resemble a completely un-balanced tree, and thus produce a recursion tree containing n levels, and the operations required for each level increments from 1 to n ? 1, in turn yielding O(n2 ) which dominates over the operations needed for decoding, m. Run Time Stats I created the following table using UNIX POSIX time function and round the mean time of 10 trials to ?ve digits after decimal point to calculate the time past. All samples have the ten possible characters to be encoded, that is 0 9. Variable input length implies the length of the sequence to be decoded. Run Time Stats Sample Input Length Hu?man Decoding 1 35 0.00031 2 37 0.00858 3 368 0.00902 1
  • 2. Pseudo Code Algorithm 1 Hu?man Code Decoding Algorithm procedure DECODE(prob table, seq) tree = a key-value associating array, with each item¨s key the node in that subtree and value its current sum probability, according to probtable. code table = an array, with length of the how many characters in prob table, which maps each code to its corresponding decoded character with each code initialised as empty strings. while more than one node in tree do sml sub nodes = key of node with smallest probability in tree sec sub nodes = key of node with second smallest probability in tree for node in sml sub nodes do code table[node].key = ￣1￣ + code table[node].key end for for node in sec sub nodes do code table[node].key = ￣0￣ + code table[node].key end for tree[sml sub nodes + sec sub nodes] = tree[sml sub nodes] + tree[sec sub nodes] delete tree[sml sub nodes] delete tree[sec sub nodes] end while temp = ￣￣ result = ￣￣ for code in seq do temp = temp + code if temp in code table then result = result + code table[temp] temp = ￣￣ end if end for return result end procedure 2