平成31年春期午後問8 ハフマン符号化のトレース4 再帰処理


平成31年春期午後問8。ハフマン符号化を扱った疑似言語の「プログラム2」のトレースです。構築されたハフマン木を使って文字を「0と1に符号化」するプログラムで再帰処理を用いています。

【再帰処理は自分で自分を呼出す 引数や変数に注意してトレース】

再帰処理は「自分で自分を呼出す」という特殊なプログラムですが、基本は変わりません。「呼出す元のプログラム」と「呼び出し先」のプログラムがあり、それぞれ引数や、変数の状況は異なります。扱うプログラムは同じでも、その中で使っている引数、変数の内容は異なる‥ここさえしっかり留意すれば再帰処理は複雑ではありません。

ここでは、状況設定として、問題文中に記載されている「図2」を使い、文字「D」を符号化することとします。なので、問題文中表5の「説明」から判断してkの初期値は「K=3」とします。

以上をもってトレースに入ります。ここでは、便宜上、プログラム「Encode」のプログラム名に番号を付けます。なので、最初に実行されるプログラムを「Encode1」とします。

1行目「Encode1」の引数は下記のとおりです。

2行目。「K=3」なので条件判定式「Parent[k] ≧ 0」は真となり、3行目に移動。3行目で新たに自分自身「Encode」を呼出しています。3行目Encodeの第1引数は「Parent[k]」となっています。ここでは。「K=3」なので「Parent[3]=4」、 3行目Encodeの第1引数は 「4」となります。

よって、「Encode1」から呼び出された「Encode2」の引数は下記のとおりです。

2行目。「k=4」なので「Parent[k] ≧ 0」は真となり、3行目に移動。3行目で新たに自分自身「Encode」を呼出しています。 そして、「Encode2」の時と同様に、「Encode3」が呼び出され、引数、変数の状況は下記の通りとなります。

プログラム「Encode3」の2行目。「k=5」なので「Parent ≧ 0」は真となり、3行目に移動。「Encode4」を呼出します。引数、変数の状況は下記のとおりです。

【再帰処理 自分自身の呼出しの後は自分自身に戻る】

プログラム「Encode4」の2行目。「k=6」なので、ここで初めて「Parent ≧ 0」が偽となり、処理は条件判断ブロックの外(8行目の次)に移動します。しかし、プログラム「Encode」に「8行目の次」がありませんので、ここで「Encode4」は終了となり、処理が「Encode3」の4行目に戻ります。

なお、処理が 「Encode3」の4行目に戻れば、引数、変数の状況も「Encode3」実行時の状態になりますので、下記の通りとなります。

ここから「Encode3」のトレースとなりますが、4行目も条件判定式となります。ここでは「K=5」となりますので真となり、処理は5行目に移ります。

なお、4行目の「Left[parent[k]] ≧ 0」は二重変数となっており、少々ややこしいので、「k=3」の場合の状況を下記に示します。

5行目で「0」が表示。ここでは出力先がディスプレイなのか、プリンタなのか‥等の記載がありませんので、「何らかの形で出力される」という程度の理解で構いません。実際、問題文中にも「出力先」に関する具体的な記載はありません。

5行目を終了すると、処理は7、8行目に移りますが、7、8行目は特に処理がないため、ここで「Encode3」が終了となります。

「Encode3」が終了 すると処理は「Encode2」に戻ります。引数、変数の状態は次の通りです。

「Encode2」の処理は4行目から再開され、4行目の条件判定式は下記の通り解析され、偽となります。

処理は6行目に移り「1」が表示されます。処理は7、8行目に移りますが、特に処理がありませんので、これで「Encode2」が終了。処理は「Encode1」に戻ります。

「Encode1」も「Encode2」同様に4行目から再開されます。引数、変数の状況、4行目条件判定文の解析は下記のとおりです。

4行目の条件判定式は偽となり、処理は6行目に移って「1」が表示されます。処理は7、8行目に移りますが、特に処理がありませんので「Encode1」の処理が終了。これで「プログラム2」のすべての処理が終了します。

ここまでで表示された符号は「0」「1」「1」。問題文中の図2のハフマン木(”D”の符号は”011″ちなる)と一致することがわかります。


