2

我正在编写 Huffman 代码，我在其中导入一个文件，为每个字符生成 Huffman 代码，然后将二进制文件输出到文件中。要导入字符，我使用读取每个字符的扫描仪，将其放入具有读取字符值和频率为 1 的节点中。然后，将该节点添加到 PriorityQueue。由于 Node 类有一个 compareTo 方法，它只比较频率，我怎样才能实现一个比较器到这个特定的 PriorityQueue，在队列中排序时比较字符？提前致谢。

文字示例：字符队列应按如下方式排序：

[A:1][A:1][A:1][B:1][C:1]
Next step:
[A:1][A:2][B:1][C:1]
Final:
[A:3][B:1][C:1]

以下是一些片段：

protected class Node implements Comparable<Node>{
    Character symbol;
    int frequency;

    Node left = null;
    Node right = null;
    @Override
    public int compareTo(Node n) {
        return n.frequency < this.frequency ? 1 : (n.frequency == this.frequency ? 0 : -1);
    }

    public Node(Character c, int f){
        this.symbol = c;
        this.frequency = f;
    }
    public String toString(){
        return "["+this.symbol +","+this.frequency+"]";
    }

这是需要自定义比较器的 PriorityQueue：

public static PriorityQueue<Node> gatherFrequency(String file) throws Exception{
    File f = new File(file);
    Scanner reader = new Scanner(f);
    PriorityQueue<Node> PQ = new PriorityQueue<Node>();
    while(reader.hasNext()){
        for(int i = 0; i < reader.next().length();i++){
            PQ.add(new Node(reader.next().charAt(0),1));
        }
    }
    if(PQ.size()>1){ //during this loop the nodes should be compared by character value
        while(PQ.size() > 1){
            Node a = PQ.remove();
            Node b = PQ.remove();
            if(a.symbol.compareTo(b.symbol)==0){
                Node c = new Node(a.symbol, a.frequency + b.frequency);
                PQ.add(c);
            }
            else break;
        }
        return PQ;
    }
    return PQ;

}

这是我使用 HashMap 创建的新方法：

public static Collection<Entry<Character,Integer>> gatherFrequency(String file) throws Exception{
        File f = new File(file);
        Scanner reader = new Scanner(f);
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        while(reader.hasNext()){
            for(int i = 0; i < reader.next().length();i++){
                Character key = reader.next().charAt(i);
                if(map.containsKey(reader.next().charAt(i))){
                    int freq = map.get(key);
                    map.put(key, freq+1);
                }
                else{
                    map.put(key, 1);
                }
            }
        }
        return map.entrySet();
    }
4

1 回答 1

2

实现霍夫曼树的标准方法是使用哈希图（在 Java 中，您可能会使用 a HashMap<Character, Integer>）来计算每个字母的频率，并将每个字母的一个节点插入优先级队列。因此，在构建 Huffman 树本身时，您从一个已经处于您展示的“最终”状态的优先级队列开始。然后霍夫曼算法重复地从优先队列中提取两个节点，为这两个节点构造一个新的父节点，并将新节点插入优先队列。

于 2011-04-15T15:36:55.677 回答