Java函数实现哈夫曼编码和解码

1. 哈夫曼编码

哈夫曼编码是一种压缩算法，将经常使用的字符用较短的编码表示，减小数据传输和存储的成本。哈夫曼编码的基本思想是，将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示。

1.1. 哈夫曼树

哈夫曼编码的实现需要用到哈夫曼树。哈夫曼树是一种二叉树，每个节点可以是一个字符或一个频率。哈夫曼树的构建过程如下：

1. 将所有字符按照出现频率排序，频率较低的字符在左边，频率较高的字符在右边。

2. 取出频率最低的两个字符作为左右子节点创建一个新节点，并将频率为这两个字符频率之和。

3. 重复上述步骤，直到所有节点都被加入哈夫曼树中。

1.2. 哈夫曼编码

哈夫曼编码的实现需要用到哈夫曼树。将哈夫曼树的左边节点编码为0，右边节点编码为1，得到每个字符的哈夫曼编码。

例如，哈夫曼树如下所示：


其中'a'的哈夫曼编码是10，'b'的哈夫曼编码是110，'c'的哈夫曼编码是111，'d'的哈夫曼编码是0。

2. 哈夫曼解码

哈夫曼解码是将哈夫曼编码还原成原始数据，需要用到哈夫曼树。从哈夫曼树的根节点开始，对于每个0向左走，对于每个1向右走，直到到达叶子节点，即找到对应的字符。

例如，考虑上述哈夫曼树和编码"110101100"，首先向左走一步，到达'b'的节点，接着向右走两步，到达'a'的节点，然后向左走一步，到达'd'的节点，接着向右走两步，到达'b'的节点。因此原始数据为"abd"。

3. Java函数实现

下面是使用Java代码实现哈夫曼编码和解码的示例：

import java.util.*;

public class Huffman {
    private class Node implements Comparable<Node> {
        char data;
        int freq;
        Node left;
        Node right;
        
        Node(char data, int freq) {
            this.data = data;
            this.freq = freq;
        }
        
        Node(int freq, Node left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
        
        boolean isLeaf() {
            return left == null && right == null;
        }

        @Override
        public int compareTo(Node other) {
            return this.freq - other.freq;
        }
    }
    
    private Node root;
    private Map<Character, String> codeTable = new HashMap<>();

    public void buildTree(char[] arr, int[] freq) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            pq.offer(new Node(arr[i], freq[i]));
        }
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            pq.offer(new Node(left.freq + right.freq, left, right));
        }
        root = pq.poll();
    }
    
    public void buildCodeTable() {
        StringBuilder sb = new StringBuilder();
        buildCodeTable(root, sb);
        }

    private void buildCodeTable(Node node, StringBuilder sb) {
        if (node.isLeaf()) {
            codeTable.put(node.data, sb.toString());
        } else {
            sb.append("0");
            buildCodeTable(node.left, sb);
            sb.deleteCharAt(sb.length() - 1);
            sb.append("1");
            buildCodeTable(node.right, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    public String encode(String data) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < data.length(); i++) {
            sb.append(codeTable.get(data.charAt(i)));
        }
        return sb.toString();
    }
    
    public String decode(String encoded) {
        StringBuilder sb = new StringBuilder();
        Node curr = root;
        for (int i = 0; i < encoded.length(); i++) {
            curr = encoded.charAt(i) == '0' ? curr.left : curr.right;
            if (curr.isLeaf()) {
                sb.append(curr.data);
                curr = root;
            }
        }
        return sb.toString();
    }
}

使用方法如下：

Huffman huffman = new Huffman();
char[] arr = {'a', 'b', 'c', 'd'};
int[] freq = {2, 3, 4, 5};
huffman.buildTree(arr, freq);
huffman.buildCodeTable();
String encoded = huffman.encode("abd");
System.out.println(encoded); // 输出：101100
String decoded = huffman.decode(encoded);
System.out.println(decoded); // 输出：abd

这个示例中，首先创建了一个Huffman对象，并调用buildTree方法构建哈夫曼树，然后调用buildCodeTable方法构建哈夫曼编码表。最后使用encode方法将数据"abd"编码成"101100"，使用decode方法将编码"101100"还原成原始数据"abd"。