MENU
  1. ホーム
  2. C言語
  3. プログラム
  4. アルゴリズム
  5. [C言語] Huffman法によるデータ圧縮の実装方法

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

アルゴリズム

Huffman法は、データ圧縮のための可変長符号化手法です。

C言語での実装は、まずデータの各シンボルの出現頻度を計算し、これを基に最小ヒープを用いてHuffman木を構築します。

次に、木をトラバースして各シンボルに対するHuffmanコードを生成します。

これにより、頻度の高いシンボルには短いコードが、頻度の低いシンボルには長いコードが割り当てられ、全体のデータサイズが縮小されます。

圧縮後は、生成したHuffmanコードを用いてデータをエンコードし、圧縮ファイルを作成します。

デコード時には、Huffman木を再構築し、エンコードされたデータを元のシンボル列に復元します。

この記事でわかること
  • Huffman法の基本原理とその利点
  • Huffman木の構築方法とその重要性
  • データのエンコードとデコードの手順
  • C言語でのHuffman法の実装例
  • Huffman法の応用例とその効果

目次から探す

Huffman法の概要

Huffman法とは

Huffman法は、データ圧縮のためのアルゴリズムの一つで、特に可変長符号化を用いることで効率的にデータを圧縮します。

このアルゴリズムは、1952年にデビッド・ハフマンによって考案されました。

Huffman法は、データ内の各シンボルの出現頻度に基づいて、短いビット列を頻繁に出現するシンボルに割り当て、長いビット列を稀に出現するシンボルに割り当てることで、全体のデータサイズを削減します。

データ圧縮の基本原理

データ圧縮の基本原理は、情報の冗長性を削減することにあります。

Huffman法では、以下の手順でデータを圧縮します。

  1. シンボルの出現頻度を計算: データ内の各シンボルの出現頻度を計算します。
  2. Huffman木の構築: 出現頻度に基づいてHuffman木を構築します。

頻度の低いシンボルほど木の深い位置に配置されます。

  1. 符号の割り当て: Huffman木をトラバースし、各シンボルに対して可変長のビット列を割り当てます。

このようにして、データ全体のビット数を削減し、圧縮を実現します。

可変長符号化の利点

可変長符号化の最大の利点は、データの圧縮効率を高めることです。

以下にその利点を示します。

  • 効率的な圧縮: 頻繁に出現するシンボルに短い符号を割り当てることで、全体のデータサイズを削減します。
  • 柔軟性: データの特性に応じて符号長を調整できるため、さまざまなデータ形式に適用可能です。
  • 情報の損失がない: Huffman法は可逆圧縮アルゴリズムであり、圧縮前のデータを完全に復元できます。

このように、可変長符号化はデータ圧縮において非常に有用な手法です。

Huffman木の構築

シンボルの出現頻度の計算

Huffman法の最初のステップは、データ内の各シンボルの出現頻度を計算することです。

これにより、どのシンボルがどの程度頻繁に現れるかを把握し、効率的な符号化を行うための基礎を築きます。

出現頻度の計算は、通常、以下の手順で行います。

  • データを1文字ずつ読み込み、各シンボルの出現回数をカウントします。
  • カウントした出現回数を基に、各シンボルの出現頻度を算出します。

この情報は、後のHuffman木の構築において重要な役割を果たします。

最小ヒープの利用

Huffman木の構築には、最小ヒープ(優先度キュー)を利用します。

最小ヒープは、常に最小の要素を効率的に取り出すことができるデータ構造で、Huffman法においては以下のように使用されます。

  • 各シンボルとその出現頻度をノードとして最小ヒープに挿入します。
  • ヒープから最小の2つのノードを取り出し、新しいノードを作成します。

この新しいノードの頻度は、取り出した2つのノードの頻度の合計です。

  • 新しいノードをヒープに挿入し、これをヒープが1つのノードになるまで繰り返します。

このプロセスにより、Huffman木の基礎が形成されます。

Huffman木の生成手順

Huffman木の生成は、以下の手順で行われます。

  1. 初期化: 各シンボルとその出現頻度をノードとして最小ヒープに挿入します。
  2. ノードの結合: ヒープから最小の2つのノードを取り出し、それらを子ノードとして持つ新しい親ノードを作成します。

