応用情報技術者 2018年 秋期 午後 問03

解答の論理構成

1. 文字列の符号化
   【問題文】には「文字列Pの文字Aを00、文字Cを01、文字Gを10、文字Tを11の2ビットのビット列に符号化して、ウェーブレット木を構築する」とあります。
   そこで P＝“CTCGAGAGTA” を 2 ビットごとに並べると、上位ビット（1 ビット目）は
   C T C G A G A G T A 0 1 0 1 0 1 0 1 1 0
   となり、根のキー値が “0101010110” になることが【問題文】で示されています。
2. 根からの振り分け
   根のキー値 “0101010110” を左から走査し、ビットが0の位置の文字を左側、1の位置の文字を右側に順序を保って集めます。
   • 0 だった位置（1,3,5,7,10 文字目）→ “C C A A A”
   • 1 だった位置（2,4,6,8,9 文字目）→ “T G G G T”
     【問題文】に示された「ビットの値が0の場合の文字列として“CCAAA”」「ビットの値が1の場合の文字列として“イ”」より、 イ＝“TGGGT” で確定します。
3. 深さ1（右子ノード）のキー値
   右子ノードは “TGGGT” に対応します。深さ1 なので【問題文】の規定「ノードの深さに応じて決まるビット位置は、“左から（深さ+1）番目”」より、2 ビット目（下位ビット）を並べたものがキー値です。
   T G G G T 1 0 0 0 1
   したがって右子ノードのキー値は “10001”。
   図1中の ア に入る文字列は “10001” となります。
4. 結論
   ア：10001
   イ：TGGGT

誤りやすいポイント

• 文字列の順序保持を忘れ、ビット0・1ごとにソートしてしまう
• 深さに応じたビット位置の数え方（“左から（深さ+1）番目”）を取り違え、1 ビット目を再利用してしまう
• 2 ビット符号の上位・下位を逆に読んで “01010…” と “10101…” を取り違える
• “TGGGT” の G を3個ではなく4個、または T を1個見落として “TGGG” としてしまう

FAQ

解答の論理構成

1. 根ノードのキー値
   問題文には「文字列P “CTCGAGAGTA”に対応する根のキー値はビット列0101010110となる。」と明記されています。
2. 0 の個数を数える
   同じく問題文で「左の子ノードに振り分けられる文字の個数は、根のキー値の0の個数に等しく、ウである。」とあります。
   0101010110 の各ビットを左から確認すると
   0,1,0,1,0,1,0,1,1,0 の計10ビットのうち
   0 は 1・3・5・7・10 番目の 5 か所です。
3. よって ウ には 5 が入ります。

誤りやすいポイント

• ビット列「0101010110」を 2 進数の値として解釈してしまい、0 の“個数”ではなく“値”で比較してしまう。
• ビットを左からではなく右から数えて 0 の位置を取り違える。
• 「0101010110」を 8 ビットや 12 ビットと誤認し、桁数を増減して数えてしまう。

FAQ

解答の論理構成

1. 取得したいのは “対象文字の符号の左から d 番目のビット”
   【問題文】には
   “// r に対応するビット列の左から d 番目のビット位置のビットの値を b に格納”
   と明記されています。
   そこで
   text x ← ( 1 を左に エ ビットシフト… ) x ← ( x and オ ) b ← ( x を右に エ ビットシフト… )
   という 3 ステップで r の該当ビットだけを取り出します。
2. エ の決定
   r は “文字の符号化に必要な最小のビット数” で表され、その値は “大域変数DEPTH” に保持されるとあります。
   左から d 番目のビットを取り出すには、右寄せ表現で
   シフト量 ＝ DEPTH - d
   とするのが定石です。
   したがって
   エ＝“DEPTH - d”。
3. オ の決定
   and でマスクする相手は符号そのもの、すなわち “r” です。
   よって
   オ＝“r”。
4. カ の決定
   ビット値が 0 なら左部分列へ、1 なら右部分列へ進むのは
   【問題文】“文字Cの符号の左から1番目のビットの値は0なので、文字Cは根から左の子ノードに振り分けられる”
   から明らかです。比較対象は数値リテラル “0”。
   よって
   カ＝“0”。
5. キ の決定
   ループの最後で n を次レベルの文字列長に更新する行です。
   その値は for ループで数え上げた count に置き換わります。
   “count ← count + 1” により得られるのは “次ノードに渡す部分文字列長” なので
   キ＝“count”。

誤りやすいポイント

• DEPTH と d の引き算の向きを逆に書き “d - DEPTH” としてしまう
  （左端基準か右端基準かを取り違え）。
• オ に nodep.key を入れてしまい、ビット抽出対象を誤る。
• b==1 を左に、b==0 を右に進むと勘違いして条件を反転。
• n ← m - count のように減算してしまい、次レベルの長さを壊す。

FAQ

解答の論理構成

• 【問題文】には
  “与えられた文字列Q内に含まれる文字の種類の個数をσとするとき”
  と明記されています。この “σ” が以後の計算量評価でそのまま使われるため、 “文字ごとに$lo{g}_2([ク])$か所のノードで操作を行い”
  の ク には “σ” が入ります。
  ⇒ ク = σ
• 同じ段落で
  “文字列Qが与えられたとき、文字列Qの長さをN”
  と置いています。よって式
  “合計でO(ケ ✕ $lo{g}_2([ク])$)である。”
  の ケ には “N” が入ります。
  ⇒ ケ = N
• 文字が1文字あたり $lo{g}_2(\sigma )$ ビットずつ複数レベルに分散してキー値に格納されるので、全体のビット列長は
  $N\times lo{g}_2(\sigma )$。
  【問題文】の
  “構築されたウェーブレット木が保持するキー値のビット列の長さの総和は、コである。”
  に当てはめると
  ⇒ コ = $Nlo{g}_2(\sigma )$

誤りやすいポイント

• “σ” と “N” の取り違え
  σは“種類数”、Nは“文字列長”です。両者を逆に入れると計算量が O(σ log₂N) となり意味が変わってしまいます。
• 乗算か指数かの混同
  $Nlo{g}_2(\sigma )$ は “N と log を掛ける” 形です。$lo{g}_2({\sigma }^N)$ ではありません。
• 2 のべき乗の前提を見落とす
  “ここで、議論を簡潔にするためには2以上の2のべき乗とする” という一文は、深さ＝$lo{g}_2(\sigma )$ が整数になることを保証しています。これを忘れると “天井関数” 付きの式を誤って書きがちです。

FAQ