ChatGPT 问答00021 java 对字符串进行高度压缩的算法

Java中对字符串进行高度压缩的算法有很多种，下面我介绍两种常见的方法。

1. Run-Length Encoding (RLE) 算法
   RLE算法是一种简单且高效的字符串压缩算法。它通过将连续重复的字符序列替换为一个字符和其重复次数的表示来实现压缩。

示例代码如下：

public static String compressString(String input) {
    StringBuilder compressed = new StringBuilder();
    int count = 1;
    
    for (int i = 0; i < input.length(); i++) {
        if (i + 1 < input.length() && input.charAt(i) == input.charAt(i + 1)) {
            count++;
        } else {
            compressed.append(input.charAt(i));
            compressed.append(count);
            count = 1;
        }
    }
    
    return compressed.toString();
}

2. Huffman 编码算法
   Huffman编码是一种基于字符出现频率的无损压缩算法。它通过构建字符集的最优二叉树来实现压缩，出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码。

示例代码如下：

import java.util.HashMap;
import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    char character;
    int frequency;
    Node left, right;

    public Node(char character, int frequency, Node left, Node right) {
        this.character = character;
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }

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

    @Override
    public int compareTo(Node node) {
        return frequency - node.frequency;
    }
}

public class HuffmanCompression {
    public static String compressString(String input) {
        HashMap<Character, Integer> frequencyMap = new HashMap<>();
        
        // 统计字符出现的频率
        for (char c : input.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        
        // 构建优先队列
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (char c : frequencyMap.keySet()) {
            queue.offer(new Node(c, frequencyMap.get(c), null, null));
        }
        
        // 构建Huffman树
        while (queue.size() > 1) {
            Node left = queue.poll();
            Node right = queue.poll();
            Node parent = new Node('\0', left.frequency + right.frequency, left, right);
            queue.offer(parent);
        }
        
        // 构建编码表
        HashMap<Character, String> encodingMap = new HashMap<>();
        buildEncodingMap(queue.peek(), "", encodingMap);
        
        // 压缩字符串
        StringBuilder compressed = new StringBuilder();
        for (char c : input.toCharArray()) {
            compressed.append(encodingMap.get(c));
        }
        
        return compressed.toString();
    }
    
    private static void buildEncodingMap(Node node, String code, HashMap<Character, String> encodingMap) {
        if (node.isLeaf()) {
            encodingMap.put(node.character, code);
        } else {
            buildEncodingMap(node.left, code + "0", encodingMap);
            buildEncodingMap(node.right, code + "1", encodingMap);
        }
    }
}

这些算法只是简单的示例，实际应用中需要根据具体情况进行调整和优化。另外，请注意对于较短的字符串，压缩可能导致更大的存储空间占用，因此在实际应用中需要综合考虑压缩和解压缩的开销以及数据规模等因素。