基本情報技術者 2009年 春期 午前（科目A） 問04
問題文
文字列中で同じ文字が繰り返される場合、繰返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法はどれか。
選択肢
ア：EBCDIC符号
イ：巡回符号
ウ：ハフマン符号
エ：ランレングス符号化（正解）
🔒 解説は解答すると表示されます
ランレングス符号化【午前解説】
正解の理由
正解は エ：ランレングス符号化（Run-Length Encoding, RLE）です。RLEは連続する同一文字（または同一バイト列）を、その繰返し回数と文字自体の組に置き換えて表現します。例えば "AAAAABBBCC" は "5A3B2C" のように表現でき、長い連続が多いデータに対して効果的です。問題文の「繰返し部分を反復回数と文字の組に置き換えて短くする」という説明がRLEの定義と一致します。
解法ステップ
- 問題文でキーワードを探す：「繰返し」「反復回数」「文字の組で置き換え」などの語句。
- 各選択肢の定義を短く思い出す：EBCDIC＝文字コード、巡回符号＝誤り訂正、ハフマン＝頻度ベースの可変長符号、ランレングス＝連続圧縮。
- 問題文の動作と各方式の特徴を照合して最も一致するものを選ぶ。
- 一致度の高いものがあればそれを正答とする（ここではRLE）。
選択肢別の誤答解説
- ア: EBCDIC符号
文字コード（主にIBM系の8ビット文字コード）であり、圧縮手法ではなく置き換えの概念とは無関係です。 - イ: 巡回符号
通信の誤り検出・訂正に使う符号（循環シフト可能な構造）で、文字列を短くする圧縮法ではありません。 - ウ: ハフマン符号
出現頻度に基づく可変長符号化で、連続回数をそのまま反復回数と文字の組に置き換える方式ではありません。 - エ: ランレングス符号化
連続する同一文字列を回数＋文字で表す方式で、問題文の記述と完全に一致します。
よくある誤解
- ハフマン符号と混同する誤解：ハフマンは「頻度に応じて可変長で符号化」する方式で、連続回数を直接置き換えるものではありません。
- RLEが常に圧縮すると思い込む誤解：短い連続やランダムデータでは逆にデータが増えることがある点を見落としやすいです。
- 表現方式の詳細を無視する誤解：繰返し回数の格納ビット長や最大値の扱い（例：カウンタが1バイトか複数バイトか）を考慮しないと実装上問題になります。
補足コラム
ランレングス符号化はビットマップ画像（単色領域が多い）やFAX、TIFFの一部形式などでよく使われます。利点は単純で実装が容易な点、欠点はデータに連続が少ないと非効率（あるいは膨張）する点です。実運用ではハフマンやLZWなど他手法と組み合わせて用いられることが多く、例えば先にRLEで単純なランを縮め、その後ハフマンで更に符号化するようなハイブリッド方式が効果的です。
FAQ
Q1: RLEはどんなデータに向くのですか？
A1: 同一シンボルが長く連続するデータ（白黒画像の大きな塗りつぶし領域、単純なパターン等）に向きます。ランが短いと効果薄または膨張します。
A1: 同一シンボルが長く連続するデータ（白黒画像の大きな塗りつぶし領域、単純なパターン等）に向きます。ランが短いと効果薄または膨張します。
Q2: RLEは可逆圧縮ですか？
A2: はい。元のデータを完全に復元できる可逆（ロスレス）圧縮方式です。
A2: はい。元のデータを完全に復元できる可逆（ロスレス）圧縮方式です。
Q3: 繰返し回数が大きい場合はどう表現しますか？
A3: 実装によってカウンタのビット幅や分割方式が異なります。例えば1バイトでは255が上限なので、それ以上は複数のランに分ける必要があります。
A3: 実装によってカウンタのビット幅や分割方式が異なります。例えば1バイトでは255が上限なので、それ以上は複数のランに分ける必要があります。
Q4: RLEとハフマンはどちらが優れている？
A4: 用途によります。ランが多ければRLEが簡単かつ効果的、全体の頻度分布で圧縮するならハフマンが有利です。組合せ運用も一般的です。
A4: 用途によります。ランが多ければRLEが簡単かつ効果的、全体の頻度分布で圧縮するならハフマンが有利です。組合せ運用も一般的です。
関連キーワード: ランレングス, RLE, 圧縮, 可逆圧縮, ハフマン符号, EBCDIC, 巡回符号, 画像圧縮, LZW, 圧縮アルゴリズム
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！