この親ノードの頻度は、子ノードの頻度の合計です。

  1. ヒープへの再挿入: 新しい親ノードをヒープに挿入します。
  2. 繰り返し: ヒープが1つのノードになるまで、ノードの結合と再挿入を繰り返します。

最終的に、ヒープに残った1つのノードがHuffman木のルートノードとなり、これによりHuffman木が完成します。

この木を用いて、各シンボルに対する可変長のビット列を生成します。

Huffmanコードの生成

木のトラバース方法

Huffmanコードを生成するためには、Huffman木をトラバースする必要があります。

トラバースとは、木構造を辿ることで、各ノードを訪問するプロセスです。

Huffman木のトラバースには、通常、深さ優先探索(DFS)が用いられます。

具体的な手順は以下の通りです。

  • 左の子ノードを訪問: 現在のノードから左の子ノードに移動し、ビット 0 を追加します。
  • 右の子ノードを訪問: 現在のノードから右の子ノードに移動し、ビット 1 を追加します。
  • 葉ノードに到達: 葉ノードに到達したら、そのノードに対応するシンボルに対して、これまでに追加したビット列を割り当てます。

この方法により、各シンボルに対するHuffmanコードを生成します。

シンボルへのコード割り当て

Huffman木をトラバースすることで、各シンボルに対して可変長のビット列を割り当てます。

具体的には、以下のように行います。

  • 葉ノードの確認: トラバース中に葉ノードに到達した場合、そのノードに対応するシンボルに対して、現在のビット列を割り当てます。
  • ビット列の記録: 各シンボルに割り当てられたビット列を記録し、後のエンコードプロセスで使用します。

このプロセスにより、頻繁に出現するシンボルには短いビット列が、稀に出現するシンボルには長いビット列が割り当てられ、全体のデータサイズを効率的に削減します。

コードの最適化

Huffmanコードの生成後、さらなる最適化を行うことで、圧縮効率を向上させることができます。

以下に、コードの最適化のポイントを示します。

  • 冗長なビットの削除: 不要なビットを削除し、ビット列を最小化します。
  • 符号の再評価: シンボルの出現頻度が変化した場合、符号を再評価し、必要に応じて再割り当てを行います。
  • 符号の整合性確認: 生成された符号が一意であり、デコード時に誤解を招かないことを確認します。

これらの最適化により、Huffman法によるデータ圧縮の効果を最大限に引き出すことができます。

データのエンコード

エンコードの手順

Huffman法によるデータのエンコードは、生成されたHuffmanコードを用いて、元のデータを圧縮するプロセスです。

以下にエンコードの手順を示します。

  1. Huffmanコードの準備: 事前に生成されたHuffmanコードを用意します。

各シンボルに対応するビット列が含まれています。

  1. データの読み込み: 圧縮対象のデータを1文字ずつ読み込みます。
  2. ビット列の置換: 読み込んだシンボルを対応するHuffmanコードのビット列に置き換えます。
  3. ビット列の連結: 置き換えたビット列を順次連結し、圧縮データを生成します。

この手順により、元のデータを効率的に圧縮することができます。

圧縮ファイルの作成

エンコードされたデータをファイルに保存することで、圧縮ファイルを作成します。

以下の手順で行います。

  • ファイルのオープン: 書き込み用のファイルを開きます。

例：FILE *file = fopen("compressed.bin", "wb");

  • ビット列の書き込み: エンコードされたビット列をファイルに書き込みます。

ビット単位での書き込みが必要な場合、バッファを用いて効率的に行います。

  • ファイルのクローズ: 書き込みが完了したら、ファイルを閉じます。

例：fclose(file);

このプロセスにより、圧縮されたデータをファイルとして保存し、後でデコードするための準備が整います。

エンコードの効率化

エンコードプロセスの効率化は、圧縮速度と圧縮率の向上に寄与します。

以下に効率化のポイントを示します。

  • バッファリングの活用: データの読み書きにバッファを使用することで、I/O操作の回数を減らし、処理速度を向上させます。
  • 並列処理の導入: 大規模なデータを扱う場合、並列処理を導入することで、エンコードの速度を向上させることができます。
  • 最適化されたデータ構造の使用: 効率的なデータ構造を使用することで、メモリ使用量を削減し、処理速度を向上させます。

これらの方法を活用することで、Huffman法によるデータのエンコードをより効率的に行うことが可能です。

データのデコード

Huffman木の再構築

データのデコードを行うためには、エンコード時に使用したHuffman木を再構築する必要があります。

Huffman木の再構築は、以下の手順で行います。

  • シンボルと頻度の情報を取得: エンコード時に使用したシンボルとその頻度の情報を取得します。

この情報は、圧縮ファイルにメタデータとして保存されていることが一般的です。

  • 最小ヒープの利用: 取得したシンボルと頻度の情報を用いて、最小ヒープを構築します。
  • Huffman木の生成: 最小ヒープを用いて、Huffman木を再構築します。

この手順は、エンコード時のHuffman木の生成手順と同様です。

再構築されたHuffman木を用いて、エンコードされたデータを正確にデコードすることが可能になります。

エンコードデータの復元

エンコードされたデータを復元するためには、Huffman木を用いてビット列を元のシンボルに変換します。

以下の手順で行います。

  • ビット列の読み込み: 圧縮ファイルからビット列を順次読み込みます。
  • Huffman木のトラバース: 読み込んだビットに従ってHuffman木をトラバースし、葉ノードに到達したら対応するシンボルを取得します。
  • シンボルの連結: 取得したシンボルを順次連結し、元のデータを復元します。

このプロセスにより、エンコードされたデータを元の形式に戻すことができます。

デコードの手順

デコードの手順は、以下の通りです。

  1. Huffman木の再構築: 圧縮ファイルからシンボルと頻度の情報を取得し、Huffman木を再構築します。
  2. ビット列の読み込み: 圧縮ファイルからビット列を読み込みます。
  3. Huffman木のトラバース: 読み込んだビットに従ってHuffman木をトラバースし、対応するシンボルを取得します。
  4. データの復元: 取得したシンボルを連結し、元のデータを復元します。

この手順により、Huffman法で圧縮されたデータを正確にデコードし、元のデータを再現することができます。

C言語での実装例

必要なデータ構造

Huffman法をC言語で実装する際には、以下のデータ構造が必要です。

  • ノード構造体: Huffman木の各ノードを表現するための構造体です。

シンボル、頻度、左の子ノード、右の子ノードをメンバーとして持ちます。

  • 最小ヒープ: ノードを管理するための優先度キューです。

頻度の小さいノードを優先的に取り出すために使用します。

以下に、ノード構造体の例を示します。

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

コードの基本構成

Huffman法のC言語実装は、以下の基本構成で行います。

  1. シンボルの出現頻度の計算: データ内の各シンボルの出現頻度を計算します。
  2. Huffman木の構築: 最小ヒープを用いてHuffman木を構築します。
  3. Huffmanコードの生成: Huffman木をトラバースし、各シンボルに対するビット列を生成します。
  4. データのエンコード: 生成されたHuffmanコードを用いてデータを圧縮します。
  5. データのデコード: 圧縮データをHuffman木を用いて元のデータに復元します。

サンプルコード

このコードは、Huffman木を構築し、各シンボルに対するHuffmanコードを生成して表示します。

エンコードとデコードの実装は、生成されたHuffmanコードを用いてデータを圧縮および復元するために追加することができます。


#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] = '

#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;
}
';
        (*index)++;
    }
}

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

#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;
}
'; i++) {
        for (j = 0; symbols[j] != '

#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;
}
'; 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] != '

#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;
}
'; 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] = '

#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;
}
';
}

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] != '

#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;
}
'; 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! 日本語もちゃんとエンコードできる

このサンプルコードでは、データ内の各シンボルの出現頻度を計算し、結果を表示しています。

このような短いテキストであっても圧縮効果に期待できる強力なアルゴリズムです。

応用例

テキストデータの圧縮

Huffman法は、テキストデータの圧縮に非常に効果的です。

テキストデータは、特定の文字や単語が頻繁に出現する傾向があるため、Huffman法の可変長符号化によって効率的に圧縮できます。

