Хаффман суффикс-код

Question

Я пытаюсь эффективно построить двоичный код суффикса для заданного набора символов с их вероятностями (т. Е. Набор слов, ни один из которых не является суффиксом какого-либо другого).

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

Есть ли способ изменить алгоритм Хаффмана, чтобы более эффективно создать суффикс-код?

Answer 1

Я бы реализовать HuffmanNode в

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 + "}"; 
    } 
} 

Этот класс представляет собой единый узел в дереве Хаффмана.
У этого есть удобные методы для получения всех листьев из (под) дерева.

Вы можете легко построить дерево:

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

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