プログラミングとデータ表現（ランレングス符号化）

高校生の健太さんは、モノクロ画像のデータ圧縮方法について調べている。題材として、0（白）と 1（黒）のピクセル値が並んだ1次元の配列 Data を考える。

健太：「例えば、Data = [0, 0, 0, 1, 1, 1, 1, 0, 0] (要素数 N=9) のようなデータがあるとする。このまま保存すると 9 個のデータが必要だけど、0 が 3 個、1 が 4 個、0 が 2 個というように、同じ値が連続する『長さ』を記録すれば、データ量を削減できそうだ。」

この「ランレングス符号化（RLE）」と呼ばれる方法を実装するため、健太さんは以下の仕様でプログラムを作成することにした。

仕様:

1. 元の配列 Data を走査し、連続する値の「長さ」を新しい配列 RLE に順に格納する。
2. Data は必ず 0 か 1 で始まる。
3. RLE の 0 番目の要素 (RLE[0]) は、最初の「0（白）」の連続する長さとする。
4. RLE の 1 番目の要素 (RLE[1]) は、次の「1（黒）」の連続する長さとする。
5. 以降、RLE の偶数番目 (RLE[2k]) は 0 の長さ、奇数番目 (RLE[2k+1]) は 1 の長さ、と交互に格納する。
6. 【重要】 もし Data が 1（黒）から始まる場合、Data[0] より前に「長さ 0 の 0（白）のラン」があったとみなし、RLE[0] に 0 を格納する。

仕様の例:

• Data = [0, 0, 0, 1, 1, 1, 1, 0, 0] (N=9) の場合:
  • 0 のラン (長さ 3), 1 のラン (長さ 4), 0 のラン (長さ 2)
  • RLE = [3, 4, 2] となる。
• Data = [1, 1, 0, 0, 0, 1, 1, 1, 1] (N=9) の場合:
  • 0 のラン (長さ 0) (仕様6), 1 のラン (長さ 2), 0 のラン (長さ 3), 1 のラン (長さ 4)
  • RLE = [0, 2, 3, 4] となる。

健太さんは、この仕様に基づき、配列 Data とその要素数 N を受け取り、配列 RLE を出力する CreateRLE という手続き（プログラム1）を作成した。

プログラム1

// 配列 Data (要素数 N) から配列 RLE を作成する
手続 CreateRLE(Data, N)
  RLE = [] // 空の配列
  もし (N == 0) ならば
    戻る // データがなければ終了
  
  // 仕様6: 最初のピクセルが 1 の場合の処理
  もし (Data[0] == 1) ならば
    RLE.追加(0)
  
  現在の値 = Data[0]
  現在の長さ = 0
  i = 0

  反復 i < N
    もし (Data[i] == 現在の値) ならば
      // 同じ値が続いている
      現在の長さ = 現在の長さ + 1
    そうでなければ
      // 値が変わった
      RLE.追加(現在の長さ)
      現在の値 = 1 - 現在の値 // 0 なら 1 に、1 なら 0 にする
      現在の長さ = 1      // 新しいランのカウント開始
    
    i = i + 1
  
  // 最後のランの長さを配列に追加
  RLE.追加(現在の長さ)
  
  表示(RLE)
  戻る