基于哈夫曼树的数据压缩算法java

哈夫曼树是一种常用的数据压缩算法，以下是基于哈夫曼树的数据压缩算法的Java实现。

首先，我们需要定义一个哈夫曼树的节点类，包含字符、权重和左右子节点等属性：

class HuffmanNode {
    char c;
    int weight;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(char c, int weight) {
        this.c = c;
        this.weight = weight;
    }

    public HuffmanNode(HuffmanNode left, HuffmanNode right) {
        this.weight = left.weight + right.weight;
        this.left = left;
        this.right = right;
    }

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

接下来，我们需要实现构建哈夫曼树的方法。我们可以先统计字符出现的频率，然后根据频率构建哈夫曼树。具体实现如下：

public static HuffmanNode buildHuffmanTree(String text) {
    Map<Character, Integer> freqMap = new HashMap<>();
    for (char c : text.toCharArray()) {
        freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
    }

    PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight));
    for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
        pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
    }

    while (pq.size() > 1) {
        HuffmanNode left = pq.poll();
        HuffmanNode right = pq.poll();
        pq.offer(new HuffmanNode(left, right));
    }

    return pq.poll();
}

接着，我们可以实现编码和解码方法。编码方法将输入的字符串转换为二进制编码，解码方法将二进制编码转换为原字符串。具体实现如下：

public static Map<Character, String> buildEncodingMap(HuffmanNode root) {
    Map<Character, String> map = new HashMap<>();
    buildEncodingMapHelper(root, "", map);
    return map;
}

private static void buildEncodingMapHelper(HuffmanNode node, String code, Map<Character, String> map) {
    if (node.isLeaf()) {
        map.put(node.c, code);
        return;
    }
    buildEncodingMapHelper(node.left, code + "0", map);
    buildEncodingMapHelper(node.right, code + "1", map);
}

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

public static String decode(String code, HuffmanNode root) {
    StringBuilder sb = new StringBuilder();
    HuffmanNode node = root;
    for (char c : code.toCharArray()) {
        node = c == '0' ? node.left : node.right;
        if (node.isLeaf()) {
            sb.append(node.c);
            node = root;
        }
    }
    return sb.toString();
}

最后，我们可以将上述方法组合在一起，实现完整的数据压缩算法：

public static String compress(String text) {
    HuffmanNode root = buildHuffmanTree(text);
    String code = encode(text, root);
    String header = buildHeader(root);
    return header + code;
}

public static String decompress(String compressedText) {
    String[] parts = compressedText.split(":", 2);
    HuffmanNode root = parseHeader(parts[0]);
    String code = parts[1];
    return decode(code, root);
}

private static String buildHeader(HuffmanNode root) {
    StringBuilder sb = new StringBuilder();
    buildHeaderHelper(root, sb);
    sb.append(":");
    return sb.toString();
}

private static void buildHeaderHelper(HuffmanNode node, StringBuilder sb) {
    if (node.isLeaf()) {
        sb.append(node.c);
        return;
    }
    sb.append("0");
    buildHeaderHelper(node.left, sb);
    sb.append("1");
    buildHeaderHelper(node.right, sb);
}

private static HuffmanNode parseHeader(String header) {
    Stack<HuffmanNode> stack = new Stack<>();
    HuffmanNode root = null;
    for (char c : header.toCharArray()) {
        if (c == '0') {
            HuffmanNode node = new HuffmanNode('\0', 0);
            if (!stack.isEmpty()) {
                HuffmanNode parent = stack.peek();
                if (parent.left == null) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
            stack.push(node);
        } else if (c == '1') {
            HuffmanNode right = stack.pop();
            HuffmanNode left = stack.pop();
            HuffmanNode parent = new HuffmanNode(left, right);
            if (stack.isEmpty()) {
                root = parent;
            } else {
                HuffmanNode grandParent = stack.peek();
                if (grandParent.left == left) {
                    grandParent.left = parent;
                } else {
                    grandParent.right = parent;
                }
            }
            stack.push(parent);
        } else {
            throw new IllegalArgumentException("Invalid header: " + header);
        }
    }
    if (stack.size() != 1) {
        throw new IllegalArgumentException("Invalid header: " + header);
    }
    return root;
}

这样，我们就实现了一个基于哈夫曼树的数据压缩算法。