java字符串压缩解压

在计算机科学中，字符串压缩是一种减少字符串占用空间的技术，它通过各种算法来减少字符的存储量。压缩后的字符串在需要使用时可以被解压回原始形式。这一技术对于处理大量文本数据尤其重要，比如在数据传输、存储优化等方面。然而，不同的压缩算法有着不同的压缩率、压缩速度和解压速度，因此在选择压缩算法时需要根据实际的应用场景进行权衡。

定义与目的

字符串压缩的目的在于减少数据的存储空间，提高数据传输的效率。它通常涉及到字符串的编码转换，将原始字符串转换成更短的表示形式。压缩算法的设计需要考虑压缩率（压缩后的数据大小与原始数据大小的比值）、压缩和解压的时间复杂度。

压缩算法的区别

目前存在多种字符串压缩算法，如Huffman编码、Run-Length Encoding (RLE)、Lempel-Ziv-Welch (LZW)等。每种算法都有其特定的应用场景和优缺点。例如，Huffman编码适合于字符出现频率差异较大的数据，而RLE适合于有大量重复字符的数据。

核心类与方法

在Java中，进行字符串压缩和解压通常会用到一些核心的类和方法。例如，可以使用StringBuilder来构建和修改字符串，使用BitSet来处理位级别的操作，以及利用一些集合类如HashMap、ArrayList来辅助算法的实现。

使用场景

字符串压缩和解压在许多场景下都有应用，如在网络传输中减少数据包的大小，或者在数据库存储中节省空间。此外，在某些文本编辑器中，也会使用压缩技术来提高文件的存储效率。

代码案例

以下是两个简单的字符串压缩和解压的Java代码案例。

案例1：使用Run-Length Encoding (RLE)

public class RLECompression {
    public static String compress(String input) {
        StringBuilder compressed = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            int count = 1;
            while (i + count < input.length() && input.charAt(i) == input.charAt(i + count)) {
                count++;
            }
            compressed.append(input.charAt(i)).append(count);
            i += count - 1;
        }
        return compressed.toString();
    }

    public static String decompress(String compressed) {
        StringBuilder decompressed = new StringBuilder();
        for (int i = 0; i < compressed.length(); ) {
            char character = compressed.charAt(i++);
            int count = Integer.parseInt(compressed.substring(i, i + count.length()));
            decompressed.append(String.valueOf(character).repeat(count));
            i += count.length();
        }
        return decompressed.toString();
    }

    public static void main(String[] args) {
        String original = "AAAABBBCCDAA";
        String compressed = compress(original);
        String decompressed = decompress(compressed);

        System.out.println("Original: " + original);
        System.out.println("Compressed: " + compressed);
        System.out.println("Decompressed: " + decompressed);
    }
}

案例2：使用Huffman编码

import java.util.*;

class HuffmanNode {
    char ch;
    int freq;
    HuffmanNode left, right;

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

public class HuffmanCoding {
    private static HashMap<Character, String> charToCode;

    private static void makeTree(String str) {
        HuffmanNode root = makeTree(str.toCharArray());
        makeCodes(root);
    }

    private static HuffmanNode makeTree(char data[]) {
        HuffmanNode nodes[] = new HuffmanNode[data.length];

        for (int i = 0; i < data.length; ++i) {
            nodes[i] = new HuffmanNode(data[i], 0);
        }

        for (int i = 0; i < data.length - 1; i++) {
            int min1 = i;
            int min2 = i + 1;
            for (int j = i + 1; j < data.length; j++) {
                if (nodes[min1].freq > nodes[j].freq)
                    min1 = j;
                if (nodes[min2].freq > nodes[j].freq && j != min1)
                    min2 = j;
            }
            HuffmanNode n1 = nodes[min1];
            HuffmanNode n2 = nodes[min2];

            HuffmanNode sum = new HuffmanNode('*', n1.freq + n2.freq);
            sum.left = n1;
            sum.right = n2;

            nodes[min1] = sum;
            if (min2 < data.length - 1) {
                nodes[min2] = nodes[data.length - 1];
            }
        }
        return nodes[data.length - 1];
    }

    private static void makeCodes(HuffmanNode root) {
        makeCodesUtil(root, "");
    }

    private static void makeCodesUtil(HuffmanNode root, String s) {
        if (root == null) {
            return;
        }
        if (root.ch != '\0') {
            charToCode.put(root.ch, s);
            return;
        }
        makeCodesUtil(root.left, s + "0");
        makeCodesUtil(root.right, s + "1");
    }

    public static String huffmanCode(String str) {
        charToCode = new HashMap<>();
        makeTree(str);
        StringBuilder sb = new StringBuilder();
        for (char c : str.toCharArray()) {
            sb.append(charToCode.get(c));
        }
        return sb.toString();
    }

    public static String huffmanDecode(String str, int n) {
        HuffmanNode root = makeTree(str.toCharArray());
        HuffmanNode temp = root;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                temp = temp.left;
            } else {
                temp = temp.right;
            }

            if (temp.left == null && temp.right == null) {
                sb.append(temp.ch);
                temp = root;
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String str = "THIS IS A SIMPLE EXAMPLE OF CHARACTER COMPRESSION";
        String compressed = huffmanCode(str);
        int n = str.length();
        String decompressed = huffmanDecode(compressed, n);

        System.out.println("Original String: " + str);
        System.out.println("Compressed String: " + compressed);
        System.out.println("Decompressed String: " + decompressed);
    }
}

表格补充

以下是对两种压缩算法的对比表格：

通过上述代码案例和表格对比，我们可以看到RLE算法简单且在处理大量重复字符时效率较高，而Huffman编码则提供了更高的压缩率，但实现相对复杂。选择合适的压缩算法需要根据具体的数据特性和应用需求来决定。