1

スタックオーバーフローを使用して質問するのはこれが初めてです。皆さんが私を助けてくれることを願っています:)

ハフマンコードを実装するためのプロジェクトに取り組んでいます。問題は、コードを印刷しようとすると間違った結果が得られることです。

入力ファイルと正しい結果は次のとおりです。

Symbol    A     B   C   D    _
frequency 0.35 0.1 0.2 0.2 0.15
Code      11   100 00  01  101

私が得た結果：

Symbol    A     B   C   D    _
frequency 0.35 0.1 0.2 0.2 0.15
Code      00   011  10  11  010

クラスファイルは次のとおりです。

import java.util.*;
import java.io.*;
import java.util.PriorityQueue;

public class Node implements Comparable<Node> {
Node left;
        Node right;
    Node parent;
    String text;
    Float frequency;

    public Node(String textIn, Float frequencies) {
        text = textIn;
        frequency = frequencies;
    }

    public Node(Float d) {
        text = "";
        frequency = d;
    }

    public int compareTo(Node n) {
        if (frequency < n.frequency) {
            return -1;
        } else if (frequency > n.frequency) {
            return 1;
        }
        return 0;
    }

    public static void buildPath(Node root,String code)
{
    if (root!=null)
    {   
        if (root.left!=null)
            buildPath(root.left, code+"0");
        if (root.right!=null)   
          buildPath(root.right,code+"1");
        if (root.left==null && root.right==null)
            System.out.println(root.text+": "+code);               
    }       
}



    public static Node makeHuffmanTree(Float[] frequencies, String text[]) {
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        for (int i = 0; i < text.length; i++) {
            Node n = new Node(text[i], frequencies[i]);
            queue.add(n);
        }
        Node root = null;
        while (queue.size() > 1) {
            Node least1 = queue.poll();
            Node least2 = queue.poll();
            Node combined = new Node(least1.frequency + least2.frequency);
            combined.right = least1;
            combined.left = least2;
            least1.parent = combined;
            least2.parent = combined;
            queue.add(combined);
            // Keep track until we actually find the root
            root = combined;
        }
        return root;
    }

私の印刷方法に問題があると思いますか？

これが私のメインです

public static void main(String[] args)
String[] Symbol = {"A","B","C","D","_"};
Float[] frequency = (0.35,0.1,0.2,0.2,0.15};

        Node root = Node.makeHuffmanTree(frequency, Symbol);
        Node.buildPath(root, "");
4

1 に答える 1

1

あなたの出力では、個々のコードの長さがうまく見えるので、ツリートラバーサルの問題であるとは確信が持てません。

不一致は、ツリーの構築方法にある可能性が非常に高いです。キューから 2 つの要素を取り出し、それら 2 つをサブツリーとして新しいツリーを作成すると、どのサブツリーを「左」サブツリーにするかの選択が結果のコードに影響します。

あなたのwhileループを見るとわかります

while (queue.size() > 1) {
        Node least1 = queue.poll();
        Node least2 = queue.poll();
        Node combined = new Node(least1.frequency + least2.frequency);
        combined.right = least1;
        combined.left = least2;
        least1.parent = combined;
        least2.parent = combined;
        queue.add(combined);
        // Keep track until we actually find the root
        root = combined;
}

例を完全に処理したわけではありませんが、あなたの例に取り組んできたので、逆の代わりにcombined.left = least1andに変更するだけで、期待するコードが得られると思います。combined.right = least2

于 2013-08-08T19:14:55.097 に答える