Question

In: Computer Science

Read through "The Huffman Code" on page 415 of the book. Write a program to implement...

Read through "The Huffman Code" on page 415 of the book. Write a program to implement Huffman coding and decoding. It should do the following: Accept a text message, possibly of more than one line. Create a Huffman tree for this message. Create a code table. Encode the message into binary. Decode the message from binary back to text. in JAVA

Solutions

Expert Solution

solution:

given data:

JAVA

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Map.*;

class HuffmanNode implements Comparable<HuffmanNode> {
int frequency;
char data;
HuffmanNode left, right;

public int compareTo(HuffmanNode node) {
return frequency - node.frequency;
}
}

public class Solution
{
private static Map<Character, String> charPrefixHashMap = new HashMap<>();
   static HuffmanNode root;

   public static void main(String[] args) {

       String test = "This is a new message";
       System.out.println("Original Text = "+test);
       String s = encode(test);
       decode(s);

   }

   private static HuffmanNode buildTree(Map<Character, Integer> freq) {

       PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
       Set<Character> keySet = freq.keySet();
       for (Character c : keySet) {

           HuffmanNode huffmanNode = new HuffmanNode();
           huffmanNode.data = c;
           huffmanNode.frequency = freq.get(c);
           huffmanNode.left = null;
           huffmanNode.right = null;
           priorityQueue.offer(huffmanNode);
       }
       assert priorityQueue.size() > 0;

       while (priorityQueue.size() > 1) {

           HuffmanNode x = priorityQueue.peek();
           priorityQueue.poll();

           HuffmanNode y = priorityQueue.peek();
           priorityQueue.poll();

           HuffmanNode sum = new HuffmanNode();

           sum.frequency = x.frequency + y.frequency;
           sum.data = '-';

           sum.left = x;

           sum.right = y;
           root = sum;

           priorityQueue.offer(sum);
       }

       return priorityQueue.poll();
   }


   private static void setPrefixCodes(HuffmanNode node, StringBuilder prefix) {

       if (node != null) {
           if (node.left == null && node.right == null) {
               charPrefixHashMap.put(node.data, prefix.toString());

           } else {
               prefix.append('0');
               setPrefixCodes(node.left, prefix);
               prefix.deleteCharAt(prefix.length() - 1);

               prefix.append('1');
               setPrefixCodes(node.right, prefix);
               prefix.deleteCharAt(prefix.length() - 1);
           }
       }

   }

   private static String encode(String test) {
       Map<Character, Integer> freq = new HashMap<>();
       for (int i = 0; i < test.length(); i++) {
           if (!freq.containsKey(test.charAt(i))) {
               freq.put(test.charAt(i), 0);
           }
           freq.put(test.charAt(i), freq.get(test.charAt(i)) + 1);
       }

//        System.out.println("Character Frequency Map = " + freq);
System.out.println("Code Table");
freq.entrySet().forEach(entry->{
System.out.println(entry.getKey() + " ------------------- " + entry.getValue());
});
       root = buildTree(freq);

       setPrefixCodes(root, new StringBuilder());
       System.out.println("Character Prefix Map = " + charPrefixHashMap);
       StringBuilder s = new StringBuilder();

       for (int i = 0; i < test.length(); i++) {
           char c = test.charAt(i);
           s.append(charPrefixHashMap.get(c));
       }

       return s.toString();
   }

   private static void decode(String s) {

       StringBuilder stringBuilder = new StringBuilder();

       HuffmanNode temp = root;

       System.out.println("Encoded: " + s);

       for (int i = 0; i < s.length(); i++) {
           int j = Integer.parseInt(String.valueOf(s.charAt(i)));

           if (j == 0) {
               temp = temp.left;
               if (temp.left == null && temp.right == null) {
                   stringBuilder.append(temp.data);
                   temp = root;
               }
           }
           if (j == 1) {
               temp = temp.right;
               if (temp.left == null && temp.right == null) {
                   stringBuilder.append(temp.data);
                   temp = root;
               }
           }
       }

       System.out.println("Decoded string is : " + stringBuilder.toString());

   }
}

please give me thumb up


Related Solutions

Read through "The Huffman Code" on page 415 of the book. Write a program to implement...
Read through "The Huffman Code" on page 415 of the book. Write a program to implement Huffman coding and decoding. It should do the following: Accept a text message, possibly of more than one line. Create a Huffman tree for this message. Create a code table. Encode the message into binary. Decode the message from binary back to text.
Read through "The Huffman Code" on page 415 of the book. Write a program to implement...
Read through "The Huffman Code" on page 415 of the book. Write a program to implement Huffman coding and decoding. It should do the following: Accept a text message, possibly of more than one line. Create a Huffman tree for this message. Create a code table. Encode the message into binary. Decode the message from binary back to text. in java please
Write Algoritm , code and output. In Operating Systems , . Implement a program for page...
Write Algoritm , code and output. In Operating Systems , . Implement a program for page replacement using the following a.FIFO b.LRU c.OPTIMAL
Write a C++ program using produces Huffman code for a string of text entered by the...
Write a C++ program using produces Huffman code for a string of text entered by the user. Must accept all ASCII characters.
Write a C++ program using produces Huffman code for a string of text entered by the...
Write a C++ program using produces Huffman code for a string of text entered by the user. The string given by the user can be either 1 word or 1000 words. Must accept all ASCII characters. Please do not copy from the internet. This is my 3rd time posting the same question and I have not received a correct answer.
Write a c or matlab text code(to be copied ) for Huffman coder and Huffman decoder...
Write a c or matlab text code(to be copied ) for Huffman coder and Huffman decoder that asks the user to enter the string and output the Huffman code for every letter and a code for encoding that will have every letter and its Huffman code and output all the possibilities for the real string. you must show a screen of an input and the output for both the encoder and the decoder
Create a JAVA code program: Huffman code will be converted to its text equivalent Output an...
Create a JAVA code program: Huffman code will be converted to its text equivalent Output an error message if the input cannot be converted I can give an thumbs up! :)
Write the code in C++. Write a program to implement Employee Directory. The main purpose of...
Write the code in C++. Write a program to implement Employee Directory. The main purpose of the class is to get the data, store it into a file, perform some operations and display data. For the purpose mentioned above, you should write a template class Directory for storing the data empID(template), empFirstName(string), empLastName(string), empContactNumber(string) and empAddress(string) of each Employee in a file EmployeeDirectory.txt. 1. Write a function Add to write the above mentioned contact details of the employee into EmployeeDirectory.txt....
write code in java and comment. thanks. the program is about interface . Implement the basics...
write code in java and comment. thanks. the program is about interface . Implement the basics of Fitness and types of Fitness: Aerobic. Implement specific Fitness types such as Swimming, Cycling, Fitness Task: public interface Fitness (10pts) This will be used as a starting point for deriving any specific Fitness type. Every fitness exercise type has one or more muscle group it affects. Therefor a Fitness has the following abstarct method (Note that all methods in an interface are abstract...
Write Algoritm , code and output. In Operating Systems , 26. Implement a program to allocate...
Write Algoritm , code and output. In Operating Systems , 26. Implement a program to allocate memory by applying the following strategies.a .FIRST FIT b.BEST FIT c.WORST FIT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT