ランレングス法の対象試験と出題頻度

ランレングス法は「AAABB を A3B2 に変える方式」と一行で説明され、読んだ瞬間に理解できてしまう用語です。ところが試験で実際に問われるのは、その先にあるビット数の計算と、圧縮比が1を超えてしまう条件のほう。

基礎理論の中でも計算問題へ直結する数少ない用語で、FE・APともに午前で語句選択として出題された実績があります。さらにAPでは午後のプログラミング問題としても登場しました。

まずは出題範囲を確認してください。

出題情報を確認する
対象試験:
基本情報技術者(FE) 応用情報技術者(AP)
出題頻度:
★★★★☆
Aランク(午前の定番。APは午後での実績あり)

ランレングス法の定義

データ圧縮の単元に入ると、ハフマン、LZW、ランレングスと似た響きの方式が並び、どれがどの説明だったか混ざってしまいます。この中でランレングス法は、最も単純な発想で成り立つ方式。

ラン(run)とは「同じ値が途切れずに並んでいる区間」を指す言葉で、その長さ(length)を数えて記録するので run-length encoding と呼ばれます。

処理は先頭から順に1文字ずつ読むだけの1パス処理で、アルゴリズムとしては極めて軽量な部類。

ランレングス法とは、

「同じデータが連続する区間の長さを数え、データと長さの組に置き換える可逆圧縮方式」

です。

編み物の編み図を思い浮かべてみてください。表目が10回続く場面を「表・表・表…」と10個書く人はいません。「表10目」と書けば済むからです。

ランレングス法がやっているのも、まったく同じ省略。元の並びを完全に復元できるため、可逆(ロスレス)に分類されます。

📊 ランレングス法の基本情報

項目 内容
英語名 Run-Length Encoding(RLE)
別名 ランレングス符号化/連長圧縮
分類 テクノロジ系 > 基礎理論 > アルゴリズム(データ圧縮)
可逆/非可逆 可逆(完全に元へ戻せる)
着目する性質 同一データの連続長(並び順に依存)
得意なデータ 白黒2値画像、FAX原稿、ベタ塗りのイラスト
苦手なデータ 連続がほとんどない自然画像・乱数列
計算量 O(n)(先頭から1回走査するだけ)

ランレングス法の仕組みを4ステップで理解する

符号化の手順:prev と runLength の2変数だけで動く

符号化に必要な変数は2つだけ。

直前に読んだ文字を保持する prev と、それが何回続いているかを数える runLength です。この2つがどう動くかを追いましょう。

ランレングス法の符号化ステップ

1
初期化
先頭文字を prev に入れ、runLength を1にする
↓
2
比較
次の1文字を読み、prev と等しいかを調べる
↓
3
加算/出力
同じなら runLength を1増やす。違えば[prev][runLength]を出力し、prev を更新して runLength を1に戻す
↓
4
終端処理
最後まで読んだら、残っている組を出力して終了

STEP3の「出力してから初期化し直す」順序を逆にすると1組ずれる

入力 xyyyzzzzxxyzzzzz を実際に流したときの変化が次の表です。

値が動いた瞬間の行だけを抜き出しました。

📊 トレース表:xyyyzzzzxxyzzzzz の符号化

i in[i] prev runLength out の内容
1 x x 1 (空)
2 y y 1 x1
5 z z 1 x1y3
9 x x 1 x1y3z4
11 y y 1 x1y3z4x2
12 z z 1 x1y3z4x2y1
16 z z 5 x1y3z4x2y1
終端 — — — x1y3z4x2y1z5

16文字が12文字になりました。圧縮比は 12÷16=0.75。数字が小さいほどよく縮んだことを表します。

なぜ白黒画像・FAXに強いのか

白黒2値画像は、1行をたどると白がずらりと並び、文字の部分で黒が数個続き、また白に戻ります。

つまりランが長い。1画素1ビットで持つ代わりに「白が何個」という数値だけを記録すれば、情報量は激減します。

1行(64画素)のラン分解

ラン長は4ビットで表すため、0〜15までしか書けない

① 元の1行(帯の幅がラン長の比率)

白10
黒34
白20
↓ 15を超えるランを切り分ける

② 符号化される9個のラン(色は白と黒が必ず交互)

白
10
黒
15
白・つなぎ
0
黒
15
白・つなぎ
0
黒
4
白
15
黒・つなぎ
0
白
5
復号側は白→黒→白→黒…と交互に読む決まりです。だから黒を15の次にもう一度続けたいときは、間に白の「0」を置いて順番だけ進めます。長さ0なので画素は1つも増えません。
結果は9個のラン。1個4ビットなので 9 × 4 = 36ビット。元は1画素1ビットで64ビットなので、圧縮比は 36 ÷ 64 = 0.5625。

つなぎの0を数え忘れると、36ビットではなく24ビットと答えてしまう

