重构霍夫曼树进行解码

Question

我使用霍夫曼压缩编码压缩字符串数据,即"需要更多资金"

编码

\n 0110
   1011
d  100
e  11
m  001
n  000
o  010
r  0111
y  1010
**
001010011111101100101000011101010110001111100111000110

我想在java中重建Huffman树来解码编码.用于这种解码的任何实现或示例.

我尝试并编写了完美的解决方案.

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;
    }
}

如果你在文本文件中有编码的消息,空格字符可能会导致任何问题,所以我也编写了该代码.

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());
            }


            }

    }

Answer 1

首先,您不需要重建霍夫曼树.您可以简单地线性搜索与下一组位匹配的代码.由于它是前缀代码,因此有一个独特的解决方案.所以第一场比赛是正确的比赛.

如果你想做一棵树,只需从第一位开始,它会给你两个选择.0左,1右.这些都不是代码,所以两者都分支在第二位,同样的事情.e的代码11中的四个结尾之一.现在将剩下的三个分支到第三位.六个中的四个以代码结束.分支剩下的两个.这四个都以代码结束,你就完成了.现在,您可以使用树进行解码,一次查看一个位,直到找到代码.发出代码,然后从树的根开始返回下一位.