java 重构霍夫曼树进行解码
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11585944/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Reconstuct Huffman Tree for Decoding
提问by wali
I have encodings for compressed string data using Huffman Compression i.e "more money needed"
我有使用霍夫曼压缩的压缩字符串数据的编码，即“需要更多的钱”
Encoding
编码
\n 0110
1011
d 100
e 11
m 001
n 000
o 010
r 0111
y 1010
**
001010011111101100101000011101010110001111100111000110
I want to reconstruct the Huffman Tree in java to decode the encoding. Any implementation or example for such decoding.
我想在java中重建霍夫曼树来解码编码。此类解码的任何实现或示例。
I tried and coded the perfect solution.
我尝试并编写了完美的解决方案。
public class HuffmanTree {
public Node root;
public HuffmanTree(){
this.root = new Node();
}
public void add(char data, String sequence){
Node temp = this.root;
int i = 0;
for(i=0;i<sequence.length()-1;i++){
if(sequence.charAt(i)=='0'){
if(temp.left == null){
temp.left = new Node();
temp = temp.left;
}
else{
temp = (Node) temp.left;
}
}
else
if(sequence.charAt(i)=='1'){
if(temp.right == null){
temp.right = new Node();
temp = temp.right;
}
else{
temp = (Node) temp.right;
}
}}
if(sequence.charAt(i)=='0'){
temp.left = new Node(data);
}
else{
temp.right = new Node(data);
}
}
public String getDecodedMessage(String encoding){
String output = "";
Node temp = this.root;
for(int i = 0;i<encoding.length();i++){
if(encoding.charAt(i) == '0'){
temp = temp.left;
if(temp.left == null && temp.right == null){
output+= temp.getData();
temp = this.root;
}
}
else
{
temp = temp.right;
if(temp.left == null && temp.right == null){
output+= temp.getData();
temp = this.root;
}
}
}
return output;
}
// Traversal of reconstructed huffman tree for debugging.
public void traversal(Node node){
if(node == null)
return;
System.out.println(node);
traversal(node.left);
traversal(node.right);
}
}
class Node{
Node left;
Node right;
char data;
public Node(){
}
public Node(char data){
this.data = data;
}
public void setData(char data){
this.data = data;
}
public char getData(){
return this.data;
}
@Override
public String toString(){
if(this.data == Character.UNASSIGNED){
return "No Value";
}
else
return ""+this.data;
}
}
If you have the encoded message in a text file the space character may cause any issue so I have written code for that one also.
如果您在文本文件中有编码消息，则空格字符可能会导致任何问题，因此我也为该问题编写了代码。
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;
public class Test {
public static void main(String[] bscs){
HuffmanTree tree = new HuffmanTree();
String inputFile;
String outputFile;
Scanner kb = new Scanner(System.in);
System.out.println("Please enter the name of the Input File");
inputFile = kb.nextLine();
File f = new File(inputFile);
Scanner fr = null;
try {
fr = new Scanner(new File(inputFile));
fr.nextLine();
tree.add('\n', fr.nextLine().trim());
String temp = fr.nextLine();
if(temp.charAt(0)==' ' && temp.charAt(1)==' ')
{
tree.add(' ', temp.trim());
}
else
tree.add(temp.charAt(0), temp.substring(1));
while(fr.hasNext()){
temp = fr.nextLine();
if(temp.equals("**")){
break;
}
else
tree.add(temp.charAt(0), temp.substring(1));
}
FileWriter f0 = new FileWriter(new File("decoded.ou"));
f0.write(tree.getDecodedMessage(fr.nextLine()));
f0.close();
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
}
}
回答by Mark Adler
First off, you don't need to reconstruct the Huffman tree. You can simply search linearly for the code that matches the next set of bits. Since it is a prefix code, there is a unique solution. So the first match is the right match.
首先，您不需要重建霍夫曼树。您可以简单地线性搜索与下一组位匹配的代码。既然是前缀码，就有了唯一的解法。所以第一场比赛是正确的比赛。
If you want to make a tree, simply start with the first bit which gives you two choices. 0 left, 1 right. Neither of those is a code, so both branch on the second bit, same thing. One of the four ends there at the code 11 for e. Now branch the remaining three on the third bit. Four of the six end there with a code. Branch the remaining two. Those four all end in a code and you're done. Now you can use the tree to decode, looking at one bit at a time until you get to a code. Emit the code, and start back at the root of the tree for the next bit.
如果你想制作一棵树，只需从第一个开始，它会给你两个选择。0 左，1 右。这些都不是代码，所以都在第二位分支，同样的事情。四个中的一个在 e 的代码 11 处结束。现在在第三位上分支剩余的三个。六个中的四个以代码结束。分支剩下的两个。这四个都以代码结尾，你就完成了。现在您可以使用树进行解码，一次查看一位，直到获得代码。发出代码，然后从树的根开始返回下一位。
