C语言实现短字符串压缩的三种方法详解

前言

短字符串压缩是一种常见的优化技术，可以减少字符串在内存中的占用空间，提高系统的性能和效率。本文将详解三种使用C语言实现短字符串压缩的方法：简单压缩、字典压缩和哈夫曼编码压缩。

一. 简单压缩

简单压缩是一种基本的字符串压缩方法，通过使用特殊字符表示连续重复的字符，从而减少字符串的长度。这种方法适用于有大量重复字符的字符串。

```c
#include 
#include 

void simpleCompress(char* str) {
    int len = strlen(str);
    if (len <= 1) {
        return;
    }
    
    char compressed[len];
    compressed[0] = str[0];
    int count = 1;
    
    for (int i = 1; i < len; i++) {
        if (str[i] == str[i-1]) {
            count++;
        } else {
            compressed[count++] = count + '0';
            compressed[count++] = str[i];
            count = 1;
        }
    }
    
    compressed[count++] = count + '0';
    compressed[count] = '\0';
    
    printf("Compressed string: %s\n", compressed);
}
```

上述代码中的simpleCompress函数实现了简单压缩的功能。它通过扫描原始字符串，统计连续重复字符的个数，并将其压缩成数字加字符的形式。例如，输入字符串"aaabbbccc"会被压缩成"a3b3c3"。

二. 字典压缩

字典压缩是一种更加高效的压缩方法，通过使用字典来存储已经出现过的字符串及其对应的索引，从而减少重复字符串的存储空间。这种方法适用于有大量重复字符串的情况。

```c
#include 
#include 
#include 

void dictionaryCompress(char* str) {
    int len = strlen(str);
    if (len <= 1) {
        return;
    }
    
    char** dictionary = malloc(len * sizeof(char*));
    int dictSize = 0;
    
    char compressed[len*2];
    int count = 1;
    
    for (int i = 1; i < len; i++) {
        int j;
        char* substr = malloc(len * sizeof(char));
        for (j = i-1; j < len; j++) {
            substr[j-i+1] = str[j];
            substr[j-i+2] = '\0';
            if (strstr(str, substr) == NULL) {
                break;
            }
        }
        
        if (j > i) {
            int index = -1;
            for (int k = 0; k < dictSize; k++) {
                if (strcmp(substr, dictionary[k]) == 0) {
                    index = k;
                    break;
                }
            }
            
            if (index == -1) {
                index = dictSize;
                dictionary[dictSize++] = strdup(substr);
            }
            
            compressed[count++] = index + '0';
            i += strlen(substr) - 1;
            free(substr);
        } else {
            compressed[count++] = str[i-1];
        }
    }
    
    compressed[count++] = str[len-1];
    compressed[count] = '\0';
    
    printf("Compressed string: %s\n", compressed);
}
```

上述代码中的dictionaryCompress函数实现了字典压缩的功能。它维护了一个字典来存储已经出现过的字符串，并通过索引来表示重复出现的字符串。例如，输入字符串"abcabcab"会被压缩成"abc2b1"。

三. 哈夫曼编码压缩

哈夫曼编码是一种无损压缩方法，适用于任意类型的数据。它通过构建一个最优二叉树来实现压缩，其中频率高的字符被赋予较短的编码。

```c
#include 
#include 
#include 

typedef struct TreeNode {
    char value;
    unsigned frequency;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void huffmanCompress(char* str) {
    int len = strlen(str);
    if (len <= 1) {
        return;
    }
    
    unsigned frequencies[256] = {0};
    
    for (int i = 0; i < len; i++) {
        frequencies[str[i]]++;
    }
    
    TreeNode** nodes = malloc(len * sizeof(TreeNode*));
    int nodeCount = 0;
    
    for (int i = 0; i < 256; i++) {
        if (frequencies[i] > 0) {
            TreeNode* node = malloc(sizeof(TreeNode));
            node->value = i;
            node->frequency = frequencies[i];
            node->left = NULL;
            node->right = NULL;
            nodes[nodeCount++] = node;
        }
    }
    
    while (nodeCount > 1) {
        TreeNode* minNode1 = nodes[0];
        TreeNode* minNode2 = nodes[1];
        int minIndex1 = 0;
        int minIndex2 = 1;
        
        for (int i = 2; i < nodeCount; i++) {
            if (nodes[i]->frequency < minNode1->frequency) {
                minNode2 = minNode1;
                minIndex2 = minIndex1;
                minNode1 = nodes[i];
                minIndex1 = i;
            } else if (nodes[i]->frequency < minNode2->frequency) {
                minNode2 = nodes[i];
                minIndex2 = i;
            }
        }
        
        TreeNode* combinedNode = malloc(sizeof(TreeNode));
        combinedNode->value = '\0';
        combinedNode->frequency = minNode1->frequency + minNode2->frequency;
        combinedNode->left = minNode1;
        combinedNode->right = minNode2;
        
        nodes[minIndex1] = combinedNode;
        nodes[minIndex2] = nodes[nodeCount-1];
        nodeCount--;
    }
    
    printf("Compressed string: ");
    printHuffmanCodes(nodes[0], "");
    printf("\n");
}

void printHuffmanCodes(TreeNode* root, char* prefix) {
    if (root == NULL) {
        return;
    }
    
    if (root->value != '\0') {
        printf("%s", prefix);
    }
    
    printHuffmanCodes(root->left, strcat(prefix, "0"));
    printHuffmanCodes(root->right, strcat(prefix, "1"));
}
```

上述代码中的huffmanCompress函数实现了哈夫曼编码压缩的功能。它首先统计字符串中各个字符的频率，然后构建哈夫曼树，并根据树的结构生成对应的编码。例如，输入字符串"aabbc"会被压缩成"01010111"。

总结

本文介绍了三种使用C语言实现短字符串压缩的方法：简单压缩、字典压缩和哈夫曼编码压缩。简单压缩通过表示连续重复字符的个数来减少字符串的长度，字典压缩通过使用索引来表示重复出现的字符串，哈夫曼编码压缩通过构建最优二叉树来实现无损压缩。根据实际需求和字符串特点，选择合适的压缩方法可以有效地优化程序的性能和效率。