Developing an Algorithm to Generate Code Words Using Huffman Coding

To implement an algorithm capable of building the tree that generates the binary code words for the character in a data file using Java:

  1. Use a priority queue to store nodes with the character frequency.
  2. Repeatedly join the two nodes with the least frequencies until you are left with a single node. The source code for this algorithm is as follows:
for (int i = 0; i < N - 1; i++) {
Node n = new Node();
n.left = pq.remove();
n.right = pq.remove();
n.frequency = n.left.frequency + n.right.frequency;
pq.add(n);
}
Snippet 4.2: Huffman code. Source class name: Huffman

Go to https://goo.gl/indhgT to access the full code.

We make use of a priority queue to store our nodes, making it very efficient (O(logn)) to extract the node with the least frequency. A priority queue is like a queue, or a stack, but each element has an additional priority associated with it. An element with a higher priority is served before an element with lower priority. Priority queues are usually implemented using heaps, which usually provide O(1) time to find the element with a higher priority, O(logn) to insert an element, and O(logn) time to remove the element with a higher priority.

To analyze the running time of Huffman's algorithm, let's break it down into steps. We first go through each character in the frequencies map and build a node that we later insert in the priority queue. It takes O(logn) time to insert a node in the priority queue. Since we go through each character, it takes O(nlogn) to create and initially populate the priority queue. The second for loop executes exactly n-1 times. Each time, we perform two removes from the priority queue, each one taking O(logn) time. In its whole, the for loop takes O(nlogn) time. We thus have two steps, each taking O(nlogn) time, which leaves us at a total running time on a set of n characters of O(nlogn).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.217.107.229