解説

〔ウェーブレット木の構築〕では、各ノードに対応する文字列を決定してから、そのノードにキー値を登録するので、設問1では先にイの文字列を求めた後、その文字列をもとにアのキー値を求める流れになります。

〔イについて〕
〔ウェーブレット木の構築〕(2)で得られたビット列「0101010110」を、続く(3)でビットの 0 と 1 に分けます。ビットが0の場合の文字列は"CCAAA"、ビットが1の場合の文字列は"TGGGT"になります。よってイには TGGGT が入ります。

∴イ＝TGGGT

〔アについて〕
右のノードに対応する文字列"TGGGT"からキー値を求めます。〔ウェーブレット木の構築〕(2)に従うと、キー値を得る手順は次の通りです。

1. イの文字列"TGGGT"をビット列に符号化する
2. ノードの深さに応じて決まるビット位置を求める
3. 1.で求めたビット列から、文字の並びと同じ順番でビットを取り出し、アのキー値とする

手順1

文字Gは10、文字Tは11ですから、文字列"TGGGT"をビット列に符号化すると「11 10 10 10 11」が得られます。

手順2

取り出すビット位置は、"左から(深さ＋1)番目"です。アのノードの深さは1なので、ビット位置は「左から(1＋1＝)2番目」となります。

手順3

手順1で求めた「11 10 10 10 11」から、各文字ごとに左から2番目のビットを取り出します。

　11 10 10 10 11 → 10001

以上の手順を行うと、アに入るキー値 10001 が得られます。∴ア＝10001

解説

問題文には、「左の子ノードに振り分けられる文字の個数は，根のキー値の0の個数に等しく，ウである」と記述されています。設問1のイを求める手順でわかったように、ある文字が左のノードに振り分けられるか右のノードに振り分けられるかは、キー値のビット列が 0 か 1 によって決定されます。

文字列Pの根のキー値「0101010110」のうち 0 の個数は5個なので、左のノードに振り分けられる文字の個数は5個になります（図1の"CCAAA"を見れば一目瞭然ですが...）。よってウには 5 が入ります。

∴5

解説

〔エ，オについて〕
図3「関数rankのプログラム」の7行目のコメント行に「rに対応するビット列の左からd番目のビット位置のビットの値をbに格納」と書かれています。8行目から10行目は、この処理を行っている箇所です。

あるビット列から特定の位置のビットを取り出す場合は、以下の手順で処理を行います。

1. 取り出したい位置のビットを 1、それ以外の位置のビットを 0 としたビット列を用意する
2. 対象文字のビット列と、1.で用意したビット列の論理積(AND)を求める
3. 2.で求めた論理積を右にビットシフトして、取り出したい位置のビットを取得する

例として、ビット列"11010"の左から2番目のビットを取り出したい場合を考えます。手順1で"01000"を用意します。これは、1を左に3ビットシフトした値です。手順2で"11010"と"01000"の論理積"01000"を求めます。手順3で01000を右に3ビットシフトすると、元のビット列の左から2番目のビットである「1」が得られます。この手順1がプログラムの8行目、手順2が図3の9行目、手順3が図3の10行目に対応しています。

また、d はプログラムの3行目と22行目の記述から、符号中の左からのビット位置を保持する変数であり、whileループを繰り返す（木構造を下がる）ごとに1、2、3、…と1ずつ増えていくことがわかります。

エは、手順1のビット列を用意するために「1を何ビット左にシフトすれば良いか」と考えます。具体例を挙げて、プログラムに落とし込む手順を踏むと、

ビット列の長さが5、左から2番目を取り出す場合

用意するビット列は"01000"なので、1を左に3ビットシフトする

ビット列の長さが5、左から3番目を取り出す場合

用意するビット列は"00100"なので、1を左に2ビットシフトする

ビット列の長さが6、左から3番目を取り出す場合

用意するビット列は"001000"なので、1を左に3ビットシフトする

