Java利用哈夫曼编码实现字符串压缩

介绍

哈夫曼编码是一种可变长度编码，它在通信和数据压缩领域得到广泛的应用。在哈夫曼编码中，出现频率高的字符或词语将被分配短的编码，出现频率低的则分配长的编码，这样可以有效地减少数据的传输量和存储空间。

本攻略将介绍如何使用Java实现字符串的压缩和解压缩，其中包括使用哈夫曼编码来实现压缩。

步骤

以下是压缩和解压缩的完整步骤：

压缩

1. 统计字符串中每个字符出现的次数，生成字符频率表。
2. 将字符频率表构建成哈夫曼树。
3. 生成哈夫曼编码表，将每个字符对应的哈夫曼编码保存在表中。
4. 将原始字符串按照哈夫曼编码表进行编码，生成压缩后的字节数组。
5. 将编码后的字节数组写入文件。

示例1：假设还原字符串为“abcbdcb”， 其中a出现1次，b出现2次，c出现2次，d出现1次，则字符频率表如下：

字符	频率
a	1
b	2
c	2
d	1

生成的哈夫曼树如下：

       6
     /    \
    b(2)   .(4)
          /   \
        2     c(2)
        / \
      a(1) d(1)

生成的哈夫曼编码表如下：

字符	哈夫曼编码
a	001
b	01
c	00
d	11

原始字符串使用生成的哈夫曼编码编码后，得到的压缩字节数组为：

0001101100110101001000001

解压缩

1. 从压缩文件中读取字节数组。
2. 根据字节数组生成二进制字符串。
3. 根据哈夫曼编码表将二进制字符串转换为原始字符串，完成解压缩。
4. 将原始字符串写入文件。

示例2：假设压缩后得到的字节数组为：0001101100110101001000001。使用上述示例1中的哈夫曼编码表，可以将字节数组转换为二进制字符串：

0001101100110101001000001
  ^^^   ^^ ^  ^  ^^   ^
  c  b  d  c  a  b   d

然后再根据哈夫曼编码表将二进制字符串转换为原始字符串，“0001101100110101001000001”经过解码后得到的原始字符串是“abcbdcb”。

代码示例

下面的代码展示了如何使用Java实现压缩和解压缩，包括哈夫曼编码的实现。它使用了Java的BitSet类来实现高效的比特位操作，以便在压缩和解压缩时能够快速地访问和操作比特位。

import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;

public class HuffmanCoding {
    // 定义一个哈夫曼树节点的类
    private static class Node implements Comparable<Node> {
        final char ch;  // 字符
        final int freq; // 频率
        final Node left, right; // 左子节点和右子节点

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

        // 实现优先队列所需要的compareTo方法
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

    // 构建哈夫曼树
    private static Node buildTree(Map<Character, Integer> freq) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            pq.offer(new Node(entry.getKey(), entry.getValue(), null, null));
        }
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            pq.offer(new Node('\0', left.freq + right.freq, left, right));
        }
        return pq.poll();
    }

    // 根据哈夫曼树生成哈夫曼编码表
    private static Map<Character, String> buildTable(Node root) {
        Map<Character, String> table = new HashMap<>();
        buildTableHelper(root, "", table);
        return table;
    }

    private static void buildTableHelper(Node x, String s, Map<Character, String> table) {
        if (x.left == null && x.right == null) {
            table.put(x.ch, s);
            return;
        }
        buildTableHelper(x.left, s + '0', table);
        buildTableHelper(x.right, s + '1', table);
    }

    // 哈夫曼编码的压缩
    public static byte[] compress(String text) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char ch : text.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }

        Node root = buildTree(freq);
        Map<Character, String> table = buildTable(root);

        BitSet bits = new BitSet();
        int size = 0;
        for (char ch : text.toCharArray()) {
            String code = table.get(ch);
            for (int i = 0; i < code.length(); i++) {
                if (code.charAt(i) == '1') {
                    bits.set(size);
                }
                size++;
            }
        }

        byte[] bytes = new byte[(size + 7) / 8];
        for (int i = 0; i < size; i++) {
            if (bits.get(i)) {
                bytes[i / 8] |= (1 << (7 - i % 8));
            }
        }
        return bytes;
    }

    // 哈夫曼编码的解压缩
    public static String decompress(byte[] bytes) {
        BitSet bits = BitSet.valueOf(bytes);

        StringBuilder sb = new StringBuilder();
        Node x = root;
        for (int i = 0; i < bits.length(); i++) {
            x = bits.get(i) ? x.right : x.left;
            if (x.left == null && x.right == null) {
                sb.append(x.ch);
                x = root;
            }
        }
        return sb.toString();
    }
}

压缩示例代码

使用上述HuffmanCoding类实现字符串压缩的示例代码：

String text = "abcbdcb";
byte[] compressed = HuffmanCoding.compress(text);
// 将压缩后的字节数组写入文件

解压缩示例代码

使用上述HuffmanCoding类实现字符串解压缩的示例代码：

byte[] compressed = // 从文件中读取压缩后的字节数组
String original = HuffmanCoding.decompress(compressed);
// 将解压缩后的原始字符串写入文件