Debian Codegraph @

texmf-dist/doc/metapost/huffman/huffman-doc-en.tex

raw
1
2 % LTeX: language=en
3
4 % huffman : draw binary huffman trees with MetaPost/MetaObj
5 %
6 % Originally written by Maxime Chupin <[email protected]>,
7 % 2023.
8 %
9 % Distributed under the terms of the GNU free documentation licence:
10 % http://www.gnu.org/licenses/fdl.html
11 % without any invariant section or cover text.
12
13 \documentclass[english]{ltxdoc}
14
15 \input{huffman-preamble}
16
17 \usepackage[english]{babel}
18
19 \makeindex[title=Command Index, columns=2]
20
21
22
23 %\lstset{moredelim=*[s][\color{red}\rmfamily\itshape]{<}{>}}
24 %\lstset{moredelim=*[s][\color{blue}\rmfamily\itshape]{<<}{>>}}
25
26 \begin{document}
27
28 \title{{Huffman} : drawing binary Huffman trees with \hologo{METAPOST} and \MO/}
29 \author{Maxime Chupin, \url{[email protected]}}
30 \date{\today}
31
32 %% === Page de garde ===================================================
33 \thispagestyle{empty}
34 \begin{tikzpicture}[remember picture, overlay]
35 \node[below right, shift={(-4pt,4pt)}] at (current page.north west) {%
36 \includegraphics{fond.pdf}%
37 };
38 \end{tikzpicture}%
39
40 \noindent
41 {\Huge \texttt{huffman}}\par\bigskip
42 \noindent
43 {\Large drawing binary Huffman trees \\[0.2cm]with \hologo{METAPOST} and \MO/}\\[1cm]
44 \parbox{0.6\textwidth}{
45 \begin{mplibcode}
46 input huffman
47
48 string charList[];
49 numeric frequency[];
50 show_bits:=false;
51 beginfig(1);
52 charList[4]:="a"; frequency[4]:=4;
53 charList[5]:="b"; frequency[5]:=5;
54 charList[3]:="c"; frequency[3]:=6;
55 charList[1]:="d"; frequency[1]:=7;
56 charList[2]:="e"; frequency[2]:=10;
57 charList[6]:="f"; frequency[6]:=10;
58 charList[7]:="g"; frequency[7]:=18;
59 charList[8]:="h"; frequency[8]:=40;
60 newBinHuffman.myHuff(8)(charList,frequency) "treemode(T)", "vbsep(0.3cm)";
61 myHuff.c=origin;
62 drawObj(myHuff);
63 endfig;
64 \end{mplibcode}
65 }\hfill
66 \parbox{0.5\textwidth}{\Large\raggedleft
67 \textbf{Contributor}\\
68 Maxime \textsc{Chupin}\\
69 \url{[email protected]}
70 }
71 \vfill
72 \begin{center}
73 Version 0.1, 2023, May, 10th \\
74 \url{https://plmlab.math.cnrs.fr/mchupin/huffman}
75 \end{center}
76 %% == Page de garde ====================================================
77 \newpage
78
79 %\maketitle
80
81 \begin{abstract}
82 This \hologo{METAPOST} package allows to draw binary Huffman trees from two
83 arrays : an arraw of strings, and an array of weights (\lstinline+numeric+).
84 It is based on the \MO/ package which
85 provides many tools to build trees in general.
86 \end{abstract}
87
88
89 \begin{center}
90 \url{https://plmlab.math.cnrs.fr/mchupin/huffman}
91 \url{https://github.com/chupinmaxime/huffman}
92 \end{center}
93
94 \tableofcontents
95
96 \bigskip
97
98 \begin{tcolorbox}[ arc=0pt,outer arc=0pt,
99 colback=darkred!3,
100 colframe=darkred,
101 breakable,
102 boxsep=0pt,left=5pt,right=5pt,top=5pt,bottom=5pt, bottomtitle =
103 3pt, toptitle=3pt,
104 boxrule=0pt,bottomrule=0.5pt,toprule=0.5pt, toprule at break =
105 0pt, bottomrule at break = 0pt,]
106 \itshape
107 This package is in beta version---do not hesitate to report bugs, as well as requests for improvement.
108 \end{tcolorbox}
109
110 \section{Installation}
111
112 \huffman is on \ctan{} and can also be installed via the package manager of your
113 distribution.
114
115 \begin{center}
116 \url{https://www.ctan.org/pkg/huffman}
117 \end{center}
118
119
120 \subsection{With \TeX live under Linux or macOS}
121
122 To install \huffman with \TeX Live, you will have to create the directory
123 \lstinline+texmf+ in your \lstinline+home+.
124
125 \begin{commandshell}
126 mkdir ~/texmf
127 \end{commandshell}
128
129 Then, you will have to place the \lstinline+huffman.mp+ file in
130 \begin{center}
131 \lstinline+~/texmf/metapost/huffman/+
132 \end{center}
133
134
135 Once this is done, \huffman will be loaded with the classic \MP{}
136 input code
137 \begin{mpcode}
138 input huffman
139 \end{mpcode}
140
141 \subsection{With Mik\TeX{} and Windows}
142
143 These two systems are unknown to the author of \huffman, so we
144 refer you to the Mik\TeX documentation concerning the addition of local packages:
145 \begin{center}
146 \url{http://docs.miktex.org/manual/localadditions.html}
147 \end{center}
148
149
150
151 \subsection{Dependencies}
152
153
154 \huffman depends, of course on \MP~\cite{ctan-metapost}, as well as the packages
155 \package{metaobj}~\cite{ctan-metaobj} and---if \huffman is not used with
156 \hologo{LuaLaTeX} and the \package{luamplib} package---the \package{latexmp}
157 package.
158
159 \section{Main Command}
160
161 The package \huffman provides one principal command (which is a \MO/ like
162 constructor):
163
164 \commande|newBinHuffman.«name»(«sizeofarrays»)(«symbarray»,«valuearray»)|\smallskip\index{newBinHuffman@\lstinline+newBinHuffman+}
165
166
167 \begin{description}
168 \item[\meta{name}:] is the name of the object;
169 \item[\meta{sizeofarrays}:] is the size (integer) of the arrays;
170 \item[\meta{symbarray}:] is the array of \lstinline+string+ containing the
171 symbols;
172 \item[\meta{valuearray}:] is the array of \lstinline+numeric+ containing the
173 weights associated to the symbols.
174 \end{description}
175
176 The data arrays should begin at index 1.
177
178 \begin{ExempleMP}
179 input huffman
180
181 beginfig(0);
182 string charList[];
183 numeric frequency[];
184 charList[1]:="a"; frequency[1]:=0.04;
185 charList[2]:="b"; frequency[2]:=0.05;
186 charList[3]:="c"; frequency[3]:=0.06;
187 charList[4]:="d"; frequency[4]:=0.07;
188 charList[5]:="e"; frequency[5]:=0.1;
189 charList[6]:="f"; frequency[6]:=0.1;
190 charList[7]:="g"; frequency[7]:=0.18;
191 charList[8]:="h"; frequency[8]:=0.4;
192
193 newBinHuffman.myHuff(8)(charList,frequency);
194 myHuff.c=origin;
195 drawObj(myHuff);
196 endfig;
197 \end{ExempleMP}
198
199 Note that the symbols are composed in mathematical \TeX{} mode.
200 \section{Package Options}
201
202 You can modify the size of the internal nodes of the tree with the following
203 command:
204
205 \commande|set_node_size(«dim»)|\smallskip\index{set_node_size@\lstinline+set_node_size+}
206 \begin{description}
207 \item[\meta{dim}:] is the diameter with unit of the circle (default: 13pt).
208 \end{description}
209
210 You can change the color for the symbol boxes with the following command:
211
212 \commande|set_leaf_color(«color»)|\smallskip\index{set_leaf_color@\lstinline+set_leaf_color+}
213 \begin{description}
214 \item[\meta{color}:] is a \hologo{METAPOST} \lstinline+color+.
215 \end{description}
216
217 You can hide the bit values printed on the edges of the tree with the following
218 boolean
219 (\lstinline+true+ by default):
220
221 \commande|show_bits|\smallskip\index{show_bits@\lstinline+show_bits+}
222
223 Similarly, you can set the following boolean to \lstinline+false+ to hide the
224 node values:
225
226 \commande|show_node_values|\smallskip\index{show_node_values@\lstinline+show_node_values+}
227
228 Finally, you can set the following boolean to \lstinline+false+ to hide the
229 leaf values:
230
231 \commande|show_leaf_values|\smallskip\index{show_leaf_values@\lstinline+show_leaf_values+}
232
233 Here an example combining all these commands and variables.
234
235 \begin{ExempleMP}
236 input huffman
237
238 beginfig(0);
239 string charList[];
240 numeric frequency[];
241 charList[1]:="s_1"; frequency[1]:=2;
242 charList[2]:="s_2"; frequency[2]:=4;
243 charList[3]:="s_3"; frequency[3]:=2;
244 charList[4]:="s_4"; frequency[4]:=12;
245 charList[5]:="s_5"; frequency[5]:=8;
246
247 set_leaf_color(0.2[white,green]);
248 set_node_size(8pt);
249 show_bits:=false;
250 show_node_values:=false;
251 show_leaf_values:=false;
252 newBinHuffman.myHuff(5)(charList,frequency);
253 myHuff.c=origin;
254 drawObj(myHuff);
255 endfig;
256 \end{ExempleMP}
257
258
259
260 \section{\MO/ Tree Options}
261
262 Because the Huffman tree is built using the \MO/ tree constructor, the \MO/ tree
263 options are available. All of them are not well suited for this application
264 mostly because the Huffman tree is built using elementary trees. The
265 options we give to the Huffman constructor are passed to all the subtrees.
266
267 We give in table~\ref{tab:options} the \MO/ options for the trees that could be
268 used for the Huffman constructor.
269
270 \begin{table}[ht]
271 \centering\small
272 \begin{tabular}{HHHp{5.5cm}}
273 \toprule
274 Option & Type & Default & Description \\
275 \midrule
276 treemode & string & "D" & direction in which the tree develops; there are
277 four different possible values: \lstinline+"D"+ (default),
278 \lstinline+"U"+, \lstinline+"L"+ and \lstinline+"R"+\\
279 treeflip & boolean & false & if true, reverses the order of the subtrees\\
280 treenodehsize & numeric & -1pt & if non-negative, all the nodes are assumed to
281 have this width\\
282 treenodevsize & numeric & -1pt & if non-negative, all the nodes are assumed to
283 have this height\\
284 dx & numeric & 0 & horizontal clearance around the tree\\
285 dy & numeric & 0 & vertical clearance around the tree\\
286 hsep & numeric & 1cm & for a horizontal tree, this is the separation be-
287 tween the root and the subtrees\\
288 vsep & numeric & 1cm & for a vertical tree, this is the separation be-
289 tween the root and the subtrees\\
290 hbsep & numeric & 1cm &for a vertical tree, this is the horizontal separation between subtrees;
291 the subtrees are actually put in a \lstinline+HBox+ and the value of this
292 option is passed to the \lstinline+HBox+ constructor\\
293 vbsep & numeric & 1cm & for an horizontal tree, this is the vertical separation between subtrees;
294 the subtrees are actually put in a \lstinline+HBox+ and the value of this
295 option is passed to the \lstinline+HBox+ constructor\\
296 edge & string & "ncline" & name of a connection command (se \MO/
297 documentation)
298 \\
299 Dalign & string & "top" & vertical alignment of subtrees for trees that go
300 down (the root on the top); the other possible
301 values are \lstinline+"center"+ and \lstinline+"bot"+\\
302 \bottomrule
303 \end{tabular}
304 \caption{Table of \MO/ tree options.}\label{tab:options}
305 \end{table}
306
307 Here is an example using some of these options.
308
309 \begin{ExempleMP}
310 input huffman
311
312 beginfig(0);
313 string charList[];
314 numeric frequency[];
315 charList[1]:="s_1"; frequency[1]:=2;
316 charList[2]:="s_2"; frequency[2]:=4;
317 charList[3]:="s_3"; frequency[3]:=2;
318 charList[4]:="s_4"; frequency[4]:=12;
319 charList[5]:="s_5"; frequency[5]:=8;
320
321 newBinHuffman.myHuff(5)(charList,frequency)
322 "treemode(R)","treeflip(true)","hsep(1.5cm)", "edge(nccurve)" , "angleA(0)", "angleB(0)";
323 myHuff.c=origin;
324 drawObj(myHuff);
325 endfig;
326 \end{ExempleMP}
327
328 \section{Access to Nodes and Leaves}
329
330 To access the nodes and the leaves, you can use the \lstinline+treeroot+ command
331 from \MO/, see the documentation for details.
332
333 \commande|ntreepos(Obj(«name»))(«int»,«int»,etc.)|\smallskip\index{ntreepos@\lstinline+ntreepos+}
334
335 The sequence of \meta{int} gives the choice of branch where the children are
336 numbered from 1 to $n$.
337
338 The following example shows a use of this mecanism.
339 \begin{ExempleMP}
340 input huffman;
341 beginfig(0);
342 string charList[];
343 numeric frequency[];
344 charList[1]:="s_1"; frequency[1]:=2;
345 charList[2]:="s_2"; frequency[2]:=4;
346 charList[3]:="s_3"; frequency[3]:=2;
347 charList[4]:="s_4"; frequency[4]:=12;
348 charList[5]:="s_5"; frequency[5]:=8;
349
350 newBinHuffman.myHuff(5)(charList,frequency);
351 myHuff.c=origin;
352 ncarcbox(ntreepos(Obj(myHuff))(2,1,2))(ntreepos(Obj(myHuff))(2,2))
353 "linestyle(dashed evenly)", "nodesepA(5mm)", "nodesepB(5mm)" ;
354 drawObj(myHuff);
355 endfig;
356 \end{ExempleMP}
357
358 Of course, this can only be used in two steps, first build the tree, then
359 annotate it.
360
361 You can also access the leaves and the nodes using names. During the
362 construction of the tree, names are given to leaves and nodes. Because you may
363 want to build several Huffman trees, the trees are numbered. You can get the
364 current tree number with the following command:
365
366 \commande|get_huffmanTreeNbr()|\smallskip\index{get_huffmanTreeNbr@\lstinline+get_huffmanTreeNbr+}
367
368 The leaves are numbered during the construction, and the corresponding \MO/
369 object is named as follows:
370
371 \commande|leaf«leaf number»_«tree number»|\smallskip
372
373 The nodes are numbered during the construction, and the corresponding \MO/
374 object is named as follows:
375
376 \commande|node«node number»_«tree number»|\smallskip
377
378 Thanks to \MO/ you can annotate the tree using all the tools \MO/ provides.
379
380 \begin{ExempleMP}
381 input huffman;
382 beginfig(0);
383 string charList[];
384 numeric frequency[];
385 charList[1]:="s_1"; frequency[1]:=2;
386 charList[2]:="s_2"; frequency[2]:=4;
387 charList[3]:="s_3"; frequency[3]:=2;
388 charList[4]:="s_4"; frequency[4]:=12;
389 charList[5]:="s_5"; frequency[5]:=8;
390
391 newBinHuffman.myHuff(5)(charList,frequency);
392 myHuff.c=origin;
393 ncarcbox(node2_1)(leaf4_1)
394 "linestyle(dashed evenly)", "nodesepA(5mm)", "nodesepB(5mm)" ;
395 drawObj(myHuff);
396 endfig;
397 \end{ExempleMP}
398
399
400
401
402
403
404
405
406 \section{Constructors}
407
408 The Huffman algorithm uses only three constructors that you can redefine to adapt
409 the tree to your needs. Here are the three constructors (roughly commented in
410 French) defined in this package. We will not discuss the code here but
411 you are free to redefine and adapt it.
412
413 \begin{mpcode}[title={Leaf Code}]
414 % style d’une feuille caractère et proba
415 vardef newHuffmanLeaf@#(expr ch)(expr v) text options=
416 % @# est l’identifiant de la feuille
417 % c est le caractère considéré (ou la chaine)
418 % v est la proba ou l’entier associé
419 save _text_v,
420 _text_token,_height_v,_height_token,_height_max,_width_token,_width_v;
421 picture _text_v,_text_token;
422 % on calcule le height max des deux écritures pour faire deux boites de même
423 % hauteur
424 _text_v := textext(v);
425 _text_token := textext("$"&ch&"$");
426 _height_v := abs((ulcorner _text_v) - (llcorner _text_v));
427 _width_v := abs(urcorner _text_v - ulcorner _text_v);
428 _height_token := abs(ulcorner _text_token - llcorner _text_token);
429 _width_token := abs(urcorner _text_token - ulcorner _text_token);
430 _height_max := max(_height_token,_height_v);
431 % on fabrique deux boîtes vides aux bonne dimensions
432 % et on ajoute un label au centre de celles-ci
433 if(show_leaf_values):
434 newEmptyBox.scantokens(str @# & "ch1")(_width_token+4,2_height_max)
435 "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options;
436 ObjLabel.Obj(scantokens(str @# & "ch1"))(textext("$" & ch & "$"));
437 newEmptyBox.scantokens(str @# & "ch2")(_width_v+4,2_height_max)
438 "framed(true)", options;
439 ObjLabel.Obj(scantokens(str @# & "ch2"))(textext(v));
440 % on fixe relativement les coordonnées des deux boites pour qu’elles se % touchent
441 scantokens(str @# & "ch1").e=scantokens(str @# & "ch2").w;
442 % on fabrique un container qui les regroupes et qui sera la feuille
443 newContainer.@#(scantokens(str @# & "ch1"),scantokens(str @# & "ch2"));
444 else:
445 % si seulement le symbole
446 newBox.@#(textext("$" & ch & "$"))
447 "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options;
448 fi
449 enddef;
450 \end{mpcode}
451
452
453 \begin{mpcode}[title={Node Code}]
454 % style d’un nœud interne (non feuille) de l’arbre
455 vardef newHuffmanNode@#(expr v) text options=
456 newCircle.@#("") "circmargin(_node_size)",options;
457 if(show_node_values):
458 ObjLabel.Obj(scantokens(str @#))(textext(v));
459 fi
460 enddef;
461 \end{mpcode}
462
463 \begin{mpcode}[title={Tree Code}]
464 % style de l’arbre binaire de Huffman
465 vardef newHuffmanBinTree@#(suffix theroot)(text subtrees) text options=
466 % un simple arbre
467 newTree.@#(theroot)(subtrees) "Dalign(top)" , "hbsep(0.3cm)",options;
468 if(show_bits):
469 % et on met 0 et 1 sur ses deux connections
470 ObjLabel.Obj(@#)(btex 0 etex)
471 "labpathid(1)", "laberase(true)", "labcolor(_huffmanBit)";
472 ObjLabel.Obj(@#)(btex 1 etex)
473 "labpathid(2)", "laberase(true)", "labcolor(_huffmanBit)";
474 fi
475 enddef;
476 \end{mpcode}
477
478 \printbibliography
479 \printindex
480 \end{document}