ビット列の長さが6、左から2番目を取り出す場合

用意するビット列は"010000"なので、1を左に4ビットシフトする

というように、左にシフト（及び手順3で右にビットシフト）させる大きさは「符号のビット数 - 取り出したいビット位置」で求められることがわかります。各文字の符号化に必要な最小のビット数は、大域変数 DEPTH に、取り出す位置は前述の通り変数 d に格納されているので、エに入る式は DEPTH - d が適切です。

オは、手順2に該当し、プログラムの8行目(手順1に相当)で作成したマスクビット列 x と論理積を求めるものですので、取り出し対象のビット列である r が入ります。

∴エ＝DEPTH - d
　オ＝r

〔「カ」について〕
図3の10行目のコメントに「bは0か1の値」と書かれているので、カには0か1のどちらかが入ります。また、図3の17行目から、この条件式を満たす場合の処理は、「nodep ← nodep.left」であることがわかります。nodep.left は、左の子ノードへのポインタであり、次回のwhileループで左の子ノードを検索対象とする処理です。本問のウェーブレット木では、ある文字の指定位置から取り出したビットが 0 の場合には左の子ノードに、1 の場合には右の子ノードに振り分けるので、出現回数を数える対象となっている文字を格納する葉に行き着くためには、bが0の場合には左の子ノードへ、bが1の場合には右の子ノードへ進まなければなりません。よってカには 0 が入ります。

∴カ＝0

〔キについて〕
図3の4行目から n は検索対象の文字列(キー値)の長さであることがわかります。このことから、プログラムの21行目は n の更新をする処理であり、キには次の検索対象の文字列の長さが入ることがわかります。次の検索対象となる文字列とは、現在のノードに振り分けられた文字列のうち、次にたどる(左又は右の)子ノードに振り分けられる文字列です。
次の検索対象となる子ノードの文字列長は、11行目から15行目の処理で求めています。具体的には、現在のノードのキー値の各ビットと b を比較して、一致する場合に変数 count を増やしています。何をしているかというと、出現回数を数える対象となっている文字と同じ子ノードに振り分けられる文字数を数えているのです。変数 count に次回の検索対象となる文字列の長さが格納されているので、次のwhileループが始まる前に n を count で更新することになります。よってキには count が入ります。

∴キ＝count

解説

〔クについて〕
ウェーブレット木の構築は、各文字ごとにルートから葉までのノードで操作を行います。ルートから葉までにたどるノードの数は、ウェーブレット木の深さと等しくなります。文字の種類の個数をσとすると、ウェーブレット木の深さは log₂(σ) となるので、クには σ が入ります。

∴ク＝σ

〔ケについて〕
各ノードでの操作に掛かる定数時間を考えます。プログラムを見ると、各ノードにはwhileループの中に記述された処理が1回だけ行われます。この中には、キー値全てを走査するfor文が1つ含まれているため、各ノードに対する計算量は O(N) (線形時間：データ量の分だけ時間を要する)になります。

∴ケ＝N

〔コについて〕
ウェーブレット木全体のキー値の長さの総和は、「深さごとのキー値の長さの和×深さ」で求めることができます。

まず、深さごとのキー値の長さの和について考えます。
本問の図1を見てみると、深さ0のノード(根)のキー値は「0101010110」であり、長さは 10(＝N) です。深さ1のノードのキー値の長さは、いずれも 5 です。ノードの深さごとのキー値は、根のキー値が分割されたものですから、ノードの深さごとのキー値の長さの和は、常に 10、すなわち N になります。

次に、ウェーブレット木の深さを求めます。これはクで求めたとおり、log₂(σ)です。

以上より、

• 深さごとのキー値の長さの和：N
• ウェーブレット木の深さ:log₂(σ)

ですから、ウェーブレット木全体のキー値の長さの総和は Nlog₂(σ) になります。

∴コ＝Nlog₂(σ)