LZW算法在C++中实现

LZW算法是一种无损压缩算法，可以将重复出现的字符串替换为较短的编码，并且可以实现高压缩比。以下是在C语言中实现LZW算法的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 4096 // 编码表大小

typedef unsigned short code_t; // 编码类型

// 初始化编码表
void init_table(char **table)
{
    for (int i = 0; i < 256; i++) {
        table[i] = (char *)malloc(2 * sizeof(char));
        table[i][0] = (char)i;
        table[i][1] = '\0';
    }
    for (int i = 256; i < TABLE_SIZE; i++) {
        table[i] = NULL;
    }
}

// 查找字符串在编码表中的位置
int find_string(char **table, char *str)
{
    int i = 0;
    while (table[i] != NULL) {
        if (strcmp(table[i], str) == 0) {
            return i;
        }
        i++;
    }
    return -1;
}

// 将字符串插入编码表中
int insert_string(char **table, char *str)
{
    int i = 0;
    while (table[i] != NULL) {
        i++;
    }
    if (i < TABLE_SIZE) {
        table[i] = (char *)malloc((strlen(str) + 1) * sizeof(char));
        strcpy(table[i], str);
    }
    return i;
}

// LZW压缩函数
int lzw_compress(char *input, code_t *output)
{
    char **table = (char **)malloc(TABLE_SIZE * sizeof(char *));
    init_table(table);

    int input_len = strlen(input);
    char string[256];
    int string_len = 0;
    int code = 0;
    int output_len = 0;

    for (int i = 0; i < input_len; i++) {
        string[string_len++] = input[i];
        string[string_len] = '\0';
        int index = find_string(table, string);
        if (index == -1) {
            output[output_len++] = code;
            code = insert_string(table, string);
            string_len = 1;
            string[0] = input[i];
            string[1] = '\0';
        } else {
            code = index;
        }
    }
    output[output_len++] = code;

    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table[i] != NULL) {
            free(table[i]);
        }
    }
    free(table);

    return output_len;
}

// LZW解压函数
int lzw_decompress(code_t *input, int input_len, char *output)
{
    char **table = (char **)malloc(TABLE_SIZE * sizeof(char *));
    init_table(table);

    int output_len = 0;
    int code = input[0];
    char *string = table[code];
    int string_len = strlen(string);
    strcpy(output, string);
    output_len += string_len;

    for (int i = 1; i < input_len; i++) {
        code = input[i];
        if (table[code] == NULL) {
            string = table[i];
            string_len = strlen(string);
            strcat(output, string);
            output_len += string_len;
            table[code] = (char *)malloc((string_len + 1) * sizeof(char));
            strcpy(table[code], string);
        } else {
            string = table[code];
            string_len = strlen(string);
            strcat(output, string);
            output_len += string_len;
            char *prev_string = table[input[i - 1]];
            int prev_string_len = strlen(prev_string);
            char new_string[256];
            strcpy(new_string, prev_string);
            new_string[prev_string_len] = string[0];
            new_string[prev_string_len + 1] = '\0';
            table[TABLE_SIZE++] = (char *)malloc((strlen(new_string) + 1) * sizeof(char));
            strcpy(table[TABLE_SIZE - 1], new_string);
        }
    }

    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table[i] != NULL) {
            free(table[i]);
        }
    }
    free(table);

    return output_len;
}

int main()
{
    char input[256] = "ababababab";
    code_t output[256];
    int output_len = lzw_compress(input, output);
    char decompressed[256];
    int decompressed_len = lzw_decompress(output, output_len, decompressed);
    printf("Input: %s\n", input);
    printf("Output: ");
    for (int i = 0; i < output_len; i++) {
        printf("%d ", output[i]);
    }
    printf("\nDecompressed: %s\n", decompressed);
    return 0;
}

在此示例代码中，使用一个字符串数组作为编码表，并按字典序初始化前256个编码。在压缩过程中，先将第一个字符加入当前字符串，然后在编码表中查找是否有相同的字符串，若有则继续添加下一个字符，否则将当前字符串编码并加入编码序列中，然后将当前字符串重置为当前字符。在解压过程中，先将第一个编码对应的字符串加入输出中，然后按照编码序列逐个解码，若当前编码在编码表中不存在，则将前一个编码对应的字符串加上当前字符串的第一个字符，并添加到编码表中，然后将当前编码对应的字符串加入输出中。若当前编码在编码表中存在，则将其对应的字符串加入输出中。