C語言字符串中的Lempel-Ziv壓縮

Lempel-Ziv（LZ77、LZ78、LZW等）是一種廣泛應用于數據壓縮的無損壓縮算法

以下是一個簡單的LZ77壓縮算法實現：

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

typedef struct {
    int offset;
    int length;
    char next_char;
} LZ77_code;

void lz77_compress(const char *input, LZ77_code **output, int *output_size) {
    int input_length = strlen(input);
    *output_size = 0;
    *output = (LZ77_code *)malloc(input_length * sizeof(LZ77_code));

    for (int i = 0; i< input_length; ++i) {
        int max_length = 0;
        int best_offset = 0;

        for (int j = 0; j < i; ++j) {
            int current_length = 0;

            while (current_length + i< input_length && input[j + current_length] == input[i + current_length]) {
                current_length++;
            }

            if (current_length > max_length) {
                max_length = current_length;
                best_offset = i - j;
            }
        }

        (*output)[*output_size].offset = best_offset;
        (*output)[*output_size].length = max_length;
        (*output)[*output_size].next_char = input[i + max_length];
        (*output_size)++;

        i += max_length;
    }
}

int main() {
    const char *input = "ABABABA";
    LZ77_code *output;
    int output_size;

    lz77_compress(input, &output, &output_size);

    printf("Input: %s\n", input);
    printf("Output:\n");
    for (int i = 0; i< output_size; ++i) {
        printf("(%d, %d, %c)\n", output[i].offset, output[i].length, output[i].next_char);
    }

    free(output);
    return 0;
}

這個程序首先定義了一個結構體LZ77_code，用于存儲LZ77壓縮后的數據。然后，lz77_compress函數接受一個輸入字符串和兩個指針，分別用于存儲輸出數據和輸出數據的大小。在主函數中，我們調用lz77_compress函數對輸入字符串進行壓縮，并打印輸出結果。

請注意，這個示例僅用于演示目的，實際應用中可能需要考慮更多的優化和錯誤處理。