c语言实现lz77压缩与解压

以下是 C 语言实现 LZ77 压缩与解压的简单示例代码，仅供参考：

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

#define MAX_WINDOW_SIZE 4096
#define MAX_LOOKAHEAD_SIZE 18
#define MIN_MATCH_LENGTH 3

typedef struct {
    int position;
    int length;
    char next;
} Match;

void compress(unsigned char* input, int input_size, unsigned char* output, int* output_size) {
    int i, j, k, pos, len, lookahead_size, window_size;
    unsigned char* window, *lookahead;
    Match match, best_match;

    window_size = MAX_WINDOW_SIZE;
    lookahead_size = MAX_LOOKAHEAD_SIZE;
    window = (unsigned char*)malloc(window_size);
    lookahead = (unsigned char*)malloc(lookahead_size);
    memset(window, ' ', window_size);
    memcpy(lookahead, input, lookahead_size);

    *output_size = 0;
    pos = 0;
    while (pos < input_size) {
        best_match.position = 0;
        best_match.length = 0;
        for (i = 0; i < lookahead_size; i++) {
            match.position = 0;
            match.length = 0;
            for (j = 0, k = i; j < window_size && k < lookahead_size; j++, k++) {
                if (window[j] != lookahead[k]) {
                    break;
                }
                match.length++;
                match.position = j;
            }
            if (match.length > best_match.length) {
                best_match = match;
            }
        }
        if (best_match.length >= MIN_MATCH_LENGTH) {
            output[(*output_size)++] = best_match.position;
            output[(*output_size)++] = (best_match.position >> 4) | ((best_match.length - MIN_MATCH_LENGTH) << 4);
            lookahead_size = best_match.length;
        } else {
            output[(*output_size)++] = lookahead[0];
            lookahead_size = 1;
        }
        memmove(window, window + lookahead_size, window_size - lookahead_size);
        memcpy(window + window_size - lookahead_size, lookahead, lookahead_size);
        memmove(lookahead, lookahead + lookahead_size, MAX_LOOKAHEAD_SIZE - lookahead_size);
        if (pos + MAX_LOOKAHEAD_SIZE < input_size) {
            memcpy(lookahead + lookahead_size, input + pos + lookahead_size, MAX_LOOKAHEAD_SIZE - lookahead_size);
        } else {
            memcpy(lookahead + lookahead_size, input + pos + lookahead_size, input_size - pos - lookahead_size);
            lookahead_size = input_size - pos - lookahead_size;
        }
        pos += lookahead_size;
    }

    free(window);
    free(lookahead);
}

void decompress(unsigned char* input, int input_size, unsigned char* output, int* output_size) {
    int i, j, pos, len;
    unsigned char* window;
    Match match;

    window = (unsigned char*)malloc(MAX_WINDOW_SIZE);
    memset(window, ' ', MAX_WINDOW_SIZE);

    *output_size = 0;
    pos = 0;
    while (pos < input_size) {
        if (input[pos] == 0 && pos + 1 < input_size) {
            output[(*output_size)++] = input[++pos];
        } else if (input[pos] > 0 && input[pos] <= MAX_WINDOW_SIZE && pos + 1 < input_size) {
            match.position = input[pos] - 1;
            match.length = (input[pos + 1] >> 4) + MIN_MATCH_LENGTH;
            len = match.length;
            for (i = 0, j = match.position; i < len; i++, j++) {
                if (j >= *output_size) {
                    break;
                }
                match.next = output[j];
                output[(*output_size)++] = match.next;
                window[i] = match.next;
            }
            pos += 2;
        }
    }

    free(window);
}

int main() {
    unsigned char input[] = "Hello, world! This is a test string.";
    int input_size = sizeof(input) - 1;
    unsigned char compressed[1024], decompressed[1024];
    int compressed_size, decompressed_size;

    compress(input, input_size, compressed, &compressed_size);
    decompress(compressed, compressed_size, decompressed, &decompressed_size);

    printf("Original: %s\n", input);
    printf("Compressed: ");
    for (int i = 0; i < compressed_size; i++) {
        printf("%02X ", compressed[i]);
    }
    printf("\n");
    printf("Decompressed: %s\n", decompressed);

    return 0;
}

该示例代码实现了 LZ77 压缩和解压，其中 `compress` 函数接受输入数据和输入数据大小，并输出压缩后的数据和压缩后的数据大小；`decompress` 函数接受压缩后的数据和压缩后的数据大小，并输出解压后的数据和解压后的数据大小。