Answered step by step
Verified Expert Solution
Question
1 Approved Answer
I need help with translating this source code into pseudo code. import java.util.*; class Node { int freq; char character; Node left = null; Node
I need help with translating this source code into pseudo code.
import java.util.*; class Node { int freq; char character; Node left = null; Node right = null; public Node() { } public Node(Character character, Integer freq) { this.freq = freq; this.character = character; } } public class Main { static final int fixed_length = 3; static int average_bits; static int total_bits; // Function that reads the text and count the frequency of every character public static Set> getCharactersFrequency(String text) { Map freq = new HashMap<>(); for (char c : text.toCharArray()) { freq.put(c, freq.getOrDefault(c, 0) + 1); } return freq.entrySet(); } // Recursive function that traverse the tree and generate the codes for each // character public static void huffmanCodes(Node root, String text, Map codes) { if (root == null) { return; } if (root.left == null && root.right == null) { System.out.println(root.character + " : " + text); codes.put(root.character, text); return; } huffmanCodes(root.left, text + "0", codes); huffmanCodes(root.right, text + "1", codes); } // Function that encode the text public static StringBuilder encodeText(Map codes, String text) { StringBuilder result = new StringBuilder(); for (char c : text.toCharArray()) { result.append(codes.get(c)); } return result; } public static int _decode(Node root, int index, StringBuilder encodedText, StringBuilder result) { if (root == null) { return index; } if (root.left == null && root.right == null) { result.append(root.character); return index; } index++; root = (encodedText.charAt(index) == '0') ? root.left : root.right; index = _decode(root, index, encodedText, result); return index; } public static StringBuilder decodeText(Node root, StringBuilder encodedText) { StringBuilder result = new StringBuilder(); int index = -1; while (index < encodedText.length() - 1) { index = _decode(root, index, encodedText, result); } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Please enter an English text: "); String text = sc.nextLine(); Set> freq = getCharactersFrequency(text); int totalCharacters = freq.stream().mapToInt(Map.Entry::getValue).sum(); System.out.println(); for (var entry : freq) { System.out.println("Probabilities of " + entry.getKey() + " = " + String.format("%.3f", ((double) entry.getValue() / totalCharacters))); } System.out.println(); // Priority queue with priority in the lowest frequency PriorityQueue q = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq)); for (var entry : freq) { q.add(new Node(entry.getKey(), entry.getValue())); } Node root = null; if (q.size() == 1) { System.out.println(" The text has only one type of character"); return; } while (q.size() > 1) { Node first = q.peek(); q.poll(); Node second = q.peek(); q.poll(); Node f = new Node(); f.freq = first.freq + second.freq; f.character = '-'; f.left = first; f.right = second; root = f; q.add(f); } // Map that will save the codes Map codes = new HashMap<>(); huffmanCodes(root, "", codes); System.out.println(); // Solving for the compression ratio double avgBitsPerSymbol = 0; int largerSize = 0; for(var entry : freq){ int size = (codes.getOrDefault(entry.getKey(), "0")).length(); if (size >= largerSize) largerSize = size; avgBitsPerSymbol += ((double) entry.getValue() / totalCharacters) * size; } double compressionRatio = ((largerSize - avgBitsPerSymbol) /largerSize) * 100.0; // Printing average bits, fixed length, compression ration System.out.println("Averages bits per character: " + String.format("%.2f", avgBitsPerSymbol) + "%"); System.out.println("Fixed-length encoding: " + String.format("%d", largerSize)); System.out.println("Compression ratio: " + String.format("%.2f", compressionRatio) + "%"); // Printing encoded and decoded texts var encodedText = encodeText(codes, text); System.out.println(" Encoded: " + encodedText); var decodedText = decodeText(root, encodedText); System.out.println(" Decoded: " + decodedText); } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started