Алгоритм Хаффмана

// скомпилируйте и введите java HuffmanTest
class Tree {
   public Tree child0;       // потомки "0" и "1"
   public Tree child1;
   public boolean leaf;      // признак листового дерева
   public int character;     // входной символ
   public int weight;        // вес этого символа
 
   public Tree() {}
 
   public Tree(int character, int weight, boolean leaf) {
     this.leaf = leaf;
     this.character = character;
     this.weight = weight;
   }
 
/*  Обход дерева с генерацией кодов
    1. "Распечатать" листовое дерево и записать код Хаффмана в массив
    2. Рекурсивно обойти левое поддерево (с генерированием кода).
    3. Рекурсивно обойти правое поддерево.
*/
   public void traverse(String code, Huffman h) {
      if (leaf) {
         System.out.println((char)character +"  "+ weight +"  "+ code);
         h.code[character] = code;
      }
      if ( child0 != null) child0.traverse(code + "0", h);
      if ( child1 != null) child1.traverse(code + "1", h);
   }
}
 
class Huffman {
   public static final int ALPHABETSIZE = 256;
   Tree[] tree   = new Tree[ALPHABETSIZE];          // рабочий массив деревьев
   int weights[] = new int[ALPHABETSIZE];           // веса символов
   public String[] code = new String[ALPHABETSIZE]; // коды Хаффмана
 
   private int getLowestTree(int used) {       // ищем самое "легкое" дерево
      int min=0;
      for (int i=1; i<used; i++)
         if (tree[i].weight < tree[min].weight ) min = i;
      return min;
   }
 
   public void growTree( int[] data ) {    // растим дерево
      for (int i=0; i<data.length; i++)    // считаем веса символов
          weights[data[i]]++;
                                   //  заполняем массив из "листовых" деревьев
      int used = 0;                //  с использованными символами
      for (int c=0; c < ALPHABETSIZE; c++) {
         int w = weights[c];
         if (w != 0) tree[used++] = new Tree(c, w, true);
      }
      while (used > 1) {                    // парами сливаем легкие ветки 
         int min = getLowestTree( used );   // ищем 1 ветку
         int weight0 = tree[min].weight;
         Tree temp = new Tree();            // создаем новое дерево
         temp.child0 = tree[min];           // и прививаем 1 ветку
         tree[min] = tree[--used];          // на место 1 ветки кладем
                                            // последнее дерево в списке
         min = getLowestTree( used );               // ищем 2 ветку и
         temp.child1 = tree[min];                   // прививаем ее к нов.дер.
         temp.weight = weight0 + tree[min].weight;  // считаем вес нов.дер.
         tree[min] = temp;                  // нов.дер. кладем на место 2 ветки
      }                                     // все! осталось 1 дерево Хаффмана
   }
 
   public void makeCode() {            // запускаем вычисление кодов Хаффмана
      tree[0].traverse( "", this);
   }
 
   public String coder( int[] data ) { // кодирует данные строкой из 1 и 0
      String str = "";
      for (int i=0; i<data.length; i++) str += code[data[i]];
      return str;
   }
 
   public String decoder(String data) {
      String str="";                  // проверяем в цикле данные на вхождение
      int l = 0;                      // кода, если да, то отбрасываем его ...
      while(data.length() > 0){
        for (int c=0; c < ALPHABETSIZE; c++) {
           if (weights[c]>0 && data.startsWith(code[c])){
              data = data.substring(code[c].length(), data.length());
              str += (char)c;
           }
        }
      }
      return str;
   }
}
 
public class HuffmanTest {                      // тест и демонстрация
   public static void main(String[] args) {
      Huffman h = new Huffman();
      String str = "to be or not to be?";       // входные данные
      int data[] = new int[str.length()];       // преобразуем в массив
      for (int i=0; i<str.length(); i++) data[i] = str.charAt(i); 
      h.growTree( data );                       // растим дерево
      h.makeCode();                             // находим коды
      str = h.coder(data);
      System.out.println(str);
      System.out.println(h.decoder(str));
   }
}