Question

在线等 哈弗曼编码实现字符串的压缩 用C++或者JAVA都可以

写一个哈弗曼编码实现压缩的代码，比如手工输入了字符串；然后通过程序实现编码，最终在屏幕上要显示字符串的编码 以及平均码长；
越简单越好，尽量每一行都有注释 ，如果可以的话再写一下代码核心部分的大概思路。拜托各位大神啦。

Answer 1

这是网上开源的huffman字串压缩和解压缩的例子：

import java.util.*;
import java.io.*;
 
public class Huffman {  // Written by: Yancy Vance Paredes, October 17, 2013
 
    public static PriorityQueue<Node> q;
    public static HashMap<Character, String> charToCode;
    public static HashMap<String, Character> codeToChar;
 
    public static void main(String[] args) throws FileNotFoundException {
        // Read all the contents of the file
        String text = new Scanner(new File("input.txt")).useDelimiter("\\A").next(); // nextLine(); // change it if you only want to read a single line without the new line character.
 
        // Count the frequency of all the characters
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
 
        for(int i = 0; i < text.length(); i++) {
            char a = text.charAt(i);
 
            if(dict.containsKey(a))
                dict.put(a, dict.get(a)+1);
            else
                dict.put(a, 1);
        }
 
        // Create a forest (group of trees) by adding all the nodes to a priority queue
        q = new PriorityQueue<Node>(100, new FrequencyComparator());
        int n = 0;
 
        for(Character c : dict.keySet()) {
            q.add(new Node(c, dict.get(c)));
            n++;
        }
 
        // Identify the root of the tree
        Node root = huffman(n);
 
        // Build the table for the variable length codes
        buildTable(root);
 
        String compressed = compress(text);
        System.out.println("The compressed used a total of " + compressed.length() + " bits");
        System.out.println(compressed);
 
        String decompressed = decompress(compressed);
        System.out.println("The original text used a total of " + decompressed.length() + " characters");
        System.out.println(decompressed);
 
        //saveToFile(compressed);
    }
 
    // This method builds the tree based on the frequency of every characters
    public static Node huffman(int n) {
        Node x, y;
 
        for(int i = 1; i <= n-1; i++) {
            Node z = new Node();
            z.left = x = q.poll();
            z.right = y = q.poll();
            z.freq = x.freq + y.freq;
            q.add(z);
        }
 
        return q.poll();
    }
 
    // This method builds the table for the compression and decompression
    public static void buildTable(Node root) {
        charToCode = new HashMap<Character, String>();
        codeToChar = new HashMap<String, Character>();
 
        postorder(root, new String());
    }
 
    // This method is used to traverse from ROOT-to-LEAVES
    public static void postorder(Node n, String s) {
        if(n == null)
            return;
 
        postorder(n.left, s+"0");
        postorder(n.right, s+"1");
 
        // Visit only nodes with keys
        if(n.alpha != '&#092;&#048;') {
            System.out.println("\'" + n.alpha + "\' -> " + s);
            charToCode.put(n.alpha, s);
            codeToChar.put(s, n.alpha);
        }
    }
 
    // This method assumes that the tree and dictionary are already built
    public static String compress(String s) {
        String c = new String();
 
        for(int i = 0; i < s.length(); i++)
            c = c + charToCode.get(s.charAt(i));
 
        return c;
    }
 
    // This method assumes that the tree and dictionary are already built
    public static String decompress(String s) {
        String temp = new String();
        String result = new String();
 
        for(int i = 0; i < s.length(); i++) {
            temp = temp + s.charAt(i);
 
            if(codeToChar.containsKey(temp)) {
                result = result + codeToChar.get(temp);
                temp = new String();
            }
        }
 
        return result;
    }
 
    public static void saveToFile(String l) throws FileNotFoundException {
        PrintWriter oFile = new PrintWriter("output.txt");
 
        for(String s : codeToChar.keySet())
            oFile.println(s + "->" + codeToChar.get(s));
 
        oFile.println(l);
 
        oFile.close();
    }
 
}
 
class Node {
 
    public char alpha;
    public int freq;
    public Node left, right;
 
    public Node(char a, int f) {
        alpha = a;
        freq = f;
    }
 
    public Node() {
 
    }
 
    public String toString() {
        return alpha + " " + freq;
    }
 
}
 
class FrequencyComparator implements Comparator<Node> {
 
    public int compare(Node a, Node b) {
        int freqA = a.freq;
        int freqB = b.freq;
 
        return freqA-freqB;
    }
 
}

追问

拜托啦~ 可以给我中文的注释吗？按照我前面写到的，帮忙改一下。拜托了

追答

11: text就是你要压缩的字符串。这里字符串从文件读，你可以从参数传过来或者从其他变量赋过来
15-24： 用一个hashmap统计字符串里面的字符频度
27-33： 用Java自带的priority queue把字符频度排序
39： 对每个字符按频度生成哈夫曼编码路径
后面就简单了
41: 压缩字串。其实就是把每个字符换成哈夫曼编码。
后面都是输出一些信息，你直接把程序拷过去，把11行的text赋成你要压缩的字串就可以运行了。