java实现哈弗曼编码与反编码实例分享(哈弗曼算法)

当然，我可以提供一个简化的Java示例来展示如何使用哈弗曼编码（Huffman Coding）算法进行编码和解码。这里我们将构建一个简单的系统，包括构建哈弗曼树、生成编码表、编码和解码字符串。

### 步骤 1: 定义哈弗曼树节点

首先，我们需要一个哈弗曼树的节点类，包含字符、频率和左右子节点。

class HuffmanNode implements Comparable<HuffmanNode> {
    char data;
    int freq;
    HuffmanNode left, right;

    public HuffmanNode(char data, int freq) {
        this.data = data;
        this.freq = freq;
        this.left = null;
        this.right = null;
    }

    @Override
    public int compareTo(HuffmanNode other) {
        return Integer.compare(this.freq, other.freq);
    }
}

### 步骤 2: 构建哈弗曼树

接下来，我们需要一个方法来根据字符频率构建哈弗曼树。

import java.util.*;

public class HuffmanCoding {
    // 构建哈弗曼树
    static HuffmanNode buildHuffmanTree(Map<Character, Integer> freq) {
        PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>(freq.size(), Comparator.comparingInt(a -> a.freq));
        freq.forEach((k, v) -> priorityQueue.add(new HuffmanNode(k, v)));

        while (priorityQueue.size() != 1) {
            HuffmanNode left = priorityQueue.poll();
            HuffmanNode right = priorityQueue.poll();

            HuffmanNode top = new HuffmanNode('$', left.freq + right.freq);
            top.left = left;
            top.right = right;
            priorityQueue.add(top);
        }

        return priorityQueue.poll();
    }

    // 其他方法...
}

### 步骤 3: 生成编码表

我们需要一个方法来从哈弗曼树生成编码表。

public static Map<Character, String> generateCodes(HuffmanNode root, String s) {
    Map<Character, String> map = new HashMap<>();
    generateCodesUtil(root, "", map);
    return map;
}

private static void generateCodesUtil(HuffmanNode root, String s, Map<Character, String> map) {
    if (root.left == null && root.right == null && root.data != '$') {
        map.put(root.data, s);
    }

    if (root.left != null) {
        generateCodesUtil(root.left, s + "0", map);
    }

    if (root.right != null) {
        generateCodesUtil(root.right, s + "1", map);
    }
}

### 步骤 4: 编码和解码

最后，我们可以添加编码和解码的方法。

``

`java

// 编码

public static String encode(String str, Map huffmanCodes) {

StringBuilder encodedStr = new StringBuilder();

for (int i = 0; i < str.length(); i++) {

char ch = str.charAt(i);

if (huffmanCodes.containsKey(ch)) {

encodedStr.append(huffmanCodes.get(ch));

}

}

return encodedStr.toString();

}

// 解码（简单示例，需要额外的逻辑来从编码中恢复原始字符串）

public static String decode(String encodedStr, HuffmanNode root) {

// 注意：这里的解码部分只是示例，真实解码需要递归遍历树

// 通常我们会将编码的二进制字符串转换为字符流

// 这里省略了详细的解码逻辑

return "解码逻辑略...";

}

// 主方法（示例）

public static void main(String[] args) {

// 示例字符频率

Map freq = new HashMap<>();

freq.put('a', 5);

freq.put('b', 9);

freq.put('c', 12);

freq.put('d', 13);

freq.put('e', 16);

freq.put('f', 45);

HuffmanNode root = buildHuffmanTree(freq);

Map codes = generateCodes(root, "");

String encoded = encode("abcdef", codes);

System.out.println("Encoded String: " + encoded);

//