summaryrefslogtreecommitdiff
path: root/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.tex
blob: b6d1a42cb33d0c819093120d9dee44918391a78a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480

% LTeX: language=en

% huffman : draw binary huffman trees with MetaPost/MetaObj
%
% Originally written by Maxime Chupin <notezik@gmail.com>,
% 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}