応用情報技術者 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. エ（図3の [a] に対応）

• 図3の最初の処理はマスクを作るところで、書かれているのは x ← ( 1 を左に [a] ビットシフトした値 ) です。ここで目的は r の「左から d 番目」のビットを取り出すことです。一般に整数のビット操作は右端（最下位ビット）を位置0として扱うため、「左から d 番目」を右端基準のシフト量に変換する必要があります。符号長が DEPTH ビットであれば、右端基準のビット位置は DEPTH - d になります。したがってマスクは 1 を DEPTH - d ビット左シフトして作るべきです。
• よって エ = DEPTH - d。
• 例（問題の符号化A=00, C=01, ... でDEPTH=2, r(C)=01, d=1）：シフト量は2 - 1 = 1、マスクは10₂、10₂ & 01₂ = 00₂ → 上位ビットは0であると判定できます。

1. オ（図3の [b] に対応）

• 次に x ← ( x and [b] ) とあります。マスク x と論理積を取る対象は、取り出したいビットを含む値、すなわち対象文字の符号を整数化した r です。したがって オ = r。
• マスクとrの AND で当該ビットのみが残り、その後の右シフトで0/1を得ます。

1. カ（図3の [c] に対応）

• 図中および本文で、ビット値が0の場合は左の子ノードへ、1の場合は右の子ノードへ振り分けると説明されています（例として「文字Cの符号の左から1番目のビットの値は0なので、文字Cは根から左の子ノードに振り分けられる」）。よって分岐判定はbが0と等しいかどうかを見ます。
• よって カ = 0。

1. キ（図3の [d] に対応）

• ループ内でcountをゼロから増やし、nodep.keyの左からi番目までのビットのうちbと等しいものを数えています。このcountは「次の深さに渡される要素（子ノードに振り分けられる文字）の個数」を表します。rankの計算は深さ毎に対象集合の先頭n個に対して行い、次の深さではその個数に限定して再帰的（反復）に調べるため、次ループのnにcountを代入する必要があります。最終的にノードがなくなったときに返す値も最後に得た個数です。
• よって キ = count。

• エ：DEPTH - d
• オ：r
• カ：0
• キ：count

• root.key = 0101010110（長さ10）、対象文字Cの符号r = 01、初期n = m = 10。
• d=1：シフト量 DEPTH - d = 2 - 1 = 1、マスク=10₂、b = (mask & r) >>1 = 0。root.key の先頭10ビット中 0 の個数 count = 5 → n←5。nodep ← nodep.left。
• d=2：シフト量 0、マスク=01₂、b = (mask & r) >>0 = 1。左子のキー（長さ5）中 1 の個数 count = 2 → n←2。次の nodep は葉なので次に nodep が NULL になり、最終的に返る値 n = 2 が rank の結果（C の出現回数）になります。

誤りやすいポイント

• rとDEPTHを取り違える：シフト量にrを使う誤りが多いです。シフト量はビット列長（DEPTH）と現在の深さdに基づき決まります。
• ビットの位置の数え方を間違える：左から数える（1始まり）ことを忘れ、右端基準でd-1を使う誤り。正しくはシフト量 = DEPTH - dです。
• 左右の振り分け値を逆にする：本文ではビット値0 → 左、1 → 右 と明示されているので、ここを逆にすると全てのカウントが崩れます。
• n の更新を忘れる、誤った変数を代入する：次の深さで扱う要素数は count に更新しなければなりません（n ← count）。更新しないと次ループで不正確な範囲を調べます。
• ループのインデックスとkeyの「左からi番目」の対応を確実にする：インデックスの基準（1始まり／0始まり）をコードと設計で統一してください。

FAQ

解答の論理構成

• 【問題文】には
  “与えられた文字列Q内に含まれる文字の種類の個数をσとするとき”
  と明記されています。この “σ” が以後の計算量評価でそのまま使われるため、 “文字ごとにlog₂(ク)か所のノードで操作を行い”
  の ク には “σ” が入ります。
  ⇒ ク = σ
• 同じ段落で
  “文字列Qが与えられたとき、文字列Qの長さをN”
  と置いています。よって式
  “合計でO(ケ × log₂(ク))である。”
  の ケ には “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