Reconstuct哈夫曼树的解码 [英] Reconstuct Huffman Tree for Decoding
问题描述
我有编码的使用霍夫曼的COM pression COM pressed字符串数据 即钱多需要
编码
\ñ0110
1011
D 100
Ë11
米001
ñ000
Ø010
- [R 0111
Ÿ1010
**
001010011111101100101000011101010110001111100111000110
我要重建霍夫曼树在Java中去$ C C编码$。任何实现或示例为这样的解码。
我想和codeD的完美解决方案。
公共类HuffmanTree {
公共节点根;
公共HuffmanTree（）{
this.root =新节点（）;
}
公共无效添加（char数据，串序列）{
节点温度= this.root;
INT I = 0;
对于（i = 0; I＆LT; sequence.length（） - 1;我++）{
如果（sequence.charAt（ⅰ）=='0'）{
如果（temp.left == NULL）{
temp.left =新节点（）;
TEMP = temp.left;
}
其他{
临时=（节点）temp.left;
}
}
其他
如果（sequence.charAt（ⅰ）=='1'）{
如果（temp.right == NULL）{
temp.right =新节点（）;
TEMP = temp.right;
}
其他{
临时=（节点）temp.right;
}
}}
如果（sequence.charAt（ⅰ）=='0'）{
temp.left =新节点（数据）;
}
其他{
temp.right =新节点（数据）;
}
}
公共字符串getDe codedMessage（字符串编码）{
字符串输出=;
节点温度= this.root;
的for（int i = 0; I＆LT; encoding.length（）;我++）{
如果（encoding.charAt（ⅰ）=='0'）{
TEMP = temp.left;
如果（temp.left == NULL和放大器;＆安培; temp.right == NULL）{
输出+ = temp.getData（）;
TEMP = this.root;
}
}
其他
{
TEMP = temp.right;
如果（temp.left == NULL和放大器;＆安培; temp.right == NULL）{
输出+ = temp.getData（）;
TEMP = this.root;
}
}
}
返回输出;
}
//遍历重建哈夫曼树进行调试。
公共无效遍历（节点node）{
如果（节点== NULL）
返回;
的System.out.println（节点）;
遍历（node.left）;
遍历（node.right）;
}
}
类节点{
节点左侧;
节点权利;
CHAR数据;
公共节点（）{
}
公共节点（char数据）{
this.data =数据;
}
公共无效使用setData（char数据）{
this.data =数据;
}
公共字符的getData（）{
返回this.data;
}
@覆盖
公共字符串的toString（）{
如果（this.data == Character.UNASSIGNED）{
返回没有价值;
}
其他
返回+ this.data;
}
}
如果你在一个文本连接codeD消息文件的空格字符可能引起的任何问题，所以我写了code为一也。
进口的java.io.File;
进口java.io.FileNotFoundException;
进口java.io.FileWriter;
进口java.io.IOException异常;
进口java.util.Scanner中;
进口java.util.logging.Level中;
进口java.util.logging.Logger中;
公共类测试{
公共静态无效的主要（字串[]的BSC）{
HuffmanTree树=新HuffmanTree（）;
字符串INPUTFILE;
字符串OUTPUTFILE;
扫描仪KB =新的扫描仪（System.in）;
的System.out.println（请输入的输入文件名）;
INPUTFILE = kb.nextLine（）;
文件F =新的文件（INPUTFILE）;
扫描仪FR = NULL;
尝试 {
FR =新的扫描仪（新File（INPUTFILE））;
fr.nextLine（）;
tree.add（'\ N'，fr.nextLine（）修剪（））;
字符串临时= fr.nextLine（）;
如果（temp.charAt（0）==''＆安培;＆安培; temp.charAt（1）==''）
{
tree.add（''，temp.trim（））;
}
其他
tree.add（temp.charAt（0），temp.substring（1））;
而（fr.hasNext（））{
临时= fr.nextLine（）;
如果（temp.equals（**））{
打破;
}
其他
tree.add（temp.charAt（0），temp.substring（1））;
}
FileWriter的F0 =新的FileWriter（新文件（德coded.ou））;
f0.write（tree.getDe codedMessage（fr.nextLine（）））;
f0.close（）;
}赶上（例外前）{
的System.out.println（ex.getMessage（））;
}
}
}
首先，你不需要重建霍夫曼树。你可以简单地线性搜索为code，下位集相匹配。既然是preFIX code，有一个独特的解决方案。所以，第一场比赛是正确的比赛。
如果你想一棵树，只是开始的第一位，让你两个选择。 0左，右1。这些都不是一个code，所以在第二位的两个分支，同样的事情。其中的四个端部有在code 11的电子商务。现在分支上的第三个比特的剩下的三个。四六个到底有没有用code的。科剩下的两个。这四个在code全部结束，你就大功告成了。现在，您可以用树状脱code，看着一位在同一时间，直到你得到一个code。发出code，并开始回到了树的下位的根。
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.
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());
}
}
}
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.
这篇关于Reconstuct哈夫曼树的解码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
