Код Хаффмана Пояснение Java

Question

Я новичок в java, и я пытаюсь понять кодировку Хаффмана, используя код онлайн. Я возился с кодом, чтобы понять, как он работает, потому что я не нашел ничего о том, как реализовать код Хаффмана. Мне нужно понять, почему в этом коде парень использовал сопоставимые классы дерева Хаффмана и строковый буфер. Если кто-то знает какое-либо хорошее объяснение кодировки Хаффмана онлайн или даже алгоритм, пожалуйста. Мне действительно нужно понять этот код. PS: Английский - это не мой родной язык, так что извините за любую путаницу. Спасибо

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

} 

Answer 1

почему парень использовал StringBuffer

Поскольку построение строки, используя один является более предпочтительным, чем строка конкатенации.

StringBuilder vs String concatenation in toString() in Java

When to use StringBuilder in Java

и т.д. ...

StringBuilder несколько отличается от StringBuffer

Why use StringBuilder? StringBuffer can work with multiple thread as well as one thread?

и сопоставимыми

Потому что используется очередь приоритетов. Он нуждается в этом интерфейсе.

How do I use a PriorityQueue?

И, читая кодирования Википедии страницу Хаффмана (которые вы можете сделать, чтобы понять алгоритм), он отмечает, что оптимальная структура кодирования заказана. Я не знаю алгоритма, лично, но я не рекомендую не копировать код из Интернета, который вы не понимаете.