ハフマンコード説明Java

-1

私はJavaで新しく、コードをオンラインで使用してハフマンコーディングを理解しようとしています。私はどのようにハフマンコードを実装するかについて何も見いだせなかったため、コードがうまく動作しているかどうかを理解するためのコードを使いこなしています。私はなぜこのコードで男がハフマンツリークラスと文字列バッファーに匹敵するのかを理解する必要があります。誰かがハフマンコーディングに関するオンラインまたはアルゴリズムの説明をよく知っている場合は、私は本当にこのコードを理解する必要があります。 PS：英語は母国語ではありません。はハフマンコード説明Java

import java.util.*; 

public class HuffmanCode { 
    // input is an array of frequencies, indexed by character code 
    public HuffmanTree buildTree(int[] charFreqs) { 
     PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>(); 
     // initially, we have a forest of leaves 
     // one for each non-empty character 
     for (int i = 0; i < charFreqs.length; i++) 
      if (charFreqs[i] > 0) 
       trees.offer(new HuffmanLeaf(charFreqs[i], (char)i)); 

     assert trees.size() > 0; 
     // loop until there is only one tree left 
     while (trees.size() > 1) { 
      // two trees with least frequency 
      HuffmanTree a = trees.poll(); 
      HuffmanTree b = trees.poll(); 

      // put into new node and re-insert into queue 
      trees.offer(new HuffmanNode(a, b)); 
     } 
     return trees.poll(); 
    } 

    public void printCodes(HuffmanTree tree, StringBuffer prefix) { 
     assert tree != null; 
     if (tree instanceof HuffmanLeaf) { 
      HuffmanLeaf leaf = (HuffmanLeaf)tree; 

      // print out character, frequency, and code for this leaf (which is just the prefix) 
      System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix); 

     } else if (tree instanceof HuffmanNode) { 
      HuffmanNode node = (HuffmanNode)tree; 

      // traverse left 
      prefix.append('0'); 
      //prefix = prefix + "0"; 
      printCodes(node.left, prefix); 
      prefix.deleteCharAt(prefix.length()-1); 

      // traverse right 
      prefix.append('1'); 
      printCodes(node.right, prefix); 
      prefix.deleteCharAt(prefix.length()-1); 
     } 
    } 
}

ハフマン木クラスをありがとう：

public class HuffmanTree implements Comparable<HuffmanTree> { 
    public final int frequency; // the frequency of this tree 

    public HuffmanTree(int freq) { 
     frequency = freq; 
    } 

    // compares on the frequency 
    public int compareTo(HuffmanTree tree) { 
     return frequency - tree.frequency; 
    } 
}

ハフマン葉：

class HuffmanLeaf extends HuffmanTree { 

    public final char value; // the character this leaf represents 

    public HuffmanLeaf(int freq, char val) { 
     super(freq); 
     value = val; 
    } 
}

ハフマンノード：

class HuffmanNode extends HuffmanTree { 

    public final HuffmanTree left, right; // subtrees 

    public HuffmanNode(HuffmanTree l, HuffmanTree r) { 
     //Calling the super constructor HuffmanTree 
     super(l.frequency + r.frequency); 
     left = l; 
     right = r; 
    } 

}

メイン：

public class Main { 

    public static void main(String[] args) { 
     String test = "Hello World"; 
     HuffmanCode newCode = new HuffmanCode(); 

     // we will assume that all our characters will have 
     // code less than 256, for simplicity 
     int[] charFreqs = new int[256]; 
     // read each character and record the frequencies 
     for (char c : test.toCharArray()) 
      charFreqs[c]++; 

     // build tree 
     ////HuffmanTree tree = buildTree(charFreqs); 
     HuffmanTree tree = newCode.buildTree(charFreqs); 

     // print out results 
     System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE"); 
     newCode.printCodes(tree, new StringBuffer()); 
    } 

}

出典

2016-12-03 Knight Ramsamy

コードにprintステートメントを追加するか、デバッガを使用して、理解してくれるまで行単位で実行してください。 –

誰かがなぜStringbufferを使用して、それに匹敵するのか説明できますか？ –

あなたが見つけたいくつかのランダムなコードを理解するために、コミュニティの取り組みとしてStackoverflowを使うべきではありません。コードを実行してみてください –