JAVA
Write an application to test the HuffmanTree class. Your application will need to read a text file and build a frequency table for the characters occurring in that file. Once that table is built create a Huffman code tree and then a string consisting of 0 and 1 characters that represents the code string for that file. Read that string back in and re-create the contents of the original file. Prompt the user for file name. Read the file, get the frequencies, create the huffman tree. Print the code for each character. Create the encoding for the file. Decode the file. Write the decoded file to another text file.
To get the ascii code of a character: char somechar;
//here you get somechar....reading from file...int i = Integer.parseInt(somechar);
public class Huffman { // alphabet size of extended ASCII private static final int R = 256; // Do not instantiate. private Huffman() { } // Huffman trie node private static class Node implements Comparable
{ private final char ch; private final int freq; private final Node left, right; Node(char ch, int freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } // is the node a leaf node? private boolean isLeaf() { assert ((left == null) && (right == null)) || ((left != null) && (right != null)); return (left == null) && (right == null); } // compare, based on frequency public int compareTo(Node that) { return this.freq - that.freq; } } /** * Reads a sequence of 8-bit bytes from standard input; compresses them * using Huffman codes with an 8-bit alphabet; and writes the results * to standard output. */ public static void compress() { // read the input String s = BinaryStdIn.readString(); char[] input = s.toCharArray(); // tabulate frequency counts int[] freq = new int[R]; for (int i = 0; i < input.length; i++) freq[input[i]]++; // build Huffman trie Node root = buildTrie(freq); // build code table String[] st = new String[R]; buildCode(st, root, \"\"); // print trie for decoder writeTrie(root); // print number of bytes in original uncompressed message BinaryStdOut.write(input.length); // use Huffman code to encode input for (int i = 0; i < input.length; i++) { String code = st[input[i]]; for (int j = 0; j < code.length(); j++) { if (code.charAt(j) == \'0\') { BinaryStdOut.write(false); } else if (code.charAt(j) == \'1\') { BinaryStdOut.write(true); } else throw new IllegalStateException(\"Illegal state\"); } } // close output stream BinaryStdOut.close(); } // build the Huffman trie given frequencies private static Node buildTrie(int[] freq) { // initialze priority queue with singleton trees MinPQ pq = new MinPQ(); for (char i = 0; i < R; i++) if (freq[i] > 0) pq.insert(new Node(i, freq[i], null, null)); // special case in case there is only one character with a nonzero frequency if (pq.size() == 1) { if (freq[\'\\0\'] == 0) pq.insert(new Node(\'\\0\', 0, null, null)); else pq.insert(new Node(\'\\1\', 0, null, null)); } // merge two smallest trees while (pq.size() > 1) { Node left = pq.delMin(); Node right = pq.delMin(); Node parent = new Node(\'\\0\', left.freq + right.freq, left, right); pq.insert(parent); } return pq.delMin(); } // write bitstring-encoded trie to standard output private static void writeTrie(Node x) { if (x.isLeaf()) { BinaryStdOut.write(true); BinaryStdOut.write(x.ch, 8); return; } BinaryStdOut.write(false); writeTrie(x.left); writeTrie(x.right); } // make a lookup table from symbols and their encodings private static void buildCode(String[] st, Node x, String s) { if (!x.isLeaf()) { buildCode(st, x.left, s + \'0\'); buildCode(st, x.right, s + \'1\'); } else { st[x.ch] = s; } } /** * Reads a sequence of bits that represents a Huffman-compressed message from * standard input; expands them; and writes the results to standard output. */ public static void expand() { // read in Huffman trie from input stream Node root = readTrie(); // number of bytes to write int length = BinaryStdIn.readInt(); // decode using the Huffman trie for (int i = 0; i < length; i++) { Node x = root; while (!x.isLeaf()) { boolean bit = BinaryStdIn.readBoolean(); if (bit) x = x.right; else x = x.left; } BinaryStdOut.write(x.ch, 8); } BinaryStdOut.close(); } private static Node readTrie() { boolean isLeaf = BinaryStdIn.readBoolean(); if (isLeaf) { return new Node(BinaryStdIn.readChar(), -1, null, null); } else { return new Node(\'\\0\', -1, readTrie(), readTrie()); } } /** * Sample client that calls {@code compress()} if the command-line * argument is \"-\" an {@code expand()} if it is \"+\". * * @param args the command-line arguments */ public static void main(String[] args) { if (args[0].equals(\"-\")) compress(); else if (args[0].equals(\"+\")) expand(); else throw new IllegalArgumentException(\"Illegal command line argument\"); } }
Homework Sourse
