Write a command line program that computes the frequencies of characters in a te

Question

Write a command line program that computes the frequencies of characters in a text file and internally builds a Huffman tree. Print in a console window the table of characters along with corresponding Huffman codes. The program should then prompt the user to enter a code of 0's and ones. When you press enter the program should decode your input based on the Huffman tree that you constructed from the original input file. If there is an error in the code, print error, rather than the decoded message. Finally, the program should prompt the user for a series of characters. When the user presses enter, those characters should be converted into the corresponding Huffman code based on the Huffman tree built from the original file input.

Explanation / Answer

public final class Huffman {

private Huffman() {};

private static class HuffmanNode {
char ch;
int frequency;
HuffmanNode left;
HuffmanNode right;

HuffmanNode(char ch, int frequency, HuffmanNode left, HuffmanNode right) {
this.ch = ch;
this.frequency = frequency;
this.left = left;
this.right = right;
}
}

private static class HuffManComparator implements Comparator<HuffmanNode> {
@Override
public int compare(HuffmanNode node1, HuffmanNode node2) {
return node1.frequency - node2.frequency;
}
}

  
Compresses the string using huffman algorithm.
The huffman tree and the huffman code are serialized to disk
  

public static void compress(String sentence) throws FileNotFoundException, IOException {
if (sentence == null) {
throw new NullPointerException("Input sentence cannot be null.");
}
if (sentence.length() == 0) {
throw new IllegalArgumentException("The string should atleast have 1 character.");
}

final Map<Character, Integer> charFreq = getCharFrequency(sentence);
final HuffmanNode root = buildTree(charFreq);
final Map<Character, String> charCode = generateCodes(charFreq.keySet(), root);
final String encodedMessage = encodeMessage(charCode, sentence);
serializeTree(root);
serializeMessage(encodedMessage);
}

private static Map<Character, Integer> getCharFrequency(String sentence) {
final Map<Character, Integer> map = new HashMap<Character, Integer>();

for (int i = 0; i < sentence.length(); i++) {
char ch = sentence.charAt(i);
if (!map.containsKey(ch)) {
map.put(ch, 1);
} else {
int val = map.get(ch);
map.put(ch, ++val);
}
}

return map;
}
private static HuffmanNode buildTree(Map<Character, Integer> map) {
final Queue<HuffmanNode> nodeQueue = createNodeQueue(map);

while (nodeQueue.size() > 1) {
final HuffmanNode node1 = nodeQueue.remove();
final HuffmanNode node2 = nodeQueue.remove();
HuffmanNode node = new HuffmanNode('', node1.frequency + node2.frequency, node1, node2);
nodeQueue.add(node);
}
return nodeQueue.remove();
}

private static Queue<HuffmanNode> createNodeQueue(Map<Character, Integer> map) {
final Queue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>(11, new HuffManComparator());
for (Entry<Character, Integer> entry : map.entrySet()) {
pq.add(new HuffmanNode(entry.getKey(), entry.getValue(), null, null));
}
return pq;
}

private static Map<Character, String> generateCodes(Set<Character> chars, HuffmanNode node) {
final Map<Character, String> map = new HashMap<Character, String>();
doGenerateCode(node, map, "");
return map;
}

private static void doGenerateCode(HuffmanNode node, Map<Character, String> map, String s) {
if (node.left == null && node.right == null) {
map.put(node.ch, s);
return;
}
doGenerateCode(node.left, map, s + '0');
doGenerateCode(node.right, map, s + '1' );
}

private static String encodeMessage(Map<Character, String> charCode, String sentence) {
final StringBuilder stringBuilder = new StringBuilder();

for (int i = 0; i < sentence.length(); i++) {
stringBuilder.append(charCode.get(sentence.charAt(i)));
}
return stringBuilder.toString();
}

private static void serializeTree(HuffmanNode node) throws FileNotFoundException, IOException {
final BitSet bitSet = new BitSet();
try (ObjectOutputStream oosTree = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"))) {
try (ObjectOutputStream oosChar = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {
IntObject o = new IntObject();
preOrder(node, oosChar, bitSet, o);
bitSet.set(o.bitPosition, true); // padded to mark end of bit set relevant for deserialization.
oosTree.writeObject(bitSet);
}
}
}

private static class IntObject {
int bitPosition;
}

*   
* Diagram and how an bit set would look as a result.
* (source node)
* /
* true true
* /
* (leaf node) (leaf node)
* | |
* false false
* | |
*
* So now a bit set looks like [false, true, false, true]
*
*/
private static void preOrder(HuffmanNode node, ObjectOutputStream oosChar, BitSet bitSet, IntObject intObject) throws IOException {
if (node.left == null && node.right == null) {
bitSet.set(intObject.bitPosition++, false); // register branch in bitset
oosChar.writeChar(node.ch);
return; // DONT take the branch.
}
bitSet.set(intObject.bitPosition++, true); // register branch in bitset
preOrder(node.left, oosChar, bitSet, intObject); // take the branch.

bitSet.set(intObject.bitPosition++, true); // register branch in bitset
preOrder(node.right, oosChar, bitSet, intObject); // take the branch.
}

private static void serializeMessage(String message) throws IOException {
final BitSet bitSet = getBitSet(message);

try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/encodedMessage"))){

oos.writeObject(bitSet);
}
}

private static BitSet getBitSet(String message) {
final BitSet bitSet = new BitSet();
int i = 0;
for (i = 0; i < message.length(); i++) {
if (message.charAt(i) == '0') {
bitSet.set(i, false);
} else {
bitSet.set(i, true);
}
}
bitSet.set(i, true); // dummy bit set to know the length
return bitSet;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.