java - 线程主异常->霍夫曼树解码
问题描述
我是一个试图解码霍夫曼树中的文本的初学者。我想我快到了,但是当我运行代码时,线程“main”中出现异常。它说第 97 行,在那里我抛出了一个期望 if (root == null),但我不知道 root 怎么可以为空。谁能帮我理解为什么以及如何解决这个问题?
预期的输出如下所示:
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 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);
}
}
解决方案
在这一行,您创建一个没有左右的节点。所以 left 和 right 都是空的。
leaf_nodes[ascii_code] = new Node(ascii_code);
在这里,您将这个具有 null leftright 的节点添加到堆中。
heap.Insert(leaf_nodes[i]);
在这里您将 root 设置为具有 null leftright 的节点
root.left = left;
所以现在root.left
包含一个没有左或右的节点。
在这里,您将 root 设置为 null:
root = root.left;
这就是为什么 root 为空
推荐阅读
- mysql - MySql 查询从两个表中获取结果
- vba - 如何从 Excel VBA 获取总体规划中的 MSP 子项目状态日期
- oracle - ODP.NET 能否通过实体框架工具支持 LDAP?
- selenium - 如何将 LeanFT Selenium 与 HP QC 集成
- firebase - Cloud Firestore 规则时间戳
- javascript - 使用 chai-http 使用 mocha-chai 进行测试期间的 UnhandledPromiseRejectionWarning
- java - 不使用 final 关键字我们可以避免继承吗?
- reactjs - 有什么方法可以知道子组件是否已安装在 React 中
- active-directory - 通过域外的 SAM 帐户名获取 UPN?
- c++ - 如何在 C++ 程序中运行带有参数的 VBS 脚本?