常用字符串压缩方法

港控/mmm° 2024-03-16 16:38 28阅读 0赞

> 在编程开发过程中，常常为了提升空间资源利用率或者提升网络通讯速率需要将文本字符串进行压缩。

常用的字符串压缩方法有多种。下面列举了几种常见的方法：

**Run-Length Encoding (RLE)**

RLE 是一种基本的字符串压缩算法，它通过将连续出现的字符序列替换为一个字符和出现次数的组合来实现压缩。例如，字符串 "AAAABBBCCDAA" 可以被压缩为 "4A3B2C1D2A"。

以下是一个使用Java实现的Run-Length Encoding（RLE）示例代码：

public class RunLengthEncoding {
    
        public static String encode(String input) {
    
            StringBuilder encodedString = new StringBuilder();
    
            int count = 1;
    
            for (int i = 1; i <= input.length(); i++) {
    
                if (i == input.length() || input.charAt(i) != input.charAt(i - 1)) {
    
                    encodedString.append(count);
    
                    encodedString.append(input.charAt(i - 1));
    
                    count = 1;
    
                } else {
    
                    count++;
    
                }
    
            }
    
            return encodedString.toString();
    
        }
    
        public static String decode(String input) {
    
            StringBuilder decodedString = new StringBuilder();
    
            int count = 0;
    
            for (int i = 0; i < input.length(); i++) {
    
                char currentChar = input.charAt(i);
    
                if (Character.isDigit(currentChar)) {
    
                    count = count * 10 + Character.getNumericValue(currentChar);
    
                } else {
    
                    for (int j = 0; j < count; j++) {
    
                        decodedString.append(currentChar);
    
                    }
    
                    count = 0;
    
                }
    
            }
    
    
            return decodedString.toString();
    
        }
    
    
        public static void main(String[] args) {
    
            String originalString = "AAAABBBCCDAA";
    
            String encodedString = encode(originalString);
    
            String decodedString = decode(encodedString);
    
    
    
            System.out.println("Original String: " + originalString);
    
            System.out.println("Encoded String: " + encodedString);
    
            System.out.println("Decoded String: " + decodedString);
    
        }
    
    }

