主线程异常 --> 霍夫曼树解码

Question

我是一个尝试解码霍夫曼树中的文本的初学者。我想我快到了，但是当我运行代码时，我在线程 "main" 中遇到异常。它说第 97 行，我在那里抛出一个 expectation if (root == null)，但我不明白 root 怎么可能是 null。谁能帮我理解为什么以及如何解决这个问题？

预期输出如下所示：

java Test “Huffman tree test”
Encoded text: 010001111001001101111010110010111101010000101111000110111
Compression ratio: 41%
Decoded text: Huffman tree test

我得到的输出是：

java Test “Huffman tree test”
Encoded text: 010011010010111001101101101110011110100000100111001011111
Compression ratio: 335.0
Exception in thread "main" java.lang.RuntimeException: Invalid input.
        at Tree.Decode(Tree.java:97)
        at Test.main(Test.java:24)

这是我的代码，包括树 class 和测试 class:

class Tree
{
    Node root;
    Node leaf_nodes[];

    public void CreateLeafNodes(String ascii_text)
    {
        // Array of leaf nodes indexed by ASCII code
        leaf_nodes = new Node[256];

        // Parse text
        for (int i = 0; i< ascii_text.length();i++)
        {
            // Get ASCII code for current character
            int ascii_code = ascii_text.charAt(i);

            // Create node if it does not exist
            if (leaf_nodes[ascii_code] == null)
                leaf_nodes[ascii_code] = new Node(ascii_code);

            // Increment frequncy
            leaf_nodes[ascii_code].frequency++;
        }
    }

    public void BuildTree()
    {
        // Create heap
        Heap heap = new Heap();

        // Insert all leaf nodes
        for (int i = 0; i < 256; i++)
            if (leaf_nodes[i] != null)
                heap.Insert(leaf_nodes[i]);

        // Build tree
        while(heap.GetLength() > 1)
        {
            // Extract 2 nodes with minimum frequency
            Node left = (Node) heap.ExtractMax();
            Node right = (Node) heap.ExtractMax();

            // Create new node and make it the root for now
            root = new Node(0);
            root.left = left;
            root.right = right;
            root.frequency = left.frequency + right.frequency;

            // Insert new node in heap
            heap.Insert(root);
        }

        // Set Huffman codes
        root.SetHuffmanCode("");
    }

    public String Encode(String ascii_text)
    {
        // Initialize result
        String huffman_text = "";

        // Traverse ASCII text
        for (int i = 0; i < ascii_text.length(); i++)
        {
            // Get ASCII code
            int ascii_code = ascii_text.charAt(i);

            // Check if character is supported
            if (leaf_nodes[ascii_code] == null)
                throw new RuntimeException("Character not supported: " + 
                        ascii_text.charAt(i));

            // Get Huffman code
            String huffman_code = leaf_nodes[ascii_code].huffman_code;

            // Add it
            huffman_text += huffman_code;

            // Message
            System.out.println(ascii_text.charAt(i) + " -> " + huffman_code);
        }

        // Result
        return huffman_text;
    }

    public String Decode(String huffman_text)
    {
        // Initialize result
        String ascii_text = "";

        // Traverse huffman text
        for (int i = 0; i < huffman_text.length(); i++)
        {
            if(root == null)
            {
                throw new RuntimeException("Invalid input.");
            }

            if (huffman_text.charAt(i) == '0')
                root = root.left;

            else if (huffman_text.charAt(i) == '1')
                root = root.right;

            ascii_text += huffman_text.charAt(i); 
        }

        // Result
        return ascii_text;
    }
}

class Test
{
    public static void main(String args[])
    {
        float compression;

        Tree tree = new Tree();

        if (args.length == 0)
            throw new RuntimeException("Please enter an argument. ");

        String ascii_text = args[0];
        tree.CreateLeafNodes(ascii_text);
        tree.BuildTree();

        System.out.println(ascii_text);

        String huffman_text = tree.Encode(ascii_text);
        System.out.println("Encoded text: " + huffman_text);

        compression = huffman_text.length() * 100/ascii_text.length();
        System.out.println("Compression ratio: " + compression);    

        String ascii_text_2 = tree.Decode(huffman_text);
        System.out.println("Decoded text: " + ascii_text_2);

    }
}

Answer 1

在这行你创建了一个没有左右的节点。所以 left 和 right 都是空的。

leaf_nodes[ascii_code] = new Node(ascii_code);

这里你把这个leftright为null的节点添加到堆中。

heap.Insert(leaf_nodes[i]);

这里你设置root为leftright为null的节点

root.left = left;

所以现在 root.left 包含一个没有左或右的节点。

这里你设置root为空：

root = root.left;

这就是 root 为空的原因

主线程异常 --> 霍夫曼树解码

Exception in thread main --> huffman tree decoding

java

ascii

decode

huffman-code

data-structures