举例实现哈夫曼编码与译码

哈夫曼编码是一种可变长度编码，它通过将出现频率较高的字符用较短的编码表示，从而实现对文本的高效压缩。下面是Java实现哈夫曼编码与译码的示例代码：

import java.util.PriorityQueue;
import java.util.Scanner;

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

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

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

public class HuffmanCoding {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the input string: ");
        String input = scanner.nextLine();
        int[] frequency = new int[256];
        for (int i = 0; i < input.length(); i++) {
            frequency[input.charAt(i)]++;
        }
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
        for (int i = 0; i < 256; i++) {
            if (frequency[i] > 0) {
                queue.add(new HuffmanNode(frequency[i], (char) i));
            }
        }
        while (queue.size() > 1) {
            HuffmanNode left = queue.poll();
            HuffmanNode right = queue.poll();
            HuffmanNode parent = new HuffmanNode(left.frequency + right.frequency, '-');
            parent.left = left;
            parent.right = right;
            queue.add(parent);
        }
        HuffmanNode root = queue.poll();
        String[] codes = new String[256];
        generateCodes(root, "", codes);
        System.out.println("Huffman Codes:");
        for (int i = 0; i < 256; i++) {
            if (codes[i] != null) {
                System.out.println((char) i + ": " + codes[i]);
            }
        }
        String encoded = encode(input, codes);
        System.out.println("Encoded string: " + encoded);
        String decoded = decode(encoded, root);
        System.out.println("Decoded string: " + decoded);
    }

    public static void generateCodes(HuffmanNode node, String code, String[] codes) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            codes[node.data] = code;
        }
        generateCodes(node.left, code + "0", codes);
        generateCodes(node.right, code + "1", codes);
    }

    public static String encode(String input, String[] codes) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            builder.append(codes[input.charAt(i)]);
        }
        return builder.toString();
    }

    public static String decode(String input, HuffmanNode root) {
        StringBuilder builder = new StringBuilder();
        HuffmanNode current = root;
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '0') {
                current = current.left;
            } else {
                current = current.right;
            }
            if (current.left == null && current.right == null) {
                builder.append(current.data);
                current = root;
            }
        }
        return builder.toString();
    }
}

在这个示例代码中，我们首先输入一个字符串，然后计算每个字符出现的频率。接着，我们使用优先队列来构建哈夫曼树。在构建哈夫曼树的过程中，我们将出现频率较小的节点作为左子树，出现频率较大的节点作为右子树，然后将它们的父节点的频率设置为它们的和。最后，我们使用递归的方式生成每个字符的哈夫曼编码，并将编码存储在一个字符串数组中。接着，我们使用生成的哈夫曼编码对输入字符串进行编码，并输出编码后的字符串。最后，我们使用哈夫曼树对编码后的字符串进行解码，并输出解码后的字符串。