基本情報 平成21年度 秋期 問4：テクノロジ系に関する問題

答えは d「ランレングス符号化」 です。

ランレングス符号化は「同じ文字の繰り返しを、回数と文字のセットに置き換えて短くする」やり方。

例：「AAAAAAABBBCC」（12文字）→「A7B3C2」（6文字）に圧縮。同じ文字が長く続くデータ（FAXの白い部分、シンプルな図形）でとても効きます。

👉 覚え方：「ラン（連続）の長さ（length）を数える」=ランレングス。

ほかの選択肢：a EBCDIC=昔のメインフレーム用の文字コード／b 巡回符号=エラー検出用の符号／c ハフマン符号=よく出る文字に短いコードを割り当てる別の圧縮法（zipなど）。

なぜこれが正解か

正解は d。ランレングス符号化（RLE: Run-Length Encoding）は、同一文字（または同一値）が連続する部分を「文字＋繰返し回数」のペアに置換する可逆圧縮方式。例：「AAAABBBCCDAA」→「A4B3C2D1A2」。実装が簡単で計算量も小さい。

各選択肢の解説

• a EBCDIC（Extended Binary Coded Decimal Interchange Code）：IBMメインフレーム由来の8ビット文字コード体系。圧縮方式ではない。
• b 巡回符号（CRC）：エラー検出に使う符号化方式。
• c ハフマン符号：出現頻度の高い文字に短いビット列、低い文字に長いビット列を割り当てるエントロピー符号化。zip/gzipの内部で使用。

覚え方・ひっかけ注意

圧縮方式の分類：可逆（lossless）＝RLE、ハフマン、LZ77/LZ78、zip、PNG／非可逆（lossy）＝JPEG（DCT＋量子化）、MP3、MPEG。RLEは「連続データ向け」、ハフマンは「出現頻度の偏り向け」と用途で区別。

理論的背景

RLEは最古の圧縮方式の一つで、シンボル列を {(symbol, run_length)} のペア列に変換する。最良圧縮率はデータが完全に均一な場合に1/n（nがランの長さ）、最悪は全シンボルがランダムで連続のない場合に2倍に膨らむ。改良版にゴロム符号、ライス符号があり、特定の確率分布に最適化されている。FAXのG3/G4規格（ITU-T T.4/T.6）はMH（Modified Huffman、行単位RLE）、MR（Modified READ、2次元RLE）、MMR（Modified Modified READ）を採用。

実務での使われ方

RLEは画像圧縮（BMPのRLE圧縮モード、TIFFのCompression=PackBits）、データベースのカラムストア圧縮（同値が連続するカラムに高効果）、機械学習の疎行列圧縮で活用。汎用圧縮（zip、gzip）ではLZ77（過去出現パターンの参照）＋ハフマン符号化の組合せがDEFLATEアルゴリズムとして標準化。Brotli（Google開発、Web圧縮の新標準）、Zstandard（Meta開発、高速・高圧縮）はDEFLATEを大きく上回る性能を持ち、近年主流化。

試験での位置づけ

FE科目Aでは圧縮方式の識別問題が定番。応用情報・データベーススペシャリストでは具体的な圧縮率計算、シャノン情報量・エントロピーの定義、ハフマン木の構築問題が頻出。エンベデッドシステムスペシャリストではIoTセンサデータの軽量圧縮（CBOR、MessagePack）が題材になる。

選択肢の発展補足

エントロピー符号化の理論的下限はシャノンエントロピー H = -Σ p_i log2(p_i) ビット/シンボル。ハフマン符号は最適接頭符号だが整数ビット長制約のためHを完全には達成できず、算術符号化（Range coding）は理論限界に漸近するが特許問題が長く実用化を阻んだ。動画圧縮（H.264/AVC、H.265/HEVC、AV1）は予測符号化＋DCT/DST＋量子化＋エントロピー符号化（CABAC: Context Adaptive Binary Arithmetic Coding）の組合せ。LLM時代のテキスト圧縮ではTransformer言語モデル自体を確率モデルとして使う「ニューラル圧縮」も研究領域。