平成31年春期午後問8 ハフマン符号化のトレース3


こちらは平成31年春期午後問8ハフマン符号化のトレース2の続きです。

【プログラム「Huffman」はほとんど加算、代入だけ】

プログラム「Huffman」5行目実行直前の各変数の状況は次の通りです。

5~15行目は繰返処理になりますが、nsizeの値は「4」ですので、5行目の継続条件式「nsize ≧ 2」は真となり、処理は6行目に移ります。6~13行目までは加算、代入が続きます。13行目実行後の状況は次の通りです。

【配列変数でハフマン木が構築されていることが確認できる】

上図を問題文中の図3と比べてみてください。配列parent、left、ridht、freqが、問題文中の図3に近づいていることがわかります。 また、図3はプログラム1の最終的な実行結果(完成したハフマン木が表現されている状態)であることも確認できます。

このまま14行目以降を実行し、5~15行目の繰返処理を2巡、3巡と繰返すと、最終的に図3が完成しますので、ぜひ試してみてください!


平成31年春期午後問8 ハフマン符号化のトレース2


こちらは平成31年春期午後問8 ハフマン符号化のトレース1の続きとなります。

【4行目で他のプログラムへ 引数に注意!】

プログラム1の4行目でプログラム「SortNode」(16行目)へジャンプします。「SortNode」の仕様は問題文中の表3をご覧ください。引数size、parent[]、freq[]は「入力」用の引数となっていますので、実行前に具体的なデータが必要になりますが、sizeの値は4、 parent[]、freq[]は プログラム「Huffman」の時と同じ内容です。

また、表3のプログラム「SortNode」の仕様から、引数nsizeとnode[]は「出力」となっていますので、「SortNode」実行後の結果が格納される引数です。そのため、プログラム実行前にデータを格納する必要はありません。加えて、17行目で変数「i」も宣言していますので、まとめると下記のようになります。

【ようやくトレースらしくなるのは18行目以降から】

ここから18行目以降のトレースとなります。
18行目でnsizeに0が入ります。
19行目は24行目までの繰返処理の始端となっており、変数iに0が設定され、継続条件の「i < size」が「真」となりますので、処理は20行目に移ります。
20行目は条件判定文です。ここでは、「i=0」なので「parent[0]=-1」となり、条件判定文「Parent[i] < 0」は「真」です。処理は21行目に進みます。
21、22行目は順次処理、23行目は条件判定文の終端で特に何も処理しません。24行目は繰返処理の終端なので、処理は19行目に戻ります。

ここから、繰返処理(19~24行目)の2巡目。19行目では「i」に1が加算(i=1となる)された後、継続条件式「i < size」は、まだ「真」なので、処理は20行目に移ります。
i=1の状況ですが、20行目の条件判定文「Parent[i] < 0」はまた「真」なので、処理は21行目に進みます。

この要領で繰返処理(19~24行目)を実行します。繰返処理終了後、25行目に処理が移った時の各変数の状況は下記のとおりです。

<参考>繰返処理終了の流れ
基本文法ですが、念のため繰返処理終了の流れを再確認しますと、19~24行目の処理の終盤、「i=3」の状況で22・23・24行目と処理が進みます。24行目は繰返処理の終端となりますので、処理が19行目に戻ります。
19行目でiに1が加算され「i=4」になった時点で繰返しの継続条件「i < size」が偽となるので、繰返処理終了となり、処理は25行目に移ります。

【仕様のみのプログラム 入出力データを確認すれば怖くない!】

25行目はプログラム「Sort」にジャンプしますが‥。「Sort」のプログラムは「仕様」のみで、実際のプログラムは記載されていません。試験問題ではこんなケースもあります。なので、このような時は、プログラム中に「入力」されたデータが、どのように「出力」されるかを考えます。

プログラム「Sort」に関しては「プログラム1の説明」の(5)に「配列nodeを受け取り‥」「要素番号に対応する要素組が表す節の値が昇順となるように整列‥」と記載されています。

次に表4からプログラム「Sort」はfreq[]、nsize、node[]が「入力データ」、node[]のみが「出力データ」であることがわかります。ここまでの処理でnsize=4、freq[]、node[]は下記のとおりです。

プログラム「Sort」の処理終了後、配列nodeが下記の通りとなって出力結果となります。「nodeに格納されているデータ」を「freqに格納されているデータの昇順」になるように整列しています。

以上でプログラム「Sort」は終了。プログラム全体に「26行目」はありませんので、ここでプログラム「SortNode」も終了となり、処理は元々の呼出し元だった4行目の次の5行目に移ります。


平成31年春期午後問8 ハフマン符号化のトレース1


与えられた文字列をハフマン符号化するプログラムのトレースです。「プログラム1」には3つのプログラム「Huffman」「SortNode」「Sort」がありますが、それぞれの「仕様」は問題文をご覧ください。


【問題文の仕様を利用してプログラム「Huffman」の引数を設定する】

トレースはプログラム「Huffman」の1行目から実行しますが、1行目を実行するには多くの「引数」が必要です。

プログラム「Huffman」ではすべての引数の「入出力」が「入力/出力」となっているため、「size、parent[]、left[]、right[]、freq[]」に予めデータが与えられる必要があります。

問題文中「プログラム1の説明」の(1)で「parent[]、left[]、right[]、freq[]のすべての要素は-1で初期化されている」との旨が記載されているので、まずは、上記4つの配列変数にはすべて「-1」が入ります。

次に「プログラム1の説明」の(3)でプログラム「Huffman」に入力するデータが説明されています。

上記⑤に「出現回数」という言葉が出て来ていますので、表1の「出現回数表」が具体例のひとつとして使えそうです(もちろん、他の例を自身で考えてもOKです)。

表1の例を使うとすると、「葉である節の個数size」の初期値は「4」。parent、left、right、freqの初期値は次の通りとなります。
なお、問題文中の「図3」は「プログラム実行後の結果」ですので、これを初期値と勘違いしないよう注意しましょう。

【引数以外に宣言部で設定される変数i、j、nsizeおよび配列node】

加えて、2、3行目でi、j、nsizeおよび配列node[]が宣言されます(値の設定なし)ので、「size」とあわせて下記の通りに書きます。

少し長くなりましたが、ここまででプログラム「Huffman」の宣言部(3行目まで)の設定が終了です。


二分探索木 データの追加3


17行目。分岐処理(17~30行目)の条件判定。「i = nil」は真となり処理は18行目に移ります。18~21行目はそれぞれ代入処理が順次行われます。

※18行目の「データの追加位置」は「6」となります。これは、事前に与えられた構造化変数TREEのデータ数が5個であるためです。

22行目。分岐処理(22~28行目)の条件判定。「ROOT = nil」は偽となり、処理は24行目に移りますが、24行目以降ががさらに分岐処理(24~27行目)となっていますが、トレース順序は「基本通り」なので安心してください!

24行目。分岐処理(24~27行目)の条件判定。「parentが4」なので 「TREE[parent].DATAは15」となり、条件判定は真。処理は25行目に移ります。

25行目。TREE[4].L-PTRにjの値6が代入されます。以降、処理は27、28、30行目と移り、プログラム全体が終了となります。

処理終了後の変数の状況および構造化変数(二分探索木)の状況は下記のとおりです。

【参考】継続条件が複合条件になっている繰返し処理と、その直後の条件分岐処理の関係

今回の疑似言語プログラムの実行部は繰返処理(10~16行目)と条件分岐処理(17~30行目)に大きく分かれます。非常に多く使われるパターンですので、覚えておくと何かと有利です。

ポイントは17行目の条件判定です。これは「10行目の繰返しの継続条件のどれが偽となって繰返し処理が終了となったか?」を検査しています。

10行目の継続条件は条件がふたつ(「i ≠ nil」と「TREE[i].DATA ≠ NUM」)あります。前者は「追加データの格納場所が見つかった(I = nil)か否か」。後者は「追加データと同じ値のデータが構造体変数中に見つかったか否か」を表しています。

前者の条件か後者の条件か‥いずれの条件式が偽となって繰返し処理が終了したかを17行目で検査し、その結果次第で条件分岐処理(17~30行目)の処理内容が変わる‥というわけです。