% LTeX: language=en % huffman : draw binary huffman trees with MetaPost/MetaObj % % Originally written by Maxime Chupin , % 2023. % % Distributed under the terms of the GNU free documentation licence: % http://www.gnu.org/licenses/fdl.html % without any invariant section or cover text. \documentclass[english]{ltxdoc} \input{huffman-preamble} \usepackage[english]{babel} \makeindex[title=Command Index, columns=2] %\lstset{moredelim=*[s][\color{red}\rmfamily\itshape]{<}{>}} %\lstset{moredelim=*[s][\color{blue}\rmfamily\itshape]{<<}{>>}} \begin{document} \title{{Huffman} : drawing binary Huffman trees with \hologo{METAPOST} and \MO/} \author{Maxime Chupin, \url{notezik@gmail.com}} \date{\today} %% === Page de garde =================================================== \thispagestyle{empty} \begin{tikzpicture}[remember picture, overlay] \node[below right, shift={(-4pt,4pt)}] at (current page.north west) {% \includegraphics{fond.pdf}% }; \end{tikzpicture}% \noindent {\Huge \texttt{huffman}}\par\bigskip \noindent {\Large drawing binary Huffman trees \\[0.2cm]with \hologo{METAPOST} and \MO/}\\[1cm] \parbox{0.6\textwidth}{ \begin{mplibcode} input huffman string charList[]; numeric frequency[]; show_bits:=false; beginfig(1); charList[4]:="a"; frequency[4]:=4; charList[5]:="b"; frequency[5]:=5; charList[3]:="c"; frequency[3]:=6; charList[1]:="d"; frequency[1]:=7; charList[2]:="e"; frequency[2]:=10; charList[6]:="f"; frequency[6]:=10; charList[7]:="g"; frequency[7]:=18; charList[8]:="h"; frequency[8]:=40; newBinHuffman.myHuff(8)(charList,frequency) "treemode(T)", "vbsep(0.3cm)"; myHuff.c=origin; drawObj(myHuff); endfig; \end{mplibcode} }\hfill \parbox{0.5\textwidth}{\Large\raggedleft \textbf{Contributor}\\ Maxime \textsc{Chupin}\\ \url{notezik@gmail.com} } \vfill \begin{center} Version 0.1, 2023, May, 10th \\ \url{https://plmlab.math.cnrs.fr/mchupin/huffman} \end{center} %% == Page de garde ==================================================== \newpage %\maketitle \begin{abstract} This \hologo{METAPOST} package allows to draw binary Huffman trees from two arrays : an arraw of strings, and an array of weights (\lstinline+numeric+). It is based on the \MO/ package which provides many tools to build trees in general. \end{abstract} \begin{center} \url{https://plmlab.math.cnrs.fr/mchupin/huffman} \url{https://github.com/chupinmaxime/huffman} \end{center} \tableofcontents \bigskip \begin{tcolorbox}[ arc=0pt,outer arc=0pt, colback=darkred!3, colframe=darkred, breakable, boxsep=0pt,left=5pt,right=5pt,top=5pt,bottom=5pt, bottomtitle = 3pt, toptitle=3pt, boxrule=0pt,bottomrule=0.5pt,toprule=0.5pt, toprule at break = 0pt, bottomrule at break = 0pt,] \itshape This package is in beta version---do not hesitate to report bugs, as well as requests for improvement. \end{tcolorbox} \section{Installation} \huffman is on \ctan{} and can also be installed via the package manager of your distribution. \begin{center} \url{https://www.ctan.org/pkg/huffman} \end{center} \subsection{With \TeX live under Linux or macOS} To install \huffman with \TeX Live, you will have to create the directory \lstinline+texmf+ in your \lstinline+home+. \begin{commandshell} mkdir ~/texmf \end{commandshell} Then, you will have to place the \lstinline+huffman.mp+ file in \begin{center} \lstinline+~/texmf/metapost/huffman/+ \end{center} Once this is done, \huffman will be loaded with the classic \MP{} input code \begin{mpcode} input huffman \end{mpcode} \subsection{With Mik\TeX{} and Windows} These two systems are unknown to the author of \huffman, so we refer you to the Mik\TeX documentation concerning the addition of local packages: \begin{center} \url{http://docs.miktex.org/manual/localadditions.html} \end{center} \subsection{Dependencies} \huffman depends, of course on \MP~\cite{ctan-metapost}, as well as the packages \package{metaobj}~\cite{ctan-metaobj} and---if \huffman is not used with \hologo{LuaLaTeX} and the \package{luamplib} package---the \package{latexmp} package. \section{Main Command} The package \huffman provides one principal command (which is a \MO/ like constructor): \commande|newBinHuffman.«name»(«sizeofarrays»)(«symbarray»,«valuearray»)|\smallskip\index{newBinHuffman@\lstinline+newBinHuffman+} \begin{description} \item[\meta{name}:] is the name of the object; \item[\meta{sizeofarrays}:] is the size (integer) of the arrays; \item[\meta{symbarray}:] is the array of \lstinline+string+ containing the symbols; \item[\meta{valuearray}:] is the array of \lstinline+numeric+ containing the weights associated to the symbols. \end{description} The data arrays should begin at index 1. \begin{ExempleMP} input huffman beginfig(0); string charList[]; numeric frequency[]; charList[1]:="a"; frequency[1]:=0.04; charList[2]:="b"; frequency[2]:=0.05; charList[3]:="c"; frequency[3]:=0.06; charList[4]:="d"; frequency[4]:=0.07; charList[5]:="e"; frequency[5]:=0.1; charList[6]:="f"; frequency[6]:=0.1; charList[7]:="g"; frequency[7]:=0.18; charList[8]:="h"; frequency[8]:=0.4; newBinHuffman.myHuff(8)(charList,frequency); myHuff.c=origin; drawObj(myHuff); endfig; \end{ExempleMP} Note that the symbols are composed in mathematical \TeX{} mode. \section{Package Options} You can modify the size of the internal nodes of the tree with the following command: \commande|set_node_size(«dim»)|\smallskip\index{set_node_size@\lstinline+set_node_size+} \begin{description} \item[\meta{dim}:] is the diameter with unit of the circle (default: 13pt). \end{description} You can change the color for the symbol boxes with the following command: \commande|set_leaf_color(«color»)|\smallskip\index{set_leaf_color@\lstinline+set_leaf_color+} \begin{description} \item[\meta{color}:] is a \hologo{METAPOST} \lstinline+color+. \end{description} You can hide the bit values printed on the edges of the tree with the following boolean (\lstinline+true+ by default): \commande|show_bits|\smallskip\index{show_bits@\lstinline+show_bits+} Similarly, you can set the following boolean to \lstinline+false+ to hide the node values: \commande|show_node_values|\smallskip\index{show_node_values@\lstinline+show_node_values+} Finally, you can set the following boolean to \lstinline+false+ to hide the leaf values: \commande|show_leaf_values|\smallskip\index{show_leaf_values@\lstinline+show_leaf_values+} Here an example combining all these commands and variables. \begin{ExempleMP} input huffman beginfig(0); string charList[]; numeric frequency[]; charList[1]:="s_1"; frequency[1]:=2; charList[2]:="s_2"; frequency[2]:=4; charList[3]:="s_3"; frequency[3]:=2; charList[4]:="s_4"; frequency[4]:=12; charList[5]:="s_5"; frequency[5]:=8; set_leaf_color(0.2[white,green]); set_node_size(8pt); show_bits:=false; show_node_values:=false; show_leaf_values:=false; newBinHuffman.myHuff(5)(charList,frequency); myHuff.c=origin; drawObj(myHuff); endfig; \end{ExempleMP} \section{\MO/ Tree Options} Because the Huffman tree is built using the \MO/ tree constructor, the \MO/ tree options are available. All of them are not well suited for this application mostly because the Huffman tree is built using elementary trees. The options we give to the Huffman constructor are passed to all the subtrees. We give in table~\ref{tab:options} the \MO/ options for the trees that could be used for the Huffman constructor. \begin{table}[ht] \centering\small \begin{tabular}{HHHp{5.5cm}} \toprule Option & Type & Default & Description \\ \midrule treemode & string & "D" & direction in which the tree develops; there are four different possible values: \lstinline+"D"+ (default), \lstinline+"U"+, \lstinline+"L"+ and \lstinline+"R"+\\ treeflip & boolean & false & if true, reverses the order of the subtrees\\ treenodehsize & numeric & -1pt & if non-negative, all the nodes are assumed to have this width\\ treenodevsize & numeric & -1pt & if non-negative, all the nodes are assumed to have this height\\ dx & numeric & 0 & horizontal clearance around the tree\\ dy & numeric & 0 & vertical clearance around the tree\\ hsep & numeric & 1cm & for a horizontal tree, this is the separation be- tween the root and the subtrees\\ vsep & numeric & 1cm & for a vertical tree, this is the separation be- tween the root and the subtrees\\ hbsep & numeric & 1cm &for a vertical tree, this is the horizontal separation between subtrees; the subtrees are actually put in a \lstinline+HBox+ and the value of this option is passed to the \lstinline+HBox+ constructor\\ vbsep & numeric & 1cm & for an horizontal tree, this is the vertical separation between subtrees; the subtrees are actually put in a \lstinline+HBox+ and the value of this option is passed to the \lstinline+HBox+ constructor\\ edge & string & "ncline" & name of a connection command (se \MO/ documentation) \\ Dalign & string & "top" & vertical alignment of subtrees for trees that go down (the root on the top); the other possible values are \lstinline+"center"+ and \lstinline+"bot"+\\ \bottomrule \end{tabular} \caption{Table of \MO/ tree options.}\label{tab:options} \end{table} Here is an example using some of these options. \begin{ExempleMP} input huffman beginfig(0); string charList[]; numeric frequency[]; charList[1]:="s_1"; frequency[1]:=2; charList[2]:="s_2"; frequency[2]:=4; charList[3]:="s_3"; frequency[3]:=2; charList[4]:="s_4"; frequency[4]:=12; charList[5]:="s_5"; frequency[5]:=8; newBinHuffman.myHuff(5)(charList,frequency) "treemode(R)","treeflip(true)","hsep(1.5cm)", "edge(nccurve)" , "angleA(0)", "angleB(0)"; myHuff.c=origin; drawObj(myHuff); endfig; \end{ExempleMP} \section{Access to Nodes and Leaves} To access the nodes and the leaves, you can use the \lstinline+treeroot+ command from \MO/, see the documentation for details. \commande|ntreepos(Obj(«name»))(«int»,«int»,etc.)|\smallskip\index{ntreepos@\lstinline+ntreepos+} The sequence of \meta{int} gives the choice of branch where the children are numbered from 1 to $n$. The following example shows a use of this mecanism. \begin{ExempleMP} input huffman; beginfig(0); string charList[]; numeric frequency[]; charList[1]:="s_1"; frequency[1]:=2; charList[2]:="s_2"; frequency[2]:=4; charList[3]:="s_3"; frequency[3]:=2; charList[4]:="s_4"; frequency[4]:=12; charList[5]:="s_5"; frequency[5]:=8; newBinHuffman.myHuff(5)(charList,frequency); myHuff.c=origin; ncarcbox(ntreepos(Obj(myHuff))(2,1,2))(ntreepos(Obj(myHuff))(2,2)) "linestyle(dashed evenly)", "nodesepA(5mm)", "nodesepB(5mm)" ; drawObj(myHuff); endfig; \end{ExempleMP} Of course, this can only be used in two steps, first build the tree, then annotate it. You can also access the leaves and the nodes using names. During the construction of the tree, names are given to leaves and nodes. Because you may want to build several Huffman trees, the trees are numbered. You can get the current tree number with the following command: \commande|get_huffmanTreeNbr()|\smallskip\index{get_huffmanTreeNbr@\lstinline+get_huffmanTreeNbr+} The leaves are numbered during the construction, and the corresponding \MO/ object is named as follows: \commande|leaf«leaf number»_«tree number»|\smallskip The nodes are numbered during the construction, and the corresponding \MO/ object is named as follows: \commande|node«node number»_«tree number»|\smallskip Thanks to \MO/ you can annotate the tree using all the tools \MO/ provides. \begin{ExempleMP} input huffman; beginfig(0); string charList[]; numeric frequency[]; charList[1]:="s_1"; frequency[1]:=2; charList[2]:="s_2"; frequency[2]:=4; charList[3]:="s_3"; frequency[3]:=2; charList[4]:="s_4"; frequency[4]:=12; charList[5]:="s_5"; frequency[5]:=8; newBinHuffman.myHuff(5)(charList,frequency); myHuff.c=origin; ncarcbox(node2_1)(leaf4_1) "linestyle(dashed evenly)", "nodesepA(5mm)", "nodesepB(5mm)" ; drawObj(myHuff); endfig; \end{ExempleMP} \section{Constructors} The Huffman algorithm uses only three constructors that you can redefine to adapt the tree to your needs. Here are the three constructors (roughly commented in French) defined in this package. We will not discuss the code here but you are free to redefine and adapt it. \begin{mpcode}[title={Leaf Code}] % style d’une feuille caractère et proba vardef newHuffmanLeaf@#(expr ch)(expr v) text options= % @# est l’identifiant de la feuille % c est le caractère considéré (ou la chaine) % v est la proba ou l’entier associé save _text_v, _text_token,_height_v,_height_token,_height_max,_width_token,_width_v; picture _text_v,_text_token; % on calcule le height max des deux écritures pour faire deux boites de même % hauteur _text_v := textext(v); _text_token := textext("$"&ch&"$"); _height_v := abs((ulcorner _text_v) - (llcorner _text_v)); _width_v := abs(urcorner _text_v - ulcorner _text_v); _height_token := abs(ulcorner _text_token - llcorner _text_token); _width_token := abs(urcorner _text_token - ulcorner _text_token); _height_max := max(_height_token,_height_v); % on fabrique deux boîtes vides aux bonne dimensions % et on ajoute un label au centre de celles-ci if(show_leaf_values): newEmptyBox.scantokens(str @# & "ch1")(_width_token+4,2_height_max) "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options; ObjLabel.Obj(scantokens(str @# & "ch1"))(textext("$" & ch & "$")); newEmptyBox.scantokens(str @# & "ch2")(_width_v+4,2_height_max) "framed(true)", options; ObjLabel.Obj(scantokens(str @# & "ch2"))(textext(v)); % on fixe relativement les coordonnées des deux boites pour qu’elles se % touchent scantokens(str @# & "ch1").e=scantokens(str @# & "ch2").w; % on fabrique un container qui les regroupes et qui sera la feuille newContainer.@#(scantokens(str @# & "ch1"),scantokens(str @# & "ch2")); else: % si seulement le symbole newBox.@#(textext("$" & ch & "$")) "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options; fi enddef; \end{mpcode} \begin{mpcode}[title={Node Code}] % style d’un nœud interne (non feuille) de l’arbre vardef newHuffmanNode@#(expr v) text options= newCircle.@#("") "circmargin(_node_size)",options; if(show_node_values): ObjLabel.Obj(scantokens(str @#))(textext(v)); fi enddef; \end{mpcode} \begin{mpcode}[title={Tree Code}] % style de l’arbre binaire de Huffman vardef newHuffmanBinTree@#(suffix theroot)(text subtrees) text options= % un simple arbre newTree.@#(theroot)(subtrees) "Dalign(top)" , "hbsep(0.3cm)",options; if(show_bits): % et on met 0 et 1 sur ses deux connections ObjLabel.Obj(@#)(btex 0 etex) "labpathid(1)", "laberase(true)", "labcolor(_huffmanBit)"; ObjLabel.Obj(@#)(btex 1 etex) "labpathid(2)", "laberase(true)", "labcolor(_huffmanBit)"; fi enddef; \end{mpcode} \printbibliography \printindex \end{document}