[C言語] Huffman法によるデータ圧縮の実装方法

typedef struct Node {
    char symbol; // シンボル
    int frequency; // 出現頻度
    struct Node *left; // 左の子ノード
    struct Node *right; // 右の子ノード
} Node;

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

#define MAX_TREE_HT 256

// ノード構造体の定義
typedef struct Node {
    char symbol;
    int frequency;
    struct Node* left;
    struct Node* right;
} Node;

// 最小ヒープ構造体の定義
typedef struct MinHeap {
    int size;
    int capacity;
    Node** array;
} MinHeap;

// ノードの作成関数
Node* createNode(char symbol, int frequency) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->symbol = symbol;
    node->frequency = frequency;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 最小ヒープの作成関数
MinHeap* createMinHeap(int capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (Node**)malloc(minHeap->capacity * sizeof(Node*));
    return minHeap;
}

// ノードを交換する関数
void swapNode(Node** a, Node** b) {
    Node* t = *a;
    *a = *b;
    *b = t;
}

// ヒープ化する関数
void minHeapify(MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < minHeap->size &&
        minHeap->array[left]->frequency < minHeap->array[smallest]->frequency)
        smallest = left;

    if (right < minHeap->size &&
        minHeap->array[right]->frequency < minHeap->array[smallest]->frequency)
        smallest = right;

    if (smallest != idx) {
        swapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

// 最小ヒープから最小のノードを取り出す関数
Node* extractMin(MinHeap* minHeap) {
    Node* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

// 最小ヒープにノードを挿入する関数
void insertMinHeap(MinHeap* minHeap, Node* node) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && node->frequency < minHeap->array[(i - 1) / 2]->frequency) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = node;
}

// 最小ヒープを構築する関数
void buildMinHeap(MinHeap* minHeap) {
    int n = minHeap->size - 1;
    for (int i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i);
}

// 最小ヒープを作成する関数
MinHeap* createAndBuildMinHeap(char symbols[], int frequency[], int size) {
    MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = createNode(symbols[i], frequency[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

// Huffman木を構築する関数
Node* buildHuffmanTree(char symbols[], int frequency[], int size) {
    Node *left, *right, *top;
    MinHeap* minHeap = createAndBuildMinHeap(symbols, frequency, size);

    while (minHeap->size != 1) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);

        top = createNode('$', left->frequency + right->frequency);
        top->left = left;
        top->right = right;

        insertMinHeap(minHeap, top);
    }

    return extractMin(minHeap);
}

// Huffmanコードを生成する関数
void printCodes(Node* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }

    if (!(root->left) && !(root->right)) {
        printf("%c: ", root->symbol);
        for (int i = 0; i < top; ++i) printf("%d", arr[i]);
        printf("\n");
    }
}

// Huffmanコードを取得する関数
void getCodes(Node* root, int arr[], int top, char codes[][MAX_TREE_HT],
              char symbols[], int* index) {
    if (root->left) {
        arr[top] = 0;
        getCodes(root->left, arr, top + 1, codes, symbols, index);
    }

    if (root->right) {
        arr[top] = 1;
        getCodes(root->right, arr, top + 1, codes, symbols, index);
    }

    if (!(root->left) && !(root->right)) {
        symbols[*index] = root->symbol;
        for (int i = 0; i < top; ++i) {
            codes[*index][i] = arr[i] + '0';
        }
        codes[*index][top] = '\0';
        (*index)++;
    }
}

// データをエンコードする関数
void encodeData(const char* data, char codes[][MAX_TREE_HT], char symbols[],
                char* encodedData) {
    int i, j;
    for (i = 0; data[i] != '\0'; i++) {
        for (j = 0; symbols[j] != '\0'; j++) {
            if (data[i] == symbols[j]) {
                strcat(encodedData, codes[j]);
                break;
            }
        }
    }
}

// データをデコードする関数
void decodeData(Node* root, const char* encodedData, char* decodedData) {
    Node* current = root;
    int i, j = 0;
    for (i = 0; encodedData[i] != '\0'; i++) {
        if (encodedData[i] == '0')
            current = current->left;
        else
            current = current->right;

        if (!(current->left) && !(current->right)) {
            decodedData[j++] = current->symbol;
            current = root;
        }
    }
    decodedData[j] = '\0';
}

int main() {
    const char* data = "Hello World! 日本語もちゃんとエンコードできる";
    int frequency[256] = {0};
    char symbols[256];
    char codes[256][MAX_TREE_HT];
    int arr[MAX_TREE_HT], top = 0;
    int index = 0;

    // 出現頻度の計算
    for (int i = 0; data[i] != '\0'; i++) {
        frequency[(unsigned char)data[i]]++;
    }

    // シンボルと頻度の配列を作成
    int size = 0;
    for (int i = 0; i < 256; i++) {
        if (frequency[i] > 0) {
            symbols[size] = (char)i;
            frequency[size] = frequency[i];
            size++;
        }
    }

    // Huffman木の構築
    Node* root = buildHuffmanTree(symbols, frequency, size);

    // Huffmanコードの生成
    getCodes(root, arr, top, codes, symbols, &index);

    // 元のテキスト
    printf("Original Data: %s\n", data);
    printf("Data Length: %d\n", (int)strlen(data));

    // エンコード
    char encodedData[1024] = "";
    encodeData(data, codes, symbols, encodedData);
    printf("Encoded Data: %s\n", encodedData);
    printf("Encoded Data Length: %d\n", (int)strlen(encodedData) / 8);

    // 圧縮率
    printf("Compression Ratio: %.2f%%\n",
           (float)strlen(encodedData) / 8 / strlen(data) * 100);

    // デコード
    char decodedData[1024];
    decodeData(root, encodedData, decodedData);
    printf("Decoded Data: %s\n", decodedData);

    return 0;
}

Original Data: Hello World! 日本語もちゃんとエンコードできる
Data Length: 45
Encoded Data: 1110011011011001100100111111100100001110101010011111010100011111100001001111011010101010011111001101011101100001111010100011011100011000101011000010111000011101111010111010110111110101100000011000010110101100
Encoded Data Length: 26
Compression Ratio: 57.78%
Decoded Data: Hello World! 日本語もちゃんとエンコードできる