Huffman sonek kodu

Question

Belirli bir karakter kümesi için olasılıkları (yani hiçbiri diğerinin eki olmayan bir sözcük kümesi) için ikili bir sonek kodunu verimli bir şekilde oluşturmaya çalışıyorum.

Temel fikrim Huffman algoritmasının uygulanmasını kullanarak bir önek kodu oluşturmaktır. Kod kelimelerini tersine çevirerek, bir ek içermeyen kod alırım. Bu çözüm çalışırken, değişken görünmeyebilir, çünkü değişken uzunluktaki kod sözcüklerini tersine çevirmeliyim (böylece bit vardiyalarıyla birlikte bir arama tablosuna ihtiyacım var).

Sonek kodu daha verimli bir şekilde oluşturmak için Huffman algoritmasını değiştirmenin bir yolu var mı?

Answer 1

Ben

class HuffmanNode implements Comparable<HuffmanNode> 
{ 
    // data 
    private String text; 
    private double frequency; 

    // linkage 
    private HuffmanNode left; 
    private HuffmanNode right; 
    private HuffmanNode parent; 

    public HuffmanNode(String text, double frequency) 
    { 
     this.text = text; 
     this.frequency = frequency; 
    } 
    public HuffmanNode(HuffmanNode n0, HuffmanNode n1) 
    { 
     if(n0.frequency < n1.frequency) 
     { 
      left = n0; 
      right = n1; 
     }else if(n0.frequency > n1.frequency) 
     { 
      left = n1; 
      right = n0; 
     }else 
     { 
      if(n0.text.compareTo(n1.text) < 0) 
      { 
       left = n0; 
       right = n1; 
      }else 
      { 
       left = n1; 
       right = n0; 
      } 
     } 
     left.parent = this; 
     right.parent = this; 
     text = left.text + right.text; 
     frequency = left.frequency + right.frequency; 
    } 

    public HuffmanNode getParent() { 
     return parent; 
    } 

    public HuffmanNode getLeft() { 
     return left; 
    } 

    public HuffmanNode getRight() { 
     return right; 
    } 

    public String getText() 
    { 
     return text; 
    } 

    @Override 
    public int compareTo(HuffmanNode o) { 
     if(frequency < o.frequency) 
      return -1; 
     else if(frequency > o.frequency) 
      return 1; 
     else 
      return text.compareTo(o.text); 
    } 

    public Collection<HuffmanNode> leaves() 
    { 
     if(left == null && right == null) 
     { 
      Set<HuffmanNode> retval = new HashSet<>(); 
      retval.add(this); 
      return retval; 
     } 
     else if(left == null || right == null) 
     { 
      Set<HuffmanNode> retval = new HashSet<>(); 
      if(left != null) 
       retval.addAll(left.leaves()); 
      if(right != null) 
       retval.addAll(right.leaves()); 
      retval.add(this); 
      return retval; 
     } 
     else 
     { 
      Set<HuffmanNode> retval = new HashSet<>(); 
      retval.addAll(left.leaves()); 
      retval.addAll(right.leaves()); 
      return retval; 
     } 
    } 

    public String toString() 
    { 
     return "{" + text + " -> " + frequency + "}"; 
    } 
} 

Bu sınıf bir Huffman ağacında tek bir düğüm temsil olarak HuffmanNode uygulamaya koyacak.
Tüm yaprakları bir (alt) ağaçtan almak için kolaylık yöntemleri vardır. Daha sonra kolayca ağacı oluşturabilirsiniz

:

private Map<String,String> buildTree(String text) 
{ 
    List<HuffmanNode> nodes = new ArrayList<>(); 
    for(Map.Entry<String,Double> en : frequency(text).entrySet()) 
    { 
     nodes.add(new HuffmanNode(en.getKey(), en.getValue())); 
    } 
    java.util.Collections.sort(nodes); 
    while(nodes.size() != 1) 
    { 
     HuffmanNode n0 = nodes.get(0); 
     HuffmanNode n1 = nodes.get(1); 

     // build merged node 
     HuffmanNode newNode = new HuffmanNode(nodes.get(0), nodes.get(1)); 
     nodes.remove(n0); 
     nodes.remove(n1); 

     // calculate insertion point 
     int insertionPoint = - java.util.Collections.binarySearch(nodes, newNode) - 1; 

     // insert 
     nodes.add(insertionPoint, newNode); 
    } 

    // build lookup table 
    Map<String, String> lookupTable = new HashMap<>(); 
    for(HuffmanNode leaf : nodes.iterator().next().leaves()) 
    { 
     String code = ""; 
     HuffmanNode tmp = leaf; 
     while(tmp.getParent() != null) 
     { 
      if(tmp.getParent().getLeft() == tmp) 
       code = "0" + code; 
      else 
       code = "1" + code; 
      tmp = tmp.getParent(); 
     } 
     lookupTable.put(leaf.getText(), code); 
    } 
    return lookupTable; 
} 

kodunu oluşturan yöntemi değiştirerek (örneğin için ekleme yerine gelecek rakamı önceden beklemede) Eğer kodları üretilen değiştirebilir.