java huffman tree precedence

Question

我對以下代碼有兩個問題，我過去幾天一直在研究。如何實現以下規則：如果存在多個關係（意味着相同數量的頻率），以便將單個字母組優先於多個字母，然後按字母順序排列？我的第二個問題是，有人可以指向我的編碼/解碼代碼方向嗎？我是否應該通過我的主要聲明來實施它，或者繼續並完成新的課程？我有點卡在從哪裏開始。

import java.util.*; 


//The following is code that is hardcoded with two separate arrays consisting of 
//characters and their corresponding frequency. The application takes in these two 
//arrays and constructs a Huffman Encoding Tree. It begins by showing the user the 
//letters, frequency, and the Huffman Code that will be assigned to that letter. 
//The application then takes in a .txt file with various strings and encodes them. 
//This result is also shown. [still working on this part-- question above] 


abstract 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) { 
    super(l.frequency + r.frequency); 
    left = l; 
    right = r; 
} 
} 

public class Huffman { 

public static void main(String[] args) { 
    //Symbols that are given to us to hard code 
    String letters = "abcdefghijklmnopqrstuvwxyz"; 

    //converting string to character array 
    char[] letterArray = letters.toCharArray(); 

    //Frequency of the letters given to us above: 
    int[] letterFreqs = {19, 16, 17, 11, 42, 12, 14, 17, 16, 5, 10, 20, 19, 24, 18, 13, 
     1, 25, 35, 25, 15, 5, 21, 2, 8, 3}; 


    // build tree 
    HuffmanTree tree = constructTree(letterFreqs,letterArray); 

    // print out results 
    System.out.println("Letter\tFrequency\tEncoding"); 
    printCodes(tree, new StringBuffer()); 
    } 




// input is an array of frequencies and a string of letters 
public static HuffmanTree constructTree(int[] charFreqs, char[] letters) { 

    //sets up the priority queue to begin constructing the tree 
    PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>(); 

    //for loop to take in the characters and there frequencies 
    for (int i = 0; i < charFreqs.length; i++) 
     if (charFreqs[i] > 0) 
      trees.offer(new HuffmanLeaf(charFreqs[i], letters[i])); 

    assert trees.size() > 0; 
    // loop until there is only one tree left 
    while (trees.size() > 1) { 

     // find the two lowest frequencies 
     HuffmanTree a = trees.poll(); 
     HuffmanTree b = trees.poll(); 

     // construct a new node and re-insert into queue 
     trees.offer(new HuffmanNode(a, b)); 
    } 
    return trees.poll(); 
} 

public static 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" + "\t" + prefix); 


    } else if (tree instanceof HuffmanNode) { 
     HuffmanNode node = (HuffmanNode)tree; 

     // traverse left 
     prefix.append('0'); 
     printCodes(node.left, prefix); 
     prefix.deleteCharAt(prefix.length()-1); 

     // traverse right 
     prefix.append('1'); 
     printCodes(node.right, prefix); 
     prefix.deleteCharAt(prefix.length()-1); 
    } 
} 

} 

Answer 1

在回答你的第一個問題，你控制通過的compareTo()實施優先級隊列的順序，所以我會做類似如下：

abstract class HuffmanTree implements Comparable<HuffmanTree> { 
    public final int frequency; // the frequency of this tree 

    public HuffmanTree(int freq) { 
     frequency = freq; 
    } 

    @Override 
    public int compareTo(HuffmanTree tree) { 
     int comparison = frequency - tree.frequency; 
     if (0 == comparison) { 
      comparison = comparisonTieBreaker(tree); 
     } 

     return comparison; 
    } 
    private int comparisonTieBreaker(HuffmanTree tree) { 
    int comparison = 0; 
    if (this.size() == 1) { 
     if (tree.size() == 1) { 
      // alphabetical comparison between 2 single-character groups: 
      Character.compare(this.firstChar(), tree.firstChar()); 
     } 
     else { 
      comparison = -1; // single < multiple 
     } 
    } else if (tree.size() == 1) { 
     comparison = 1; // multiple > single 
    } 
    return comparison; 
} 

public abstract int size(); 

public abstract char firstChar(); 
} 

至於兩個抽象方法，在HuffmanLeaf,size()返回1，firstChar()返回其字符。在HuffmanNode,size()返回left.size() + right.size()（基本遞歸）和firstChar()可以返回left.firstChar()，但firstChar()通常不會在HuffmanNode上調用。

迴應你的第二個問題，我認爲你應該有encode()和decode()方法，無論是在Huffman類本身還是在另一個類中。你可以明顯地從主函數中調用它們，但是我會從主函數中抽出任何可以在別處重用的東西。

編輯：你讓我詳細說明。你的第二個問題還不是很清楚，但你似乎陷入瞭如何進行編碼和解碼。我首先將HuffmanTree方法toMapForDecoding()和toMapForEncoding()加入到HuffmanTree中，每個方法都返回一個Map（兩個方法基本上都是相同的映射，但鍵和值反轉）。這些映射（將用於您的encode()和decode()方法）允許在輸入符號和（編碼或解碼）輸出符號之間進行恆定時間轉換。這些方法的實現可能與您在printCodes()中已完成的操作非常相似。至於在哪裏放置encode()和decode()方法，不要被阻止。把它們放在方便你的地方，然後在需要時再移動它們。