This question's explanation and your answers so far.
問96
頻出度★☆☆
図1は，8×8画素の白黒の画像例である。この図に対して，白を0，黒を1として表すと，図2に示すように8ビットのビット列が8行あるディジタルデータとして，画像データを表現することができる。
文字データしか送れない通信で画像データを送ろうとする場合，画像データを文字データであるかのように変換して通信する必要がある。
また，文字データと比べてデータ量の大きい画像データを効率よく通信するために，データを圧縮して送るという工夫がなされる。図2のビット列を左上から順に見ていくと，0が10個続き，次に1が34個続き，その次に0が20個続いていることが分かる。この同じ値が続く個数のことをランレングスという。これを利用して画像データを圧縮する方法を考える。
次に示す画像データの表現方法は，画像データの情報量を圧縮することを目的とする変換である。図2に示す画像データは，何ビットで表現されるか。
〔画像データの表現方法〕
(1) 画像データをランレングスで表現し，それらの値を2進数で表現する。
(2) ランレングスの値を2進数で表現したときの値 n に対して，その n の桁数が m のとき，次の形式で，一つのランレングスを表現する。
①桁数の情報
②区切りの情報
③ランレングスの情報
①桁数の情報：(m－2)ビットの連続する1で表現。なお，m が0～2の場合は，“0”と表現
②区切りの情報：区切りは“0”で表現
③ランレングスの情報：n
例えば，ランレングスの値が20のとき，それを2進数で表現したときの値 n は“10100”となり，その桁数 m は5となる。したがって，m が5のとき，①は(5－2)ビットの連続する1なので“111”となり，これに区切りの“0”と n をつなげ，結果は“111010100”となる。
(3) (2)で求めた形式の値をつなげていく。このとき，画像データは必ず白から始まるものとし，もし，画像データが黒から始まる場合は，ランレングス0の白があるとして先頭に“000”を補う。
出典 平成24年度 秋期 ITパスポート試験 問96
解説
問 96
//
※ Our check while writing this explanation could not fully confirm the published answer; scoring follows IPA's official key.
○ア
正解Reading the bit string of Figure 2 in order from the top left, it runs white(0) x 10 → black(1) x 34 → white(0) x 20 (64 bits in total = 8 x 8 pixels). The original wording of (3), following the source page 44, is “assume that the image data always starts with white; if the image data starts with black, treat it as if there is a white run-length of 0, and prepend 000 at the beginning”, and Figure 2 does start with white, so the step of prepending “000” is unnecessary. The rest is to encode each of the three run-lengths 10, 34 and 20 by the rule and add them up.
(a) 10 → in binary n is “1010”, so the digit count is m = 4. ① (digit-count information) is the (4-2) = 2-bit “11”, ② (separator) is “0”, and ③ is the 4 bits of n. The code is “1101010”, i.e. 2 + 1 + 4 = 7 bits.
(b) 34 → in binary n is “100010”, so m = 6. ① is the (6-2) = 4-bit “1111”, ② is “0”, and ③ is 6 bits. 4 + 1 + 6 = 11 bits.
(c) 20 → in binary n is “10100”, so m = 5. ① is the (5-2) = 3-bit “111”, ② is “0”, and ③ is 5 bits. 3 + 1 + 5 = 9 bits (this is exactly the example given in the question).
The total is 7 + 11 + 9 = 27 bits, so ア is correct. Note also that when m is 3 or more, the length of one run-length can be summarized as (m-2) + 1 + m = 2m - 1 bits, so substituting m = 4, 6, 5 gives 7, 11 and 9 straight away.
×Incorrectイ
30 is the value obtained by adding the unnecessary 3 bits “000” to the correct 27 bits. The instruction in (3) to prepend “000” is a remedy for the case where the image data starts with black; the first row of Figure 2 is 00000000, which starts with white, so it must not be prepended. Doing it mechanically without reading the condition makes the result 3 bits too long.
×Incorrectウ
33 is the value obtained when ① (the digit-count information) is misread as “m bits” instead of “(m-2) consecutive 1s”. With that misreading it becomes m + 1 + m = 2m + 1, and for m = 4, 6, 5 this gives 9 + 13 + 11 = 33 bits. What is being confused is that ① does not lay out the digit count m itself, but is a variable-length code that conveys m by means of m-2 ones.
×Incorrectエ
36 is the value when the unnecessary 3 bits “000” are further added on top of the mistake in ウ above (treating ① as m bits, which gives 33 bits), so two errors are stacked. There are only three run-lengths, 10, 34 and 20, and if the rule is followed the total cannot exceed 7 + 11 + 9 = 27 bits.
ここがポイント
Run-length encoding is a lossless compression method that reduces the amount of information by recording how many times the same value occurs in a row (the run length); it is very effective for data in which the same colour continues for a long stretch, such as black-and-white binary images or fax data. The starting point is to first count the run lengths correctly from the figure, as in white 10, black 34, white 20.
The variable-length code in this question is made up of ① (m-2) consecutive 1s + ② the separator “0” + ③ the m bits of n, so when m is 3 or more one run-length takes 2m - 1 bits. ① is a mechanism that conveys the digit count m by how many 1s appear before the separating 0; when m is 0 to 2, ① is the single bit “0” (which is why a white run-length of 0 is represented as “0” + “0” + “0” = “000”, 3 bits in all).