# 霍夫曼压缩算法

## 实现

```①读入完整的输入流，并转化为字符数组。
②计算每个字符出现的次数
③构建Huffman树
④构建编译表
⑤将单词查找树编码成比特输出串并写入到输出流
⑥将单词总数编码成比特输出串并写入到输出流
⑦使用编译表翻译每个输入字符```

### 节点的表示

```    private static final int R = 256;       //字符为ASCII表示

private static class Node implements Comparable<Node> {

private final char ch;
private final int freq;
private final Node left, right;

public Node(char ch, int freq, Node left, Node right) {
this.freq = freq;
this.ch = ch;
this.left = left;
this.right = right;
}

private boolean isLeaf() {
return left == null && right == null;
}

@Override
public int compareTo(Node that) {
return this.freq - that.freq;
}
}```

### 构建Huffman单词查找树

```    /**
* @param freq 字符出现的次数
* @return
*/
private static Node buildTrie(char[] freq) {
MinPQ<Node> pq = new MinPQ<Node>();

//初始化多个将构成一颗Huffman树的结点
for (char i = 0; i < R; i++) {
if (freq[i] > 0) pq.insert(new Node(i, freq[i], null, null));
}

// special case in case there is only one character with a nonzero frequency
if (pq.size() == 1) {
if (freq['\0'] == 0) pq.insert(new Node('\0', 0, null, null));
else pq.insert(new Node('\1', 0, null, null));
}

//归并两个小树
while (pq.size() > 1) {
Node left = pq.delMin();
Node right = pq.delMin();

Node parent = new Node('\0', left.freq + right.freq, left, right);      //创建连接子树的中间结点
pq.insert(parent);
}

return pq.delMin();
}```

### 将Huffman单词查找树转化成字节流写到压缩文件中

```    /**
* 将单词查找树编码成比特输出串并写入到输出流
* 用前序遍历
*/
private static void writeTrie(Node x) {
if (x.isLeaf()) {
BinaryStdOut.write(true);
BinaryStdOut.write(x.ch);
return;
}

BinaryStdOut.write(false);
writeTrie(x.left);
writeTrie(x.right);
}```

### 将压缩文件中字节流转化为Huffman单词查找树

```    /**
* 读比特流，得出一颗单词查找树
*/
return new Node(BinaryStdIn.readChar(), 0, null, null);
}

//读到的是0，说明是中间结点，需要递归直到读到1为止

return new Node('\0', 0, left, right);
}```

### 构建编译表

```    private static void buildCode(String[] st, Node x, String s) {
if (!x.isLeaf()) {
buildCode(st, x.left, s + "0");
buildCode(st, x.right, s + "1");
} else {
st[x.ch] = s;
}

}```

### 压缩

```      /**
* 从输入流中读字节流，并将压缩后的结果写入输出流
*/
private static void compress() {
//①读入完整的输入流，并转化为字符数组
char[] input = s.toCharArray();

//②计算每个字符出现的次数，没有出现的就为0
char[] freq = new char[R];
for (int i = 0; i < input.length; i++) {
freq[input[i]]++;
}

//③构建Huffman树
Node root = buildTrie(freq);

//④构建编译表，将输入中的每个char值与一个比特字符串（即Huffman树上路径）相关联
String st[] = new String[R];
buildCode(st, root, "");

//⑤将单词查找树编码成比特输出串并写入到输出流
writeTrie(root);

//⑥将单词总数编码成比特输出串并写入到输出流
BinaryStdOut.write(input.length);

//⑦使用编译表翻译每个输入字符
for (int i = 0; i < input.length; i++) {
String code = st[input[i]];   //code表示Huffman单词查找数上的路径
for (int j = 0; j < code.length(); j++) {  //要一位一位地输出
if (code.charAt(j) == '1') {
BinaryStdOut.write(true);
} else {
BinaryStdOut.write(false);
}
}

}

BinaryStdOut.close();
}```

### 解压

```     /**
* 解压
* 读取压缩文件的比特流，
* 将比特流对应为路径在单词查找树上找，将找到的结点中的字符写出
*/
private static void expand() {

for (int i = 0; i < N; i++) {   //找出源文件中每个字符

Node x = root;
while (!x.isLeaf()) {       //遍历，知道叶子结点
x = x.right;
} else {
x = x.left;
}

}

BinaryStdOut.write(x.ch);
}

BinaryStdOut.close();
}```

## 参考

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne

43 篇文章26 人订阅

0 条评论

## 相关文章

1022

2759

1261

2095

### Scala第四章学习笔记（面向对象编程)

DelayedInit特质是为编译器提供的标记性的特质。整个构造器被包装成一个函数并传递给delayedInit方法。

881

2857

### c语言基础学习04_条件判断语句

============================================================================= 涉及...

4521

2115

1833