java 哈夫曼树优先级

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 上调用。

针对你的第二个问题，我认为你应该在 Huffman 类中使用 encode() 和 decode() 方法本身或另一个类中。显然，您可以从主方法中调用它们，但我会从主方法中提取任何可以在其他地方重用的内容。

编辑:您要求我详细说明。您的第二个问题不太清楚，但似乎您陷入了如何进行编码和解码的困境。我首先添加到 HuffmanTree 方法 toMapForDecoding() 和 toMapForEncoding()，每个方法都返回一个 Map (它基本上与两种方法，但键和值相反)。这些映射(在 encode() 和 decode() 方法中使用)允许输入符号和(编码或解码)输出符号之间的恒定时间转换。这些方法的实现与您在 printCodes() 中所做的非常相似。至于把encode()和decode()方法放在哪里，不要被那个挡住了。将它们放在您方便的地方，然后在需要时移动它们。