用Java实现哈夫曼编码问题

哈夫曼编码是一种前缀编码方法，可以通过统计字符出现频率来生成最优编码。在Java中，可以通过构建哈夫曼树来实现。

首先，我们需要定义一个节点类来表示哈夫曼树中的节点：

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

    public HuffmanNode(int frequency, char data) {
        this.frequency = frequency;
        this.data = data;
    }

    @Override
    public int compareTo(HuffmanNode o) {
        return this.frequency - o.frequency;
    }
}

然后，我们可以使用一个优先队列来存储节点，并按照节点出现频率排序。接下来，我们可以通过不断取出队列中频率最小的两个节点，并将它们合并成一个新节点，直到队列中只剩下一个节点为止。这个最后剩下的节点就是哈夫曼树的根节点。

public static HuffmanNode buildHuffmanTree(Map<Character, Integer> charFrequencies) {
    PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
    for (Map.Entry<Character, Integer> entry : charFrequencies.entrySet()) {
        queue.offer(new HuffmanNode(entry.getValue(), entry.getKey()));
    }

    while (queue.size() > 1) {
        HuffmanNode node1 = queue.poll();
        HuffmanNode node2 = queue.poll();

        HuffmanNode mergedNode = new HuffmanNode(node1.frequency + node2.frequency, '\0');
        mergedNode.left = node1;
        mergedNode.right = node2;

        queue.offer(mergedNode);
    }

    return queue.poll();
}

一旦我们有了哈夫曼树，我们就可以通过遍历树来生成编码表。对于每个叶子节点，我们可以追溯它的祖先节点，记录下每个节点的编码。在遍历过程中，我们可以使用一个StringBuilder来记录当前路径。

public static Map<Character, String> buildHuffmanTable(HuffmanNode root) {
    Map<Character, String> table = new HashMap<>();
    StringBuilder sb = new StringBuilder();
    buildHuffmanTable(root, table, sb);
    return table;
}

private static void buildHuffmanTable(HuffmanNode node, Map<Character, String> table, StringBuilder sb) {
    if (node == null) {
        return;
    }

    if (node.left == null && node.right == null) {
        table.put(node.data, sb.toString());
        return;
    }

    sb.append('0');
    buildHuffmanTable(node.left, table, sb);
    sb.setLength(sb.length() - 1);

    sb.append('1');
    buildHuffmanTable(node.right, table, sb);
    sb.setLength(sb.length() - 1);
}

最后，我们可以使用编码表来对字符串进行编码和解码。

public static String encode(String input, Map<Character, String> table) {
    StringBuilder sb = new StringBuilder();
    for (char c : input.toCharArray()) {
        sb.append(table.get(c));
    }
    return sb.toString();
}

public static String decode(String input, HuffmanNode root) {
    StringBuilder sb = new StringBuilder();
    HuffmanNode node = root;
    for (char c : input.toCharArray()) {
        if (c == '0') {
            node = node.left;
        } else {
            node = node.right;
        }
        if (node.left == null && node.right == null) {
            sb.append(node.data);
            node = root;
        }
    }
    return sb.toString();
}

完整的实现代码如下：

import java.util.*;

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

    public HuffmanNode(int frequency, char data) {
        this.frequency = frequency;
        this.data = data;
    }

    @Override
    public int compareTo(HuffmanNode o) {
        return this.frequency - o.frequency;
    }
}

public class HuffmanCoding {

    public static void main(String[] args) {
        String input = "hello world";
        Map<Character, Integer> charFrequencies = getCharFrequencies(input);
        HuffmanNode root = buildHuffmanTree(charFrequencies);
        Map<Character, String> table = buildHuffmanTable(root);

        String encoded = encode(input, table);
        System.out.println("Encoded: " + encoded);

        String decoded = decode(encoded, root);
        System.out.println("Decoded: " + decoded);
    }

    public static Map<Character, Integer> getCharFrequencies(String input) {
        Map<Character, Integer> charFrequencies = new HashMap<>();
        for (char c : input.toCharArray()) {
            charFrequencies.put(c, charFrequencies.getOrDefault(c, 0) + 1);
        }
        return charFrequencies;
    }

    public static HuffmanNode buildHuffmanTree(Map<Character, Integer> charFrequencies) {
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : charFrequencies.entrySet()) {
            queue.offer(new HuffmanNode(entry.getValue(), entry.getKey()));
        }

        while (queue.size() > 1) {
            HuffmanNode node1 = queue.poll();
            HuffmanNode node2 = queue.poll();

            HuffmanNode mergedNode = new HuffmanNode(node1.frequency + node2.frequency, '\0');
            mergedNode.left = node1;
            mergedNode.right = node2;

            queue.offer(mergedNode);
        }

        return queue.poll();
    }

    public static Map<Character, String> buildHuffmanTable(HuffmanNode root) {
        Map<Character, String> table = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        buildHuffmanTable(root, table, sb);
        return table;
    }

    private static void buildHuffmanTable(HuffmanNode node, Map<Character, String> table, StringBuilder sb) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            table.put(node.data, sb.toString());
            return;
        }

        sb.append('0');
        buildHuffmanTable(node.left, table, sb);
        sb.setLength(sb.length() - 1);

        sb.append('1');
        buildHuffmanTable(node.right, table, sb);
        sb.setLength(sb.length() - 1);
    }

    public static String encode(String input, Map<Character, String> table) {
        StringBuilder sb = new StringBuilder();
        for (char c : input.toCharArray()) {
            sb.append(table.get(c));
        }
        return sb.toString();
    }

    public static String decode(String input, HuffmanNode root) {
        StringBuilder sb = new StringBuilder();
        HuffmanNode node = root;
        for (char c : input.toCharArray()) {
            if (c == '0') {
                node = node.left;
            } else {
                node = node.right;
            }
            if (node.left == null && node.right == null) {
                sb.append(node.data);
                node = root;
            }
        }
        return sb.toString();
    }
}