Reconstuct哈夫曼树的解码

Question

我使用霍夫曼压缩 即“需要更多的资金”用于压缩字符串数据编码

编码

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

我想重建霍夫曼树在Java中的编码解码。这种解码的任何实现或例子。

我试过并编码完美的解决方案。

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的四个端点之一。现在将剩余的三个分支分配给第三位。六个中的四个以代码结束。分支剩下的两个。这四个都以代码结束，你就完成了。现在，您可以使用该树进行解码，一次只查看一行，直到找到代码。发出代码，并从树的根部开始回到下一位。