coffee break

某の情報系大学院生

LaTeXでハフマン符号の木を作る

大分前にレポートでハフマン符号を作る問題をやるときに、せっかくだからTeX上で作れないかなと方法を探していたら無事見つかったので残しておく。
考えはなんてことない、木構造を作るパッケージを使って木を横に伸びるようにさせるだけだ。

必要なパッケージ

tikz

これ1つだけでかなりの描画ツールが使用できる。今回はtreesを用いる。

サンプルコード

今回は4つの要素を持つハフマン符号を作成する。

実行結果

f:id:mildtech:20170728223610p:plain
木にしては結構歪な仕上がりになっているが枝に割り当てる符号語を表示させたかったためこれでいいとする。

解説

  • \documentclass[dvipdfmx]{artcle}

出力時のドライバにdvipdfmxを必ず指定することを忘れないこと。これを忘れるとせっかく作った木が全部表示されなくなる。

  • \usepackage{tikz}
  • \usetikzlibrary{trees}

tikzのライブラリtreesを使いますの宣言

  • \tikzset{スタイル名/.style = {スタイル内容}}

ノードの表示方法など、いちいち設定するのが面倒なので冒頭でエイリアスとして宣言する。今回はスタイル名をhollow nodeとして、各ノードが大きさ1ptの○になるように設定した。circleが〇,drawで○を表示せよ、inner sep = 1.0で直径1を指定している。
ノードを表示させずに枝を交差させる方法はないのか色々試したのだが、今のところ解決策は見つかっていないので妥協策。0pt指定もできるが下限値が設定されているらしく、それを下回ると下限値の大きさの○が表示され逆に見栄えが悪くなる。

  • \tikzset{level x/.style = {level distance = y cm,sibling distance = z cm}}
  • \tikzset{end/.style = {hollow node}}

xは何段目のノードであるかを表す。根が1段目だ。この段以降はすべてこの設定にしたいというときはx+と書くことで実現できる。yは次の段のノードとの高さを表す。zは親から分岐する子がどれくらい離れているかを表す。今回はこれに加え先ほど定義したhollow nodeもスタイルに加えることでノードの様式指定も同時に行っている。
今回は最終的にどのノード間も1cmになるよう調節した。残念ながら手動で計算して適切に設定しないと枝が重なったり木がぐちゃぐちゃになってしまう。自動でそろえてくれるパッケージもあるのだが、僕の理想の形の木を作ることができなかったので断念した(今回でも大分妥協してる部分が大きいのだが…)
endは葉を表す。これ以上分岐もすることないのでノードの様式だけ指定して終了。

  • \begin{tikzpicture}[オプション]
  • \end{tikzpicture}

これで挟まれた間に木構造の記述をする。今回は木を左方向に伸ばしたいのでオプションにgrow = leftを指定した。右に伸ばすときはrightにすればいい

  • \node[オプション]{ノード内容}

ここからが本番。このコードは根の宣言だ。ここから木を伸ばしていくのだが、木の記述を終えたらセミコロン";"で閉じなければならない
疑似コード風に書くと以下のようにする。

\node[option]{concept}
  child{
    ....
  }
  child{
    ....
  }
  ...;    %木全体の記述が終わったことを";"によって宣言

根は一段目なのでオプションに先ほど設定したlevel 1を付け加える。ノードには何も表示させないのでノード内容は空にしている。
これから子供たちの宣言をするのだが、pythonを書いている時並みのインデントを意識した方がいい。その方が親子の対応関係が分かりやすくなるからだ。

child{
node[オプション]{ノード内容}
edge from parent node[オプション]{オプション}
}

\node{}またはnode{}の下に直接childを書き込むことで木を伸ばすことができる。childの中で宣言されるnodeにバックスラッシュをつける必要はない。
サンプルコードのように入れ子状に書いていくことで木は形成される。level 1の直下に宣言されたchildは当然レベル2なのでnodeのオプションにはlevel 2を宣言する。1回のchild宣言につき一個の子ノードが作られるため、親から複数の子を伸ばすときはその回数分宣言する。
node
child{....}
child{....}
 ....
といった感じだ。

  • node[label=位置指定子:{ラベル内容}]{ノード内容}

ノードの周りに説明を書きたい場合はオプションにラベルを指定する。場所指定子はノードの左の場合はleft、右ならright、上ならabove、下ならbelowを指定する。このとき木の成長方向は関係なく、ノードに対する絶対位置で指定されることに注意されたい。位置を指定したらコロン":"を挟んで{}の中にラベルの内容を記述する。今回の例では数式コマンドを使っているので当然$$で囲む必要がある。また葉に対してラベルを付けているのでオプションにendも追加している。

  • edge from parent node[オプション]{ノード内容}

これは枝の途中に説明を加えるための記述だ。今回の例では割り振られた符号語を枝に表示させるために書いた。
edge from parentの字面そのままで、親から伸びてきた枝に対して何かしますよと言っている。nodeのオプションにはauto,swapが使える。これは枝に対してどちらの側にノード内容を表示させるかを指定するものだ。基本的にはautoを指定すると、親から子へ伸びる方向に対して左側に出力される。右側に出力させたい場合はswapも追加で指定する。サンプルコードと実行結果を見比べながら理解してほしい。


以上を駆使して頑張って書くとハフマン符号の木が作れる。ここまで説明しておいてなんだが、inkscapeillustratorなどを使って描画して画像を埋め込んだ方が自分の理想の木を簡単に作れる。TeX上ですべて完結させようとするとそれなりの労力を強いられることになるのでよく考えよう。