筆者は業務システムの帳票をFAX送信する案件を担当したとき、G3ファクシミリの符号化がRLE系のMH符号だと知りました。

「白紙に近い帳票ほど送信が速い」という利用者の体感は理論どおりだったわけです。

逆に写真を貼った帳票は送信時間が跳ね上がり、これがRLEの弱点そのものでした。

ハフマン符号との決定的な違い:連続か、頻度か

午前問題で最も混同されるのがハフマン符号との識別です。

判別の軸は1つ。RLEは「同じものが並んでいるか」だけを見る方式で、ハフマン符号は「同じものが何回出るか」を見る方式。

並び順に依存するのが前者、順序に依存しないのが後者。

📊 可逆圧縮3方式の比較

比較軸 ランレングス法 ハフマン符号 LZW(辞書式)
着目点 同一データの連続長 各データの出現頻度 繰り返しパターン
可逆性 可逆 可逆 可逆
符号長 固定長のペア(実装依存) 可変長・接頭辞符号 固定長の辞書番号
得意 白黒2値画像、FAX、ベタ塗り 出現に偏りがあるテキスト 同一語句が繰り返される文書
苦手 連続がないデータ(逆に増える) 頻度が均一なデータ 短いデータ(辞書が育たない)
狙われる語 「連なり」「ブロックの長さ」 「発生確率」「平均符号長」 「辞書」「参照番号」

3方式とも可逆である点は共通しているため、「可逆かどうか」では判別できません。

選択肢に現れるキーワードで切り分けてください。

実務での居場所:単独では使わず、他方式と組み合わせる

現在のRLEは、単独の圧縮ソフトとしてではなく他方式の前段・後段に置かれる「部品」として生き残っています。

Windows BMPのRLE8、PNGのフィルタ後段、JPEGの量子化後の係数列などが代表例。組込み系でメモリが逼迫した場面では、スプライト画像に自前のRLEをかける判断も現役です。

なおZIPは「複数ファイルをまとめるアーカイブ(書庫化)」と「圧縮」の2機能を併せ持つ形式であり、圧縮部分の主役はLZ系+ハフマンの組み合わせ。

書庫化と圧縮は別概念なので、午前問題では区別して読む必要があります。

📝 ポイント整理

・RLEが見るのは「連続」だけ。頻度も辞書も使わない
・変数は prev と runLength の2つ、走査は1回だけのO(n)処理
・ラン長に上限があると分割が起き、長さ0のランを補う必要が出る

ランレングス法は試験ではこう出る!

出題パターン分析

📝 IPA試験での出題パターン

パターン1:語句選択型(FE午前・AP午前)
定義文を4択から選ぶ形と、「ハフマン方式はどれか」でRLEをダミーに使う逆パターンの2種類。選択肢中の「連なり」「ブロックの長さ」がRLEの目印。

 

パターン2:ビット数計算型(IP中問・FE午後)
「ラン長の上限で分割 → 色情報ビットを付加 → 総ビット数を合計」の3手順。上限超過時の分割と長さ0のランを落とすと必ず外れる。

 

パターン3:アルゴリズム実装型(AP午後)
擬似言語で prev と runLength をトレースし、圧縮比を算出したうえで最悪ケースを言葉で説明させる。

 

パターン1は暗記で確保でき、得点差がつくのはパターン2と3。

ひっかけポイントと対策

誤答選択肢の顔ぶれは毎回よく似ています。次の4類型を覚えれば消去法が働きます。

⚠️ ひっかけ早見表

誤答の値・選択肢 その正体
「発生確率」「平均符号長が最小」 ハフマン符号の説明文。最頻出のダミー
EBCDIC符号・巡回符号・BCD そもそも圧縮ではない符号化方式
「標本化」「量子化」を含む記述 A/D変換の工程。圧縮とは別の話
計算問題で少なめのビット数 長さ0のランの補填漏れ

📝 試験区分別の対策方針

・FE:午前は語句一致で1問確保。科目B用にトレースを1回手書き
・AP:午前はハフマンとの識別。午後は圧縮比の式と最悪ケースまで
・参考(IP):上限で分割するビット数計算の型を1問だけ解く

過去問での出題実績(7件)を開く

FE 平成21年春 午前 問4:「同じ文字の繰返し部分を反復回数と文字の組に置き換える方法はどれか」。選択肢はEBCDIC符号/巡回符号/ハフマン符号/ランレングス符号化。正解は「エ」

FE 平成21年春 午後 問1(ハードウェア):2値画像のランレングス符号化を回路で実装。ラン長 n の2進表記の桁数 m を用いた可変長ビット表現を扱う(記述・複数設問)

AP 平成30年秋 午前 問5:「ハフマン方式はどれか」。選択肢アの「0又は1の連なりを一つのブロックとし、このブロックに長さを表す符号を割り当てる」がランレングス法の説明。正解は「ウ」

