応用情報技術者過去問題 平成30年秋期 午後問3

問3 プログラミング

ウェーブレット木に関する次の記述を読んで,設問1〜4に答えよ。

 ウェーブレット木は,文字列内の文字の出現頻度を集計する場合などに用いられる2分木である。ウェーブレット木は,文字列内に含まれる文字を符号化して,それを基に構築される。特に計算に必要な作業領域を小さくできるので,文字列が長大な場合に効果的である。
 例えば,DNAはA(アデニン),C(シトシン),G(グアニン),T(チミン)の4種類の文字の配列で表すことができ,その配列は長大になることが多いので,ウェーブレット木はDNAの塩基配列(以下,DNA配列という)の構造解析に適している。
 ウェーブレット木において,文字の出現回数を数える操作と文字の出現位置を返す操作を組み合わせることによって,文字列の様々な操作を実現することができる。本問では,文字の出現回数を数える操作を扱う。

〔ウェーブレット木の構築〕
 文字の種類の個数が4の場合を考える。DNA配列を例に文字列Pを"CTCGAGAGTA"とするとき,ウェーブレット木が構築される様子を図1に示す。
 ここで,2分木の頂点のノードを根と呼び,子をもたないノードを葉と呼ぶ。根からノードまでの経路の長さ(経路に含まれるノードの個数−1)を,そのノードの深さと呼ぶ。各ノードにはキー値を登録する。
 図1では,文字列Pの文字Aを00,文字Cを01,文字Gを10,文字Tを11の2ビットのビット列に符号化して,ウェーブレット木を構築する様子を示している。また,図1の文字列の振り分けは,ウェーブレット木によって文字列Pが振り分けられる様子を示している。
pm03_1.gif/image-size:525×164
 ウェーブレット木は,次の(1)〜(3)の手順で構築する。
  • 根(深さ0)を生成し,文字列Pを対応付ける。
  • ノードに対応する文字列の各文字を表す符号に対して,ノードの深さに応じて決まるビット位置のビットの値を取り出し,文字の並びと同じ順番で並べてビット列として構成したものをキー値としてノードに登録する。ここで,ノードの深さに応じて決まるビット位置は,"左から(深さ+1)番目"とする。
     ノードが根の場合は,ビット位置は左から(0+1=1)番目となるので,図2に示すように,文字列P"CTCGAGAGTA"に対応する根のキー値はビット列0101010110となる。
    pm03_2.gif/image-size:311×88
  • キー値のビット列を左から1ビットずつ順番に見ていき,キー値の元になった文字列から,そのビットに対応する文字を,ビットの値が0の場合とビットの値が1の場合とで分けて取り出し,それぞれの文字を順番に並べて新たな文字列を作成する。
     文字列Pに対応する根のキー値の場合は,ビットの値が0の場合の文字列として"CCAAA"を取り出し,ビットの値が1の場合の文字列として""を取り出す。
     ビットの値が0の場合に取り出した文字列内の文字が2種類以上の場合は,その文字列に対応する新たなノードを生成して,左の子ノードとする。取り出した文字列内の文字が1種類の場合は,新たなノードは生成しない。
     ビットの値が1の場合に取り出した文字列内の文字が2種類以上の場合は,その文字列に対応する新たなノードを生成して,右の子ノードとする。取り出した文字列内の文字が1種類の場合は,新たなノードは生成しない。
     生成した子ノードに対して,(2),(3)の処理を繰り返す。新たなノードが生成されなかった場合は,処理を終了する。


〔文字の出現回数を数える操作〕
 文字列P全体での文字C(=01)の出現回数は,次の(1),(2)の手順で求める。
  • 文字Cの符号の左から1番目のビットの値は0なので,文字Cは根から左の子ノードに振り分けられる。左の子ノードに振り分けられる文字の個数は,根のキー値の0の個数に等しく,である。
  • 文字Cの符号の左から2番目のビットの値は1である。(1)で振り分けられた左の子ノードのキー値の1の個数は2で,このノードは葉であるので,これが文字列P全体での文字Cの出現回数となる。

〔文字の出現回数を数えるプログラム〕
 与えられた文字列Q内に含まれる文字の種類の個数をσとするとき,あらかじめ生成したウェーブレット木を用いて,与えられた文字列内で指定した文字の出現回数を数えるプログラムを考える。ウェーブレット木の各ノードを表す構造体 Node を表1に示す。左の子ノード,又は右の子ノードがない場合は,それぞれ,left,right にはNULLを格納する。
pm03_3.gif/image-size:331×99
 文字列Qに対応して生成したウェーブレット木の根へのポインタを root とする。文字列Q内に存在する一つの文字(以下,対象文字という)をビット列に符号化して,整数(0〜σ〜1)に変換したものを r とする。
 このとき,文字列Qの1文字目からm文字目までの部分文字列で,対象文字の出現回数を数える関数 rank(root,m,r) のプログラムを図3に示す。
 文字の符号化に必要な最小のビット数は,大域変数 DEPTH に格納されているものとする。
pm03_4.gif/image-size:497×433
〔ウェーブレット木の評価〕
 文字列Qが与えられたとき,文字列Qの長さをN,文字の種類の個数をσとする。ここで,議論を簡潔にするためにσは2以上の2のべき乗とする。
 文字列Qが与えられたときのウェーブレット木の構築時間は,文字ごとにlog2()か所のノードで操作を行い,各ノードでの操作は定数時間で行うことができるので,合計でO(×log2())である。
 構築されたウェーブレット木が保持するキー値のビット列の長さの総和は,である。

設問1

図1中の,図1及び本文中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ア:
  • イ:

-解答例・解答の要点-

  • ア:10001
  • イ:TGGGT

-解説-

この設問の解説はまだありません。

設問2

本文中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ウ:

-解答例・解答の要点-

  • ウ:5

-解説-

この設問の解説はまだありません。

設問3

図3中のに入れる適切な字句を答えよ。

-解答入力欄-

  • エ:
  • オ:
  • カ:
  • キ:

-解答例・解答の要点-

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

-解説-

この設問の解説はまだありません。

設問4

本文中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ク:
  • ケ:
  • コ:

-解答例・解答の要点-

  • ク:σ
  • ケ:N
  • コ:Nlog2(σ)

-解説-

この設問の解説はまだありません。
問3成績
【30年秋期 午後問題】
 問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11
© 2010-2019 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop