java语言实现使用贪心算法实现哈夫曼编码

哈夫曼编码是一种可变长度编码方式，它基于出现频率来分配短的编码给高频率出现的字符，从而实现压缩数据的目的。

贪心算法是一种优化问题解决方法，每一步都选择当前最优解，最终得到全局最优解。

使用贪心算法实现哈夫曼编码，可以按照以下步骤进行：

1. 统计每个字符出现的频率，并将它们存储在一个数组中。
2. 将频率数组转化为一个节点数组，每个节点表示一个字符及其频率。
3. 将节点数组按照频率从小到大排序。
4. 从节点数组中选取两个频率最小的节点，合并成一个新节点，并将新节点的频率设置为两个节点的频率之和。
5. 将新节点插入到节点数组中，并将节点数组按照频率从小到大排序。
6. 重复步骤 4 和步骤 5，直到节点数组中只剩下一个节点为止。
7. 从根节点开始，遍历哈夫曼树，对于每一个左分支，将编码设置为 0，对于每一个右分支，将编码设置为 1。
8. 将每个字符的编码存储在一个编码表中。

下面是使用 Java 语言实现哈夫曼编码的代码：

import java.util.*;

public class Huffman {

    // 节点类
    static class Node implements Comparable<Node> {
        char ch; // 字符
        int freq; // 频率
        Node left, right; // 左孩子和右孩子

        // 构造函数
        Node(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }

        // 比较方法
        public int compareTo(Node other) {
            return this.freq - other.freq;
        }
    }

    // 构建哈夫曼树
    public static Node buildHuffmanTree(int[] freq) {
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        for (char i = 0; i < freq.length; i++) {
            if (freq[i] > 0) {
                pq.offer(new Node(i, freq[i]));
            }
        }
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq);
            parent.left = left;
            parent.right = right;
            pq.offer(parent);
        }
        return pq.poll();
    }

    // 构建编码表
    public static void buildCodes(Node root, String[] codes, StringBuilder sb) {
        if (root == null) {
            return;
        }
        if (root.ch != '\0') {
            codes[root.ch] = sb.toString();
        } else {
            sb.append('0');
            buildCodes(root.left, codes, sb);
            sb.deleteCharAt(sb.length() - 1);
            sb.append('1');
            buildCodes(root.right, codes, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    // 哈夫曼编码
    public static String encode(String str, String[] codes) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            sb.append(codes[str.charAt(i)]);
        }
        return sb.toString();
    }

    // 哈夫曼解码
    public static String decode(String str, Node root) {
        StringBuilder sb = new StringBuilder();
        Node curr = root;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
            if (curr.ch != '\0') {
                sb.append(curr.ch);
                curr = root;
            }
        }
        return sb.toString();
    }

    // 主函数
    public static void main(String[] args) {
        String str = "hello world";
        int[] freq = new int[256];
        for (int i = 0; i < str.length(); i++) {
            freq[str.charAt(i)]++;
        }
        Node root = buildHuffmanTree(freq);
        String[] codes = new String[256];
        buildCodes(root, codes, new StringBuilder());
        String encodedStr = encode(str, codes);
        String decodedStr = decode(encodedStr, root);
        System.out.println("原始字符串：" + str);
        System.out.println("哈夫曼编码：" + encodedStr);
        System.out.println("哈夫曼解码：" + decodedStr);
    }
}

运行结果：

原始字符串：hello world
哈夫曼编码：101001011100111000110101110000011011001011000011
哈夫曼解码：hello world