用java实现哈夫曼问题

这里提供一个简单的 Java 实现哈夫曼编码和解码的示例代码。

import java.util.*;

class HuffmanNode implements Comparable<HuffmanNode> {
    int value;
    char ch;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(int value, char ch, HuffmanNode left, HuffmanNode right) {
        this.value = value;
        this.ch = ch;
        this.left = left;
        this.right = right;
    }

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

    public int compareTo(HuffmanNode node) {
        return value - node.value;
    }
}

public class Huffman {
    public static void main(String[] args) {
        String str = "hello world";
        Map<Character, Integer> freqMap = getFrequency(str);
        HuffmanNode root = buildTree(freqMap);
        Map<Character, String> codeMap = getCode(root);
        String encoded = encode(str, codeMap);
        String decoded = decode(encoded, root);
        System.out.println("Original string: " + str);
        System.out.println("Encoded string: " + encoded);
        System.out.println("Decoded string: " + decoded);
    }

    private static Map<Character, Integer> getFrequency(String str) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : str.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }
        return freqMap;
    }

    private static HuffmanNode buildTree(Map<Character, Integer> freqMap) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            pq.offer(new HuffmanNode(entry.getValue(), entry.getKey(), null, null));
        }
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            pq.offer(new HuffmanNode(left.value + right.value, '\0', left, right));
        }
        return pq.poll();
    }

    private static Map<Character, String> getCode(HuffmanNode root) {
        Map<Character, String> codeMap = new HashMap<>();
        getCodeHelper(root, "", codeMap);
        return codeMap;
    }

    private static void getCodeHelper(HuffmanNode node, String code, Map<Character, String> codeMap) {
        if (node.isLeaf()) {
            codeMap.put(node.ch, code);
        } else {
            getCodeHelper(node.left, code + "0", codeMap);
            getCodeHelper(node.right, code + "1", codeMap);
        }
    }

    private static String encode(String str, Map<Character, String> codeMap) {
        StringBuilder sb = new StringBuilder();
        for (char ch : str.toCharArray()) {
            sb.append(codeMap.get(ch));
        }
        return sb.toString();
    }

    private static String decode(String encoded, HuffmanNode root) {
        StringBuilder sb = new StringBuilder();
        HuffmanNode cur = root;
        for (char ch : encoded.toCharArray()) {
            if (ch == '0') {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
            if (cur.isLeaf()) {
                sb.append(cur.ch);
                cur = root;
            }
        }
        return sb.toString();
    }
}

在本示例中，我们首先计算字符串中每个字符的出现频率，然后使用频率构建哈夫曼树。接着，我们计算每个字符的编码，将原始字符串编码为一系列 0 和 1 的字符串，并进行解码以恢复原始字符串。