Kod sufiksu Huffmana

Question

Próbuję wydajnie skonstruować kod binarnego sufiksu dla danego zestawu znaków z ich prawdopodobieństwami (tj. Zestawem słów, z których żaden nie jest przyrostkiem żadnego innego).

Moją podstawową ideą jest skonstruowanie kodu prefiksu za pomocą implementacji algorytmu Huffmana. Odwracając słowa kodowe otrzymuję kod bez sufiksu. Chociaż to rozwiązanie działa, może nie wydawać się optymalne, ponieważ muszę odwrócić słowa kodowe o zmiennej długości (w związku z tym potrzebuję tabeli odnośników w połączeniu z przesunięciami bitowymi).

Czy istnieje sposób zmodyfikowania algorytmu Huffmana w celu wydajniejszego utworzenia kodu sufiksowego?

Answer 1

chciałbym wdrożyć HuffmanNode jak

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

Klasa ta reprezentuje pojedynczy węzeł w drzewie Huffmana.
Posiada wygodne metody uzyskiwania wszystkich liści z drzewa (pod).

Następnie można łatwo zbudować drzewo:

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

Zmieniając sposób, który buduje kod (na przykład wstępnie oczekiwaniu na następną cyfrę zamiast dołączania go) można zmienić kody produkowane.