哈夫曼编码（Huffman-Coding）

哈夫曼编码（Huffman Coding），又称为霍夫曼编码，是一种变长编码（Variable-length Code）的压缩算法，由美国学者大卫·哈夫曼（David Huffman）于1952年提出。

哈夫曼编码是一种无损压缩算法，它通过将频率较高的字符用较短的编码表示，将频率较低的字符用较长的编码表示，从而达到压缩数据的目的。它的基本思想是将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，以此来减少编码的长度。

哈夫曼编码的主要步骤如下：

统计每个字符在文本中出现的频率，并按照频率从小到大排序。 将频率最小的两个字符组成一个新的节点，节点的权值为两个字符的权值之和，将这个节点加入到字符集合中。 将新节点与其他节点继续排序，重复步骤2和步骤3，直到所有的节点都被合并成一棵树。 对于树中的每个字符，按照从根节点到该字符的路径记录该字符的编码。 由于哈夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀，因此哈夫曼编码可以保证解码的唯一性。

在实际应用中，哈夫曼编码通常被用于压缩文本、图像和音频等数据。由于哈夫曼编码具有高压缩比、解压速度快等优点，因此它是目前常用的无损压缩算法之一。

Java中可以通过构建哈夫曼树来实现哈夫曼编码，通常使用优先队列（PriorityQueue）来存储节点。可以使用HashMap来存储每个字符的出现频率，并使用字符集合（HashSet）来存储文本中出现的所有字符。

以下是哈夫曼编码的 Java 实现示例：

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

class HuffmanNode {
    int data;
    char c;
    HuffmanNode left;
    HuffmanNode right;
}

class MyComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.data - y.data;
    }
}

public class HuffmanCoding {
    public static void printCode(HuffmanNode root, String s) {
        if (root.left == null && root.right == null && Character.isLetter(root.c)) {
            System.out.println(root.c + ":" + s);
            return;
        }
        printCode(root.left, s + "0");
        printCode(root.right, s + "1");
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.print("Enter string: ");
        String str = s.nextLine();
        int[] charFreq = new int[26];
        for (int i = 0; i < str.length(); i++) {
            charFreq[str.charAt(i) - 'a']++;
        }
        PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(new MyComparator());
        for (int i = 0; i < 26; i++) {
            if (charFreq[i] > 0) {
                HuffmanNode hn = new HuffmanNode();
                hn.c = (char) ('a' + i);
                hn.data = charFreq[i];
                hn.left = null;
                hn.right = null;
                q.add(hn);
            }
        }
        HuffmanNode root = null;
        while (q.size() > 1) {
            HuffmanNode x = q.peek();
            q.poll();
            HuffmanNode y = q.peek();
            q.poll();
            HuffmanNode f = new HuffmanNode();
            f.data = x.data + y.data;
            f.c = '-';
            f.left = x;
            f.right = y;
            root = f;
            q.add(f);
        }
        System.out.println("Huffman Codes are : ");
        printCode(root, "");
    }
}

此示例中，我们首先使用 Scanner 类从用户输入中获取字符串。接下来，我们计算每个字母出现的频率，并将其存储在 charFreq 数组中。然后，我们使用优先队列来创建哈夫曼树，使用 MyComparator 类来比较节点。最后，我们使用 printCode 函数打印哈夫曼编码。