在上面的示例中，\`encode\`方法接受一个字符串作为输入，并返回其RLE编码后的字符串。\`decode\`方法接受一个RLE编码的字符串，并返回解码后的原始字符串。

在\`main\`方法中，我们使用示例字符串"AAAABBBCCDAA"进行测试。首先，我们对原始字符串进行编码并打印编码后的字符串，然后对编码后的字符串进行解码并打印解码后的字符串。输出如下：

> Original String: AAAABBBCCDAA
> 
> Encoded String: 4A3B2C1D2A
> 
> Decoded String: AAAABBBCCDAA

**Huffman 编码**

Huffman 编码是一种基于字符频率的压缩算法。它使用变长编码来表示不同的字符，使频率较高的字符使用较短的编码，频率较低的字符使用较长的编码。这样可以实现对整个字符串的有效压缩。

Huffman压缩的原理如下：

1.  统计输入数据中每个字符的出现频率。
2.  将每个字符作为叶节点，构建一棵Huffman树。树的每个节点都有一个权重，对于叶节点来说，权重就是其对应字符的频率。
3.  从根节点开始，沿着左子树为0，右子树为1的路径，为每个叶节点生成对应的编码。编码是从根节点到叶节点的路径上的0和1序列。
4.  使用生成的编码，对输入数据进行编码，将每个字符替换为其对应的编码。
5.  将编码后的数据存储或传输。

压缩过程中，Huffman编码保证了没有编码是其他编码的前缀，这被称为前缀码。这意味着在解压缩时，编码可以被唯一地解码回原始字符。

解压缩过程如下：

1.  使用相同的Huffman编码表，将编码后的数据转换为二进制序列。
2.  从根节点开始，依次读取每个二进制位。如果是0，向左子节点移动；如果是1，向右子节点移动。
3.  当到达叶节点时，将对应的字符输出，并返回根节点。
4.  重复步骤2和3，直到读取完所有的二进制位。

以下是一个使用Java实现Huffman编码的示例代码：

package cn.buglife.learn.compress;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.PriorityQueue;
    
    class HuffmanNode implements Comparable<HuffmanNode> {
        char character;
        int frequency;
        HuffmanNode leftChild;
        HuffmanNode rightChild;
    
        public HuffmanNode(char character, int frequency) {
            this.character = character;
            this.frequency = frequency;
        }
    
        public boolean isLeaf() {
            return leftChild == null && rightChild == null;
        }
    
        @Override
        public int compareTo(HuffmanNode other) {
            return this.frequency - other.frequency;
        }
    }
    
    public class HuffmanCompression {
        private static Map<Character, String> encodingTable;
        private static HuffmanNode root;
    
        public static String compress(String input) {
            // 计算字符频率
            Map<Character, Integer> frequencyMap = calculateFrequency(input);
    
            // 构建Huffman树
            buildHuffmanTree(frequencyMap);
    
            // 生成字符编码表
            encodingTable = new HashMap<>();
            buildEncodingTable(root, "");
    
            // 压缩输入字符串
            StringBuilder compressed = new StringBuilder();
            for (char c : input.toCharArray()) {
                compressed.append(encodingTable.get(c));
            }
    
            return compressed.toString();
        }
    
        public static String decompress(String compressed) {
            StringBuilder decompressed = new StringBuilder();
            HuffmanNode currentNode = root;
    
            // 解压缩字符串
            for (char bit : compressed.toCharArray()) {
                if (bit == '0') {
                    currentNode = currentNode.leftChild;
                } else if (bit == '1') {
                    currentNode = currentNode.rightChild;
                }
    
                if (currentNode.isLeaf()) {
                    decompressed.append(currentNode.character);
                    currentNode = root;
                }
            }
    
            return decompressed.toString();
        }
    
        private static Map<Character, Integer> calculateFrequency(String input) {
            Map<Character, Integer> frequencyMap = new HashMap<>();
    
            for (char c : input.toCharArray()) {
                frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
            }
    
            return frequencyMap;
        }
    
        private static void buildHuffmanTree(Map<Character, Integer> frequencyMap) {
            PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
    
            // 创建叶节点
            for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
                HuffmanNode node = new HuffmanNode(entry.getKey(), entry.getValue());
                priorityQueue.offer(node);
            }
    
            // 构建Huffman树
            while (priorityQueue.size() > 1) {
                HuffmanNode leftChild = priorityQueue.poll();
                HuffmanNode rightChild = priorityQueue.poll();
    
                HuffmanNode parentNode = new HuffmanNode('\0', leftChild.frequency + rightChild.frequency);
                parentNode.leftChild = leftChild;
                parentNode.rightChild = rightChild;
    
                priorityQueue.offer(parentNode);
            }
    
            // 设置根节点
            root = priorityQueue.poll();
        }
    
        private static void buildEncodingTable(HuffmanNode node, String code) {
            if (node.isLeaf()) {
                encodingTable.put(node.character, code);
                return;
            }
    
            buildEncodingTable(node.leftChild, code + "0");
            buildEncodingTable(node.rightChild, code + "1");
        }
    
        public static void main(String[] args) {
            String original = "HELLO, 不爱运动的跑者!";
            System.out.println("Original: " + original);
    
            String compressed = compress(original);
            System.out.println("Compressed: " + compressed);
    
            String decompressed = decompress(compressed);
            System.out.println("DECompressed: " + decompressed);
        }
    }

这个示例代码实现了Huffman编码的构建和编码/解码功能。

**Lempel-Ziv-Welch (LZW) 压缩**

LZW 是一种无损的字典压缩算法，广泛应用于各种文件压缩格式中，如GIF、TIFF等。它通过构建一个字典来存储出现的字符串，并将字符串替换为字典中对应的索引值。这样可以实现对重复出现的字符串的压缩。

下面是一个Java实现Lempel-Ziv-Welch（LZW）压缩算法的示例代码：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class LZWCompression {
        public static String compress(String input) {
            Map<String, Integer> dictionary = new HashMap<>();
    
            // 初始化字典
            for (int i = 0; i < 256; i++) {
                dictionary.put(String.valueOf((char) i), i);
            }
    
            StringBuilder compressed = new StringBuilder();
            String current = "";
            for (char c : input.toCharArray()) {
                String currentPlusC = current + c;
                if (dictionary.containsKey(currentPlusC)) {
                    current = currentPlusC;
                } else {
                    compressed.append(dictionary.get(current)).append(" ");
                    dictionary.put(currentPlusC, dictionary.size());
                    current = String.valueOf(c);
                }
            }
    
            if (!current.equals("")) {
                compressed.append(dictionary.get(current)).append(" ");
            }
    
            return compressed.toString();
        }
    
        public static String decompress(String input) {
            Map<Integer, String> dictionary = new HashMap<>();
    
            // 初始化字典
            for (int i = 0; i < 256; i++) {
                dictionary.put(i, String.valueOf((char) i));
            }
    
            String[] compressedArray = input.trim().split(" ");
            List<String> compressedList = new ArrayList<>();
            for (String s : compressedArray) {
                compressedList.add(s);
            }
    
            StringBuilder decompressed = new StringBuilder();
            int previousCode = Integer.parseInt(compressedList.get(0));
            decompressed.append(dictionary.get(previousCode));
            String current = dictionary.get(previousCode);
            for (int i = 1; i < compressedList.size(); i++) {
                int currentCode = Integer.parseInt(compressedList.get(i));
                String entry;
                if (dictionary.containsKey(currentCode)) {
                    entry = dictionary.get(currentCode);
                } else if (currentCode == dictionary.size()) {
                    entry = current + current.charAt(0);
                } else {
                    throw new IllegalArgumentException("Invalid compressed input");
                }
    
                decompressed.append(entry);
                dictionary.put(dictionary.size(), current + entry.charAt(0));
                current = entry;
            }
    
            return decompressed.toString();
        }
    
        public static void main(String[] args) {
            String original = "TOBEORNOTTOBEORTOBEORNOT2121";
            System.out.println("Original: " + original);
    
            String compressed = compress(original);
            System.out.println("Compressed: " + compressed);
    
            String decompressed = decompress(compressed);
            System.out.println("Decompressed: " + decompressed);
        }
    }

这个代码使用了一个字典来跟踪已经出现的字符串，并为它们分配唯一的编码。在压缩过程中，我们从输入字符串中读取字符，然后构建当前字符串（current）加上读取的字符（c）。如果当前字符串加上字符存在于字典中，则继续向后读取字符并更新当前字符串。如果当前字符串加上字符不在字典中，则将当前字符串的编码添加到结果列表中，并将当前字符串加上字符添加到字典中，并为它分配一个新的编码。

在上面的示例中，我们使用了一个简单的字符串作为输入，并打印了压缩后的结果。可以根据自己的需要修改输入字符串，并对结果进行进一步的处理和存储。

**进制转换**

进制转换可以被视为一种对数字型字符串的压缩方法。当你将一个数字从一种进制转换为另一种进制时，可以使用更少的字符来表示相同的数值。例如，假设有一个十进制数值 255，如果将其转换为二进制，可以用字符串 "11111111" 表示。相比于十进制表示需要三个字符（"255"），二进制表示只需要八个字符，因此可以说它对数字型字符串进行了一定程度的压缩。同样地，可以将数字从其他进制转换为十进制，或者将十进制转换为其他进制。每种进制的表示方法都有其优点和局限性，具体取决于使用场景和需求。

例如下面是使用Java实现的十进制数字字符串与62进制相互转化以达到数字字符串压缩和解压缩的目的：

import java.util.HashMap;
    import java.util.Map;
    
    public class NumberCompression {
        private static final String CHARACTERS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
        private static final int BASE = CHARACTERS.length();
    
        // 十进制数字字符串转换为62进制
        public static String decimalTo62(String number) {
            long decimal = Long.parseLong(number);
            StringBuilder sb = new StringBuilder();
    
            while (decimal > 0) {
                int index = (int) (decimal % BASE);
                sb.append(CHARACTERS.charAt(index));
                decimal /= BASE;
            }
    
            return sb.reverse().toString();
        }
    
        // 62进制转换为十进制数字字符串
        public static String base62ToDecimal(String number) {
            long decimal = 0;
            int length = number.length();
    
            for (int i = 0; i < length; i++) {
                int digit = CHARACTERS.indexOf(number.charAt(i));
                decimal += digit * Math.pow(BASE, length - i - 1);
            }
    
            return String.valueOf(decimal);
        }
    
        
    
        // 测试压缩和解压缩
        public static void main(String[] args) {
            String number = "123456789000"; // 要压缩的数字字符串
            System.out.println("原始数字字符串: " + number);
    
            // 十进制转换为62进制
            String base62 = decimalTo62(number);
            System.out.println("62进制表示: " + base62);
    
            // 62进制转换为十进制
            String decimal = base62ToDecimal(base62);
            System.out.println("还原的数字字符串: " + decimal);
        }
    }

### 如何科学选择压缩方法 ###

选择压缩算法需要考虑多个因素，包括以下几个方面：

1.  压缩效率：不同算法对不同类型的数据具有不同的压缩效率。一些算法在特定类型的数据上表现优秀，而在其他类型的数据上可能效果较差。因此，要根据具体的数据类型和数据分布来选择最适合的算法。
2.  压缩速度：有些算法可能具有较高的压缩效率，但压缩和解压缩的速度较慢。如果需要快速的压缩和解压缩速度，可以选择具有较低复杂度的算法，如Run-Length Encoding (RLE)。
3.  内存消耗：某些算法可能需要较大的内存空间来执行压缩和解压缩操作，特别是在处理大型数据集时。如果内存资源有限，可以选择消耗较少内存的算法。
4.  数据完整性：一些压缩算法可能会引入数据损失，导致解压缩后的数据与原始数据不完全一致。这在某些场景下可能是可以接受的，但在其他场景下可能是不可接受的。根据数据的重要性和对数据完整性的需求，选择适当的算法。

基于上面这些因素考虑，选择压缩方法时可以参考这么几点建议：

*  如果数据具有大量重复连续的字符或重复的字节序列，可以考虑使用Run-Length Encoding (RLE)算法，因为它对连续重复的数据具有很好的压缩效果。
 *  如果数据具有统计规律的分布，Huffman编码可以提供较好的压缩效果。Huffman编码适用于符号频率不同的情况。
 *  对于通用数据压缩，Lempel-Ziv-Welch (LZW)算法是一种常用且有效的选择。它适用于多种类型的数据，并且在压缩效率和速度之间取得了良好的平衡。
 *  数字进制转换算法适用于将十进制数字字符串转换为其他进制表示，通常用于短字符串的压缩。