問85
頻出度★☆☆
図を画素で表す手法を考える。図1の場合，3×3個の画素を左上から1行ずつ右方向へ1画素ずつ読み取り，黒なら B，白なら W と書くと“BWBBBBBWB”(9文字)となる。次に，B や W が n 文字連続する場合を“Bn”，“Wn”と表す(n は2以上の整数)と，図1は“BWB5WB”(6文字)と表現でき，このときの圧縮率を 6/9=66.7% であると定義する。図2の5×5の図形について同じ手法で表現すると，圧縮率は何%か。
平成22年度 秋期 ITパスポート試験 問85
テクノロジ系情報メディア › マルチメディア技術
This question's explanation and your answers so far.
解説
問 85
Incorrectア
48.0% is the value obtained as 100−52, that is, the proportion that the compression “removed”. As the Figure 1 example shows with 6÷9 = 66.7%, this question defines the compression ratio as the number of characters after compression divided by the number of characters before it. It is not the reduction rate (the proportion that was cut), so 13 characters ÷ 25 characters = 52.0% is itself the answer. Mistaking the definition and answering with the remainder leads you to pick ア.
- イ
正解 The correct answer is イ (52.0%). First, read the 25 pixels of Figure 2 one row at a time from the top-left toward the right, exactly as the question states. Row 1 is black in all 5 positions, giving BBBBB; row 2 is black only at the left end, giving BWWWW; row 3 has the 4 leftmost pixels black, giving BBBBW; rows 4 and 5 are both BWWWW. Joining them gives the 25 characters “BBBBBBWWWWBBBBWBWWWWBWWWW”. The most important point here is that a run is not broken at the end of a row. The 5 black pixels of row 1 connect with the 1 black pixel at the start of row 2, so the string begins with 6 black pixels in a row. Divided into runs, it is 6 B, 4 W, 4 B, 1 W, 1 B, 4 W, 1 B, and 4 W — eight runs in all. Only a run of 2 or more characters is replaced by a 2-character form such as “B6” or “W4”; a run of just 1 character is not replaced and is counted as 1 character (because n is defined as an integer of 2 or more). The compressed form is therefore 2+2+2+1+1+2+1+2 = 13 characters. Following the definition given in the question, the compression ratio is the compressed length divided by the original length, so 13÷25 = 0.52, that is, 52.0%.
Incorrectウ
76.0% corresponds to 19÷25 and comes out when the reading order is mistaken. For example, reading vertically column by column downward from the top-left gives BBBBB / BWBWW / BWBWW / BWBWW / BWWWW; black and white then alternate one pixel at a time in many places, so single-character runs that cannot be replaced occur frequently and the compressed form ends up as 19 characters. The question specifies scanning one row at a time toward the right, and in that order the long runs stay together and shrink to 13 characters.
Incorrectエ
88.0% corresponds to 22÷25 and is the figure obtained when compression is applied to only some of the runs. For example, replacing only the conspicuous 5 black pixels of row 1 with B5 and counting the rest as they are gives 25−5+2 = 22 characters, which is 88%. In reality every run of 2 or more characters is subject to replacement, and Figure 2 has five runs of 4 or more characters (6 black, 4 black, and 4 white in three places), so it shrinks to 13 characters. Count the runs through to the very end so that no replacement is missed.
ここがポイント
- The basics of run-length encoding — a lossless compression that replaces a stretch of identical values with a pair consisting of the symbol and the number of repetitions. Always follow the scanning order the question specifies (here, one row at a time from the top-left toward the right), and when the same color continues across a row boundary, join it and count it as a single run. Overlooking this crossing of rows leads to a wrong character count.
- Follow the definition of compression ratio that the question itself gives — here it is the number of characters after compression divided by the number before it, and the smaller the value, the better the compression (the 6÷9 = 66.7% of Figure 1 is the model). Also, since n is fixed at 2 or more, a run of only 1 character is not replaced, because replacing it would actually increase it to 2 characters.
用語