霍夫曼编码，如何处理与字节的压缩

Question

我的霍夫曼压缩程序应该能够压缩任何类型的文件。这就是为什么我使用FileInputStream从文件而不是字符中读取字节。

步骤1.创建的频率表是带有整数的数组。

    /**
 * Initialises field frequencyTable.
 * Opens file, reads one byte at a time and counts each bytes frequency.
 * @param file the file to be read.
 *
 */
private void buildFrequencyTable(String file){
    //since we are reading one byte at a time there are 256 possible values.
    this.frequencyTable = new int[256];
    try{
        FileInputStream in = new FileInputStream(file);
        int currentByte;
        while((currentByte = in.read())!=-1){
            //add that byte to frequencyTable and increment it.
            this.frequencyTable[currentByte] ++;
        }
    }catch (IOException e){
        e.printStackTrace();
    }
}

步骤2：我创建霍夫曼树。

this.pq是优先级。PQ中的所有对象都是为每个唯一字节创建的节点。每个节点都有一个代表字节的整数值。以及代表该字节频率的另一个整数值。节点与它们的频率相当，因此在构建霍夫曼树时，使用较少的位等地编码了频率最高的字节。

节点类：

class Node implements Comparable<Node>{
private int value;
private int frequency;
private Node left_child;
private Node right_child;
Node(int value, int frequency, Node left_child, Node right_child){
    this.value = value;
    this.frequency = frequency;
    this.left_child = left_child;
    this.right_child = right_child;
}
//Checks if two nodes have equal frequency.
private boolean equals(Node n){
    return this.frequency == n.frequency;
}

@Override
public int compareTo(Node other) {
    if(this.equals(other)){
        return 0;
    }else if(this.frequency > other.frequency){
        return 1;
    }else return -1;
}

霍夫曼树建筑商方法：

private void createHuffmanTree(){
    while(this.pq.size() > 1){
        Node left = this.pq.poll();
        Node right = this.pq.poll();
        //null character means its not a leaf node.
        Node parent = new Node('',left.getFrequency()+right.getFrequency(), left, right);
        this.pq.add(parent);
    }
    //The last item in priority queue will be the final huffman tree node.
    this.huffmanTree = this.pq.poll();

}

---

我的问题：

步骤3.进行压缩。

所以现在我准备了一棵霍夫曼树，可以用于创建原始文件的编码版本。但是我不明白这一步。

如果我创建了一个hashmap，将每个字节映射到其Huffman位编码。我是否在地图中将编码作为字符串放置？

等等，如果我创建了一种称为compress((的方法。我一次再次阅读原始文件一个字节。我将如何使用此hashmap来：1。从文件中找到currentbyte的键值，2.找到其相应的位编码(即字符串(，然后将这些单独的位写入另一个是压缩版本的文件？

例如。我有字节65(a(，并具有编码的" 11"。然后，压缩方法将输出：11 11 11(带有额外的填充(

---

注意！我得到了一些代码，这些代码实现了一个名为：bitfilereader的类。该课程读取文件，可以一次阅读。尽管我不知道如何在程序中使用此课程。

Answer 1

伪代码(非常(

void convert(InputStream in, BitFileWriter out) {
    HuffmanTree huffman = new HuffmanTree()
    int b;
    while ((b = in.read()) != -1) {
        huffman.add(b);
        Bits bits = huffman.get(b);
        for (int bit : bits.values()) {
             out.writeBit(bit);
        }
    }
    out.close();
}

位可能只是int[]。或使用bitset：

class Bits {
    final BitSet bitset;
    final int nbits;
    Bits(BitSet bitset, int nbits) {
        this.bitset = bitset;
        this.nbits = nbits;
    }
    int[] values() {
        int[] v = new int[nbits];
        for (int i = bitset.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
            v[i] = 1;
        }
        return v;
    }
}