AP 平成24年春 午後 問2(プログラミング):[文字][回数]形式と、4回以上のみ[文字]*[回数]とする形式の2方式を擬似言語で実装・比較。圧縮比の算出と最悪ケース(圧縮比2)の記述を含む全4設問

参考:IP 平成24年秋 問94(中問C):ラン長を最大15で区切り、白黒を各4ビットの対で表す方式のビット数。正解は「ウ(40ビット)」

参考:IP 平成24年秋 問95(中問C):最大128で区切り、値−1を7ビット+色情報1ビットで表す方式のビット数。正解は「エ(24ビット)」

参考:IP 平成24年秋 問96(中問C):桁数情報(m−2個の1)+区切りの0+ラン長値、という可変長形式のビット数。正解は「ア(27ビット)」

圧縮したのにデータが増える?RLEの“逆効果”を計算で確かめる

筆者はAP午後でこのプログラミング問題を選択したとき、擬似言語のトレースは完答できたのに、最後の圧縮比の設問で落としました。

「連続がまったくない入力では2倍になる」ことに気づけなかったからです。仕組みを知っていることと、数字で言えることは別物でした。

圧縮比の定義は次の一行に尽きます。圧縮比=圧縮後のサイズ÷圧縮前のサイズ。

1未満なら縮み、1を超えたら膨らんだことを意味します。

最良ケースと最悪ケースの計算を開く

ケース1:連続がある(xyyyzzzzxxyzzzzz)
16文字 → x1y3z4x2y1z5 の12文字。圧縮比は 12 ÷ 16 = 0.75。

ケース2:ランが長い(白が20個続く行)
20文字 → [白][20]の2要素。圧縮比は 2 ÷ 20 = 0.1。ランが長いほど劇的に縮む。

ケース3:連続がまったくない(abcdefghij)
10文字 → a1b1c1d1e1f1g1h1i1j1 の20文字。圧縮比は 20 ÷ 10 = 2.0。すべての文字に「1」という回数が付くため、必ずちょうど2倍になる。

膨張は事故ではなく仕様上の必然。

だから実装側では、短い連続をあえて圧縮しない仕組みを用意します。次の擬似コードは、3回以下の連続はそのまま出力し、4回以上のときだけ[文字]*[回数]に置き換える方式の骨子です。

〇圧縮処理(入力 in[1..n])
  prev ← in[1],runLength ← 1
  i を 2 から n まで 1 ずつ増やす
    in[i]が prev と等しい ならば
      runLength ← runLength + 1
    そうでなければ
      出力(prev,runLength)
      prev ← in[i],runLength ← 1
  出力(prev,runLength)

〇出力(文字 c,整数 r)
  r が 3 以下 ならば c を r 個そのまま書き出す
  そうでなければ c,"*",r を書き出す

この分岐があれば、連続のない入力でも出力は元と同じ長さで済み、圧縮比は1で頭打ちになります。

実ファイル形式が「非圧縮モード」を併せ持つのも同じ理由。圧縮後が元より大きければ非圧縮のまま格納するフラグを持たせるのが、フォーマット設計の定石です。

【確認テスト】ランレングス法の理解度チェック

Q. データ圧縮手法であるランレングス法の説明として、最も適切なものはどれか。

  • A. 発生確率が分かっている記号群を、1記号当たりの平均符号長が最小になるように符号化する。
  • B. 0又は1の連なりを一つのブロックとし、そのブロックの長さを表す符号を割り当てる。
  • C. データ中に繰り返し出現する文字列パターンを辞書に登録し、辞書の参照番号に置き換える。
正解と解説を見る

正解:B

解説:
Bの「連なり」という語が、ランレングス法の核心である連続長への着目を示しています。ブロック(=ラン)の長さを符号にする、という記述はそのまま定義。平成30年秋 午前問5では、この文言とAの文言が同じ問題の選択肢として並んでおり、識別できないと失点に直結します。3つとも可逆圧縮である点は共通なので、可逆か否かでは判別できない点に注意してください。

Aが不正解の理由:出現確率に着目して平均符号長を最小化する可変長符号化=ハフマン符号の説明。頻度を見ている時点でRLEではありません。

Cが不正解の理由:パターンを辞書に登録して参照番号へ置き換える方式=LZW符号化の説明。GIFやZIPの基盤技術であり、「辞書」「参照番号」が目印です。

ランレングス法の関連用語ネットワーク

ランレングス法は圧縮方式の入口にあたる用語で、前後にはビット表現の基礎と、より高度な符号化方式が控えています。

📊 関連用語マップ

カテゴリ 関連用語
前提知識 ビット/バイト、2進数、アルゴリズム、データ圧縮(可逆・非可逆の全体像)
関連用語 ハフマン符号、LZW(辞書式圧縮)、MH符号(G3ファクシミリ)、可逆圧縮/非可逆圧縮
発展 2分木(ハフマン木の前提)、オーダー記法(RLEはO(n)の1パス処理)、JPEG/PNG/ZIPの内部構造