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的四個端點之一。現在將剩餘的三個分支分配給第三位。六個中的四個以代碼結束。分支剩下的兩個。這四個都以代碼結束，你就完成了。現在，您可以使用該樹進行解碼，一次只查看一行，直到找到代碼。發出代碼，並從樹的根部開始回到下一位。