以下に、テキストデータ圧縮のポイントを示します。

  • 文字頻度の分析: テキスト内の各文字の出現頻度を分析し、Huffman木を構築します。
  • 符号化の適用: 頻度に基づいて生成されたHuffmanコードを用いて、テキストデータを圧縮します。
  • 圧縮率の向上: 特に長い文書や特定の文字が多く出現する場合、圧縮率が向上します。

テキストデータの圧縮は、電子書籍やログファイルの保存において、ストレージの節約に役立ちます。

画像データの圧縮

画像データの圧縮にもHuffman法は応用されます。

特に、画像フォーマットの一部としてHuffman法が使用されることがあります。

以下に、画像データ圧縮のポイントを示します。

  • ピクセル値の頻度分析: 画像内のピクセル値の出現頻度を分析し、Huffman木を構築します。
  • 色の符号化: 頻度に基づいて生成されたHuffmanコードを用いて、ピクセルデータを圧縮します。
  • フォーマットの統合: JPEGなどの画像フォーマットでは、Huffman法が圧縮アルゴリズムの一部として組み込まれています。

画像データの圧縮は、ファイルサイズを削減し、転送速度を向上させるために重要です。

音声データの圧縮

音声データの圧縮にもHuffman法が利用されます。

音声データは、特定の周波数や音のパターンが繰り返されることが多いため、Huffman法による圧縮が効果的です。

以下に、音声データ圧縮のポイントを示します。

  • 音のパターン分析: 音声データ内の音のパターンや周波数の出現頻度を分析し、Huffman木を構築します。
  • 符号化の適用: 頻度に基づいて生成されたHuffmanコードを用いて、音声データを圧縮します。
  • 品質の維持: 可逆圧縮であるため、音声データの品質を維持しながら圧縮できます。

音声データの圧縮は、ストリーミングサービスや音声ファイルの保存において、データ転送量の削減に貢献します。

よくある質問

Huffman法の圧縮率はどのくらいですか？

Huffman法の圧縮率は、データの特性に大きく依存します。

一般的に、データ内のシンボルの出現頻度に偏りがあるほど、圧縮率は高くなります。

例えば、テキストデータでは、特定の文字が頻繁に出現するため、圧縮率が高くなる傾向があります。

一方、ランダムなデータやすでに圧縮されたデータに対しては、圧縮率が低くなるか、場合によっては圧縮できないこともあります。

他の圧縮アルゴリズムとの違いは何ですか？

Huffman法は、可変長符号化を用いる可逆圧縮アルゴリズムであり、以下の点で他の圧縮アルゴリズムと異なります。

  • 可逆性: Huffman法は可逆圧縮であり、圧縮前のデータを完全に復元できます。

例：gzipやbzip2も可逆圧縮を提供します。

  • 符号化の単純さ: Huffman法は比較的単純なアルゴリズムであり、実装が容易です。
  • 適用範囲: Huffman法は、特定のデータ形式(例：テキスト、画像、音声)に対して効果的ですが、他のアルゴリズム(例：LZ77、LZW)は、より広範なデータ形式に対応することができます。

Huffman法の実装で注意すべき点は？

Huffman法を実装する際には、以下の点に注意が必要です。

  • メモリ管理: Huffman木の構築や最小ヒープの管理において、メモリの動的確保と解放を適切に行う必要があります。
  • 符号の一意性: 生成されたHuffmanコードが一意であり、デコード時に誤解を招かないことを確認する必要があります。
  • エッジケースの処理: データ内のシンボルが少ない場合や、出現頻度が均一な場合など、エッジケースに対する処理を考慮する必要があります。

これらの点を考慮することで、Huffman法を効果的に実装し、データ圧縮を行うことができます。

まとめ

この記事では、Huffman法によるデータ圧縮の基本的な概念から、C言語での実装方法までを詳しく解説しました。

Huffman法の特性や利点を理解することで、さまざまなデータ形式に対して効率的な圧縮を実現する手法を学ぶことができました。

これを機に、実際にHuffman法を用いたプログラムを作成し、データ圧縮の効果を体感してみてはいかがでしょうか。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

アルゴリズム
  • URLをコピーしました！

関連記事

目次から探す