C言語で解説するランレングス符号化による連長圧縮実装

本記事では、C言語を利用した連長圧縮の実装方法を解説します。

ランレングス符号化は、同じ値が連続する場合にその出現回数を記録するシンプルなデータ圧縮手法です。

具体的なコード例を交えながら、アルゴリズムの考え方や実装手順をわかりやすく紹介します。

C言語での実践的な圧縮処理の基礎を学ぶ教材としてご活用いただけます。

連長圧縮アルゴリズムの原理

ランレングス符号化の基本

ランレングス符号化(Run-Length Encoding, RLE)は、連続する同一データをひとまとめにすることで、データ量を減らす手法です。

連続する値が多い場合に有効であり、例えば下記のようなデータ

$A,A,A,B,B,C,C,C,C$

は、$(3,A),(2,B),(4,C)$という形式で表現できます。

これにより、重複した情報をまとめることで、全体のデータサイズを削減できます。

アルゴリズムの利点と制約

RLEの利点はシンプルな実装である点と、連続性の高いデータに対して高い圧縮率を実現できる点です。

しかし、同じ値が連続しないランダムなデータでは、かえってデータサイズが増加する可能性もあります。

また、圧縮後のデータを復元する際には、正確な連続回数が必要となるため、エラー処理や異常系への対応が求められます。

C言語による実装準備

開発環境とコンパイラの設定

C言語で実装する場合、主に以下のツールや環境が必要になります。

• LinuxやWindows、macOSなどのOS
• gccやclangなどのCコンパイラ
• テキストエディタまたはIDE(例: Visual Studio Code、Code::Blocks)

これらの環境は基本的に整備済みとし、コンパイル時には以下のようなコマンドを使用します。

gcc -o rle rle.c

以上の環境が正しく構築されていれば、実装やデバッグがスムーズに進められます。

必要なライブラリとデータ構造の選定

基本的な標準ライブラリとして、stdio.h、stdlib.h、string.hなどが必要です。

データ構造については、入力データを配列やポインタで管理し、連長圧縮の結果を格納するために構造体を用いると分かりやすくなります。

例として、圧縮後のデータを保持するための構造体は下記のように定義できます。

typedef struct {
    int count;       // 連続回数
    char value;      // 対象となる値
} Run;

このようにシンプルなデータ構造を利用することで、プログラム全体の可読性と保守性が向上します。

実装手順の詳細解説

入力データの処理

ファイル入出力の方法

まず、入力元のファイルからデータを読み込むために、fopen、fread、fcloseなどの関数を活用します。

ファイルが正しく開けなかった場合のエラーチェックを行い、予期しない入力に対する対処も可能な設計にする必要があります。

例えば、以下のようなサンプルコードでファイルのオープンと読み込みを行うことができます。

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    FILE *inputFile = fopen("input.txt", "r"); // 入力ファイルをオープン
    if (inputFile == NULL) {
        fprintf(stderr, "Error: ファイルが開けません\n");
        return 1;
    }
    // ファイルからデータを読み込む処理
    fclose(inputFile); // ファイルをクローズ
    return 0;
}

// 入力ファイルが存在しない場合など、エラーメッセージが標準エラー出力に表示されます。

エッジケースの処理

入力データに対しては、空ファイルや一文字のみのファイル、極端に大きなデータが含まれる場合など、さまざまなエッジケースが考えられます。

• 空ファイルの場合は、処理を中断してユーザにエラーメッセージを出力する。
• 一文字だけの場合は、そのまま出力するか、特別なハンドリングを行う。
• 不正なデータ形式が混在している場合には、データの有効性チェックを入れることで、予期しない動作を防止します。

連長検出のロジック

カウンタ管理とリセット処理

入力データを1文字ずつ順に処理し、現在の値と前回の値を比較します。

連続する同一の値が検出された場合は、カウンタをインクリメントし、一度値が変わったらカウンタをリセットします。

この際、カウンタが示す連続回数と対象の値を構造体に保持することで、後の出力段階で利用できる形式に変換します。

具体的には、以下のような流れとなります。

• 初期状態ではカウンタを1に設定する。
• 次の文字と現在の文字を比較し、同一ならカウンタを加算する。
• 異なる場合には、現在のカウンタと値を保存し、カウンタを1にリセットする。

連続値の検出手法

文字列の各位置で前回の値と比較することによって連続性をチェックします。

• 最初の文字は特別扱いする。
• その後、ループ内で前回の文字と一致するかどうかを判定し、一致すればカウンタを更新します。
• 連続が途切れたタイミングで、既に記録した情報に対して新たなエントリを追加する処理を実装します。

なお、大量のデータを処理する際は、ポインタ演算などで効率よく走査する方法を検討すると良いでしょう。

出力データの生成

圧縮データのフォーマット設計

圧縮後のデータは、通常、各連続部分を$(count,value)$のペアとして表現します。

具体的には、以下のようなフォーマットが考えられます。

• 数値部分は整数として表現
• 値部分は文字またはバイト列として表現
• 区切り文字や固定長のフォーマットを採用することで、後続の復元処理を容易にする

例えば、圧縮データをテキスト形式にする場合、

3 A
2 B
4 C

といった出力が得られます。

書き出し処理の実装

圧縮結果をファイルに書き出す際は、fprintfやfwriteを利用して、適切なフォーマットで記録します。

書き出し処理では、ファイルが正しくオープンできるかのチェックや、書き込みエラーに対する対処が必要です。

実装例として、下記のコードは圧縮データの書き出しの一部を示しています。

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int count;
    char value;
} Run;
int main(void) {
    // 圧縮データのサンプル
    Run runData[] = { {3, 'A'}, {2, 'B'}, {4, 'C'} };
    FILE *outputFile = fopen("output.txt", "w"); // 出力ファイルをオープン
    if (outputFile == NULL) {
        fprintf(stderr, "Error: 出力ファイルが開けません\n");
        return 1;
    }
    // 各要素をファイルへ書き出す
    for (int i = 0; i < 3; i++) {
        fprintf(outputFile, "%d %c\n", runData[i].count, runData[i].value);
    }
    fclose(outputFile); // ファイルをクローズ
    return 0;
}

3 A
2 B
4 C

コード例の解説

各関数の役割と構造

コード例では、主に次のような関数を考慮しています。

• readInput(): 入力ファイルからデータを読み込む。
• encodeRLE(): 読み込んだデータに基づいて、連長圧縮のアルゴリズムを適用する。
• writeOutput(): 圧縮結果をファイルに書き出す。

各関数はシンプルな役割に徹し、関数間でデータの受け渡しを行うために、構造体やポインタを活用します。

コメントにはその関数の役割を明記し、コード自体の可読性を高めています。

以下は、簡単なサンプルコードの一部です。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 圧縮結果を格納する構造体
typedef struct {
    int count;       // 連続した回数
    char value;      // 圧縮対象の値
} Run;
// 入力ファイルから文字列を読み込む関数
char* readInput(const char *filename) {
    FILE *file = fopen(filename, "r"); // 入力ファイルをオープン
    if (file == NULL) {
        fprintf(stderr, "Error: 入力ファイルが開けません\n");
        return NULL;
    }
    fseek(file, 0, SEEK_END);
    long fileSize = ftell(file);
    rewind(file);
    char *data = (char *)malloc(fileSize + 1);
    if (data == NULL) {
        fprintf(stderr, "Error: メモリ確保に失敗しました\n");
        fclose(file);
        return NULL;
    }
    fread(data, 1, fileSize, file);
    data[fileSize] = '\0'; // 文字列終端
    fclose(file);
    return data;
}
// 連長圧縮を行う関数
// data: 入力文字列, runArray: 圧縮結果を格納する配列, runCount: 結果の数を返す変数
Run* encodeRLE(const char *data, int *runCount) {
    int len = strlen(data);
    // 仮の結果領域を確保
    Run *runs = (Run *)malloc(sizeof(Run) * len);
    int count = 0;
    int index = 0;
    char prev = data[0];
    int runLength = 1;
    for (int i = 1; i < len; i++) {
        if (data[i] == prev) {
            runLength++;
        } else {
            runs[index].count = runLength;
            runs[index].value = prev;
            index++;
            prev = data[i];
            runLength = 1;
        }
    }
    // 最後の文字列を記録
    runs[index].count = runLength;
    runs[index].value = prev;
    index++;
    *runCount = index;
    return runs;
}
int main(void) {
    // 入力データの読み込み
    char *inputStr = readInput("input.txt");
    if (inputStr == NULL) return 1;
    // 連長圧縮の実行
    int runCount = 0;
    Run *runs = encodeRLE(inputStr, &runCount);
    // 圧縮結果の表示
    for (int i = 0; i < runCount; i++) {
        printf("%d %c\n", runs[i].count, runs[i].value);
    }
    // メモリの解放
    free(inputStr);
    free(runs);
    return 0;
}

// 入力ファイル "input.txt" に「AAABBCCCC」と記述した場合の出力例:
// 3 A
// 2 B
// 4 C

メモリ管理とエラー処理

C言語では、動的メモリ管理が必要となるため、mallocやfreeを適切に利用します。

上記のサンプルコードでも、入力データのバッファや圧縮結果の配列を動的に確保した後、必ずfreeを用いてメモリを解放しています。

また、各関数では、ファイルのオープン失敗やメモリ確保失敗といったエラーをチェックし、エラーメッセージを表示することで、予期しない動作を防止しています。

エラー処理としては、エラー発生時にプログラムを終了する、または適切なリカバリ処理を行う、といった実装が考えられます。

デバッグと動作確認のポイント

テストケースの準備

動作確認を行う際には、複数のテストケースを準備することが重要です。

以下は例です。

• 入力ファイルに対して通常の連続データを含むケース
• 空ファイルやデータがひとつだけの場合のケース
• 入力データに特殊文字や改行が含まれるケース

これらを用いて、さまざまなシナリオで正しい圧縮結果が得られるかを検証する必要があります。

出力結果の検証方法

出力結果は、期待される圧縮結果とプログラムが出力する結果を比較します。

手動で確認する場合は、結果をファイルに書き出し、以下のように表形式で整理すると分かりやすいです。

また、デバッグ用に各関数内で変数の状態や処理経過をprintfで出力するなど、一時的なログ出力を利用して、アルゴリズムが正しく動作していることを確認する方法も有効です。

まとめ

本記事では、連長圧縮アルゴリズムの仕組みと、C言語を用いた実装の全体像を解説しています。

ランレングス符号化の基本原理や、入力データの読み込み・エッジケースへの対処、連続値検出および出力フォーマットの設計方法について学ぶことができます。

また、各関数の役割や動作確認のポイント、メモリ管理とエラー処理の実装例を通して、実用的なコード例も理解できる内容です。