Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this community
I want to make Huffman coding with Mathematica. I saw a demonstration, but it is not the thing I want to make. I want to show the tree for given string. Here is an example picture:
You can see the demonstration from here. This demonstration looks very atractive but difficult. However, I believe at least, making step by step should be possible.
Wagner, in "Power Programming with Mathematica", pp 118-126, has a whole section on Huffman encoding, and the following relies very heavily on his implementation of the Huffman algorithm.
Huffman encoding is a prefix-free, variable-length encoding where characters with a higher frequency are represented by fewer bits.
The algorithm may be implemented by counting the frequencies of all characters, combining the characters with the two lowest frequencies into a new entity whose frequency is the sum of the individual frequencies, substituting the new entity for the individual components, and continuing iteratively until a single entity is obtained (referred to as a Huffman expression below). (Wagner, p121)
data="COMPRESSION_IS_COOL";
Some preliminaries. A sorted list of character frequencies may be obtained as follows:
sortTally[msg_]:=SortBy[Reverse/@Tally[Characters[msg]],First]
freqs=sortTally[data]
(* {{1, E}, {1, L}, {1, M}, {1, N}, {1, P}, {1, R}, {2, _}, {2, C},
{2, I}, {3, S}, {4, O}} *)
Union@Characters@data//{Length@#,#}&
(* {11, {_, C, E, I, L, M, N, O, P, R, S}} *)
huffmanExpression[msg_String]:=FixedPoint[
If[Length[#] < 2,
#,
Union[Drop[#,2],{MapAt[Total, Transpose[Take[#,2]],{1}]}]
]&,
SortBy[Reverse/@Tally[Characters[msg]],First]
]
huffmanExpression is a modification of Wagner's combine (1.11 Step-by-Step). It splits the input string into characters, then iteratively combines entities with the two lowest frequencies into a single entity, continuing until a single combined entity (or 'Huffman expression') is obtained.
dataExpression = huffmanExpression[data]
(* {{19, {{{_, C}, {I, {E, L}}}, {{{M, N}, {P, R}}, {S, O}}}}} *)
The integer in the first position of dataExpression (strictly Part[#,1,1]&) gives the sum of the frequencies of all characters.
Subtracting 1 from the position of any character in the second part of dataExpression (strictly Part[#,1,2]&) gives the Huffman code for that character (Wagner, p122).
Position[Part[dataExpression,1,2],"C"] - 1
(* {{0, 0, 1}} *)
The binary tree associated with dataExpression may be visualized with ExpressionTree.
tree=ExpressionTree[dataExpression[[1,2]],"Atoms"]
The Huffman code for any character may be obtained from the binary tree: start at the root, write 0 for each left branch taken, and 1 for each right branch taken, and continue, concatenating the values, until the character is reached.
Alternatively, the binary tree may be used to decode using the same procedure: 001 encodes C, for example.
Huffman encoding produces a binary tree where every node has two children and minimum redundancy is achieved by first assigning longer codes to the least frequent characters. Thus, characters with higher frequencies tend to occur towards the top of the binary tree.
huffmanExpressionFull[msg_String]:=FixedPoint[
If[Length[#] < 2,
#,
Union[Drop[#,2],{MapAt[Total, Transpose[Take[#,2]],{1}]/.{x_,{y__}}->{x,x[y]}}]
]&,
SortBy[Reverse/@Tally[Characters[msg]],First]
]
Although Huffman encoding is lossless, the previous Huffman expression (dataExpression) may be considered 'lossy' as intermediate frequency totals (or node weights) are discarded.
huffmanExpressionFull attempts to solve this problem by giving the Huffman expression in a form similar to that obtained with TreeExpression, where the Head of the intermediary expressions is the cumulated frequency rather than List:
dataExpressionFull=huffmanExpressionFull[data]
(* {{19, 19[8[4[_, C], 4[I, 2[E, L]]], 11[4[2[M, N], 2[P, R]], 7[S, O]]]}} *)
For comparison:
TreeExpression@RulesTree[a -> {b, c -> {d, e}, f, g}]
(* a[b, c[d, e], f, g] *)
The individual steps leading to dataExpressionFull are shown in (1.11 Step-by-Step).
tree=ExpressionTree[dataExpressionFull[[1,2]]];
vertices=TreeFold[List,ExpressionTree[huffmanExpressionFull[data] [[1,2]]]]//Flatten;
vertexTransformationRules=Thread[
#[[All,2]]->#/. {x_Integer/;x>1,y_String}:>y<>"("<>ToString[x]<>")"]&@Select[
freqs,#[[1]]>1&];
ExpressionTree[TreeExpression@tree/.vertexTransformationRules]
tree is a full binary tree (rendered as an ExpressionTree) where the cumulative frequency (or weight) of each node is shown, and where the frequency of elements greater than one is shown in parentheses.
The full binary tree rendered as an ExpressionGraph:
placedVertices=If[IntegerQ[#],
Placed[#,Above], Placed[#,Below]]&/@(vertices/.vertexTransformationRules);
ExpressionGraph[dataExpression[[1,2]], VertexSize->0.25,
VertexStyle->Blue,VertexLabels -> Thread[Range[21]-> placedVertices]]
huffmanEncode[huffmanExpression_List,character_String]:=Position[huffmanExpression[[1,2]],
character][[1]]-1
huffmanEncodeAll[huffmanExpression_, msg_]:=(Flatten[huffmanEncode[MapApply[Sequence,
{huffmanExpression}],#]&/@Characters[msg]])
huffmanEncode The character code is obtained by subtracting 1 from the Position of that character in the Huffman expression (1.2 Huffman Encoding).
For example:
huffmanEncode[dataExpressionFull, #]&/@{"C","O","M"}
(* {{0, 0, 1}, {1, 1, 1}, {1, 0, 0, 0}} *)
huffmanEncodeAll takes the full message (as a string) as second argument.
encodedData=huffmanEncodeAll[dataExpression,data]
(*
{0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1,
1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0,
0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0,
1, 1, 1}
*)
Length@encodedData
(* 63 *)
As the total number of characters in data is 11 (1.1 Frequencies), a minimum 4-bit fixed length code is required. As there are 19 entities to encode, the length of a 4-bit fixed-length encoding will be 76 (see Wagner pp 118-120). Huffman encoding is shorter by 13 bits.
huffmanDecode[huffmanExpression_List, binaryList_List]:= Extract[huffmanExpression[[1,2]],
binaryList + 1]
huffmanDecodeAll[huffmanExpression_List,encodedText_]:=StringJoin[
(Fold[
Block[{a,newstate = Append[#1,#2]},
If[StringQ[a = Extract[huffmanExpression[[1,2]], newstate+1]],
Sow[a];{},
(*else*)
newstate
](*If*)
](*Block*)&,
{},encodedText](*Fold*)//Reap)[[2,1]]
](*StringJoin*)
huffmanDecode The character corresponding to the Huffman code may be obtained programmatically by adding 1 to the binary list, and using Extract to obtain the character from the appropiate Huffman expression (Wagner, p 123).
Huffman codes are prefix-free. Decoding may be achieved by stepping through the binary tree where the step direction is determined by the binary sequence: take the left branch on 0 and the right branch on 1, continue until a character is encountered, remember the result, and then start again from the root node.
Wagner (p 123) has likened the procedure to the operation of a finite state machine where the binary tree (or the Huffman expression) acts as transition table and the current position within the binary tree (or the Huffman expression) is that state of the machine.
huffmanDecodeAll, which is merely a modification of Wagner's elegant trans function (Wagner, p 124) , may be though of as operating as a state machine: The initial state-list is set to the empty set, and the function steps though the encoded binary list character-by-character, calling Extract on the Huffman expression with the state-list as second argument. If the entity returned by Extract is a string, Sow is called on the result and the state-list is reset to the empty set; otherwise the character is appended to the state-list.
huffmanDecode[dataExpression, {0,0,1}]
(* "C" *)
decodedData=huffmanDecodeAll[dataExpressionFull,encodedData]
(* COMPRESSION_IS_COOL *)
A modification of huffmanDecodeAll, which returns the state-list at each step, as well as the decoded character (huffmanDecodeAllList), is given in (1.11 Step-by-Step)
TableForm[SortBy[Join[SortBy[freqs,Last],huffmanEncode[dataExpression,
#]&/@(SortBy[freqs,Last][[All,2]]),2],First],
TableHeadings -> {None,{"Freq", "Char"}}]//TeXForm
$$\begin{array}{cccccc} \text{Freq} & \text{Char} & \text{} & \text{} & \text{} & \text{} \\ 1 & \text{E} & 0 & 1 & 1 & 0 \\ 1 & \text{L} & 0 & 1 & 1 & 1 \\ 1 & \text{M} & 1 & 0 & 0 & 0 \\ 1 & \text{N} & 1 & 0 & 0 & 1 \\ 1 & \text{P} & 1 & 0 & 1 & 0 \\ 1 & \text{R} & 1 & 0 & 1 & 1 \\ 2 & \_ & 0 & 0 & 0 & \text{} \\ 2 & \text{C} & 0 & 0 & 1 & \text{} \\ 2 & \text{I} & 0 & 1 & 0 & \text{} \\ 3 & \text{S} & 1 & 1 & 0 & \text{} \\ 4 & \text{O} & 1 & 1 & 1 & \text{} \\ \end{array}$$
(i) Encode
combine2[x_List]:= If[
Length[x] < 2,
x,
Union[Drop[x,2],{MapAt[Total, Transpose[Take[x,2]],{1}]/.{a_,{b__}}->{a,a[b]}}]]
combine2 For a (list) argument of length greater than 1, the first two elements are removed and replaced with a single entity with a frequency equal to the sum of the individual frequencies, and a sorted list is returned; otherwise the argument is returned. combine2 is a modification of Wagner's combine function (Wagner, p 121)
The first step in the iterative process, where the first two elements of freqs are replaced by a single combined entity:
freqs
combine2[freqs]
(*
{{1, E}, {1, L}, {1, M}, {1, N}, {1, P}, {1, R}, {2, _}, {2, C}, {2, I}, {3, S}, {4, O}}
{{1, M}, {1, N}, {1, P}, {1, R}, {2, _}, {2, C}, {2, I}, {2, 2[E, L]}, {3, S}, {4, O}}
*)
This process is continued until a single entity (Huffman expression is obtained). For simple messages, such as the OP example, this could be done without the aid of a computer.
The result of each iteration:
FixedPointList[combine2,freqs]
(* {
{{1, E}, {1, L}, {1, M}, {1, N}, {1, P}, {1, R}, {2, _}, {2, C}, {2, I}, {3, S}, {4, O}}
{{1, M}, {1, N}, {1, P}, {1, R}, {2, _}, {2, C}, {2, I}, {2, 2[E, L]}, {3, S}, {4, O}},
{{1, P}, {1, R}, {2, _}, {2, C}, {2, I}, {2, 2[E, L]}, {2, 2[M, N]}, {3, S}, {4, O}},
{{2, _}, {2, C}, {2, I}, {2, 2[E, L]}, {2, 2[M, N]}, {2, 2[P, R]}, {3, S}, {4, O}},
{{2, I}, {2, 2[E, L]}, {2, 2[M, N]}, {2, 2[P, R]}, {3, S}, {4, O}, {4, 4[_, C]}},
{{2, 2[M, N]}, {2, 2[P, R]}, {3, S}, {4, O}, {4, 4[_, C]}, {4, 4[I, 2[E, L]]}},
{{3, S}, {4, O}, {4, 4[_, C]}, {4, 4[I, 2[E, L]]}, {4, 4[2[M, N], 2[P, R]]}},
{{4, 4[2[M, N], 2[P, R]]}, {7, 7[S, O]}, {8, 8[4[_, C], 4[I, 2[E, L]]]}},
{{8, 8[4[_, C], 4[I, 2[E, L]]]}, {11, 11[4[2[M, N], 2[P, R]], 7[S, O]]}},
{{19, 19[8[4[_, C], 4[I, 2[E, L]]], 11[4[2[M, N], 2[P, R]], 7[S, O]]]}},
{{19, 19[8[4[_, C], 4[I, 2[E, L]]], 11[4[2[M, N], 2[P, R]], 7[S, O]]]}}
} *)
(ii) Decode
ClearAll[huffmanDecodeAllList]
huffmanDecodeAllList[huffmanExpression_List,encodedText_]:=
(Fold[
Block[{a,newstate = Append[#1,#2]},
If[StringQ[a = Extract[huffmanExpression[[1,2]], newstate+1]],
Sow[{newstate->a}];{},
(*else*)
Sow[newstate]
](*If*)
](*Block*)&,
{},encodedText](*Fold*)//Reap)[[2,1]]
huffmanDecodeAllList is a modification of huffmanDecodeAll (1.9 Decoding) where the individual steps in the decoding process form part of the output. Wagner (p 123) has likened the decoding process to the operation of a state machine. huffmanDecodeAll gives the 'state' at each step, as well as the decoded character.
huffmanDecodeAllList[dataExpressionFull,encodedData]
{{0}, {0, 0}, {{0, 0, 1} -> C},
{1}, {1, 1}, {{1, 1, 1} -> O},
{1}, {1, 0}, {1, 0, 0}, {{1, 0, 0, 0} -> M},
{1}, {1, 0}, {1, 0, 1}, {{1, 0, 1, 0} -> P},
{1}, {1, 0}, {1, 0, 1}, {{1, 0, 1, 1} -> R},
{0}, {0, 1}, {0, 1, 1}, {{0, 1, 1, 0} -> E},
{1}, {1, 1}, {{1, 1, 0} -> S},
{1}, {1, 1}, {{1, 1, 0} -> S},
{0}, {0, 1}, {{0, 1, 0} -> I},
{1}, {1, 1}, {{1, 1, 1} -> O},
{1}, {1, 0}, {1, 0, 0}, {{1, 0, 0, 1} -> N},
{0}, {0, 0}, {{0, 0, 0} -> _},
{0}, {0, 1}, {{0, 1, 0} -> I},
{1}, {1, 1}, {{1, 1, 0} -> S},
{0}, {0, 0}, {{0, 0, 0} -> _},
{0}, {0, 0}, {{0, 0, 1} -> C},
{1}, {1, 1}, {{1, 1, 1} -> O},
{1}, {1, 1}, {{1, 1, 1} -> O},
{0}, {0, 1}, {0, 1, 1},{{0, 1, 1, 1} -> L}
} *)
Because of the possibility of 'draws' (entities with the same weight), a Huffman tree is not necessarily unique: it is likely that more than one tree can be constructed for a given message. (This is the case in the examples considered here).
The binary tree associated with the following Huffman expression is identical to that shown by the OP.
altDataExpression=List[{Head@#,#}&@TreeExpression@RulesTree[19->
{11->{7->{4->{"_","C"},"S"},"O"},8->{4->{2->{"R","E"},2->
{"M","P"}},4->{"I",2->{"N","L"}}}}]]
(* 19[11[7[4[_, C], S], O], 8[4[2[R, E], 2[M, P]], 4[I, 2[N, L]]]] *)
ExpressionTree[altDataExpression[[1,2]]/.vertexTransformationRules]
Examination of the above binary tree shows that it differs from the one shown in (1.5 Full Expression Tree) only in the treatment of entities with identical frequencies (weights).
encodedDataAlt=huffmanEncodeAll[altDataExpression,data]
(* {0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,
0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1,
1, 1, 1}
*)
Length@encodedDataAlt
(* 63 *)
The length of the encoded message is the same as that of encodedData (1.7 Huffman Encoding)
huffmanDecodeAll[altDataExpression, encodedDataAlt]
(* COMPRESSION_IS_COOL *)
But the appropriate Huffman expression must be used:
huffmanDecodeAll[dataExpression, encodedDataAlt]
(* _RIRMNCCSLMCMM_IRO *)
Step-by-step decoding:
huffmanDecodeAllList[dataExpressionAlt,encodedDataAlt]//OutputForm
{{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 1} -> C},
{0}, {{0, 1} -> O},
{1}, {1, 0}, {1, 0, 1}, {{1, 0, 1, 0} -> M},
{1}, {1, 0}, {1, 0, 1}, {{1, 0, 1, 1} -> P},
{1}, {1, 0}, {1, 0, 0}, {{1, 0, 0, 0} -> R},
{1}, {1, 0}, {1, 0, 0}, {{1, 0, 0, 1} -> E},
{0}, {0, 0}, {{0, 0, 1} -> S},
{0}, {0, 0}, {{0, 0, 1} -> S},
{1}, {1, 1}, {{1, 1, 0} -> I},
{0}, {{0, 1} -> O},
{1}, {1, 1}, {1, 1, 1}, {{1, 1, 1, 0} -> N},
{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 0} -> _},
{1}, {1, 1}, {{1, 1, 0} -> I},
{0}, {0, 0}, {{0, 0, 1} -> S},
{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 0} -> _},
{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 1} -> C},
{0}, {{0, 1} -> O},
{0}, {{0, 1} -> O},
{1}, {1, 1}, {1, 1, 1}, {{1, 1, 1, 1} -> L}}
TableForm[SortBy[Join[SortBy[freqs,Last],huffmanEncode[altDataExpression,
#]&/@(SortBy[freqs,Last][[All,2]]),2],First],
TableHeadings -> {None,{"Freq", "Char"}}]//TeXForm//OutputForm
$$\begin{array}{cccccc} \text{Freq} & \text{Char} & \text{} & \text{} & \text{} & \text{} \\ 1 & \text{E} & 1 & 0 & 0 & 1 \\ 1 & \text{L} & 1 & 1 & 1 & 1 \\ 1 & \text{M} & 1 & 0 & 1 & 0 \\ 1 & \text{N} & 1 & 1 & 1 & 0 \\ 1 & \text{P} & 1 & 0 & 1 & 1 \\ 1 & \text{R} & 1 & 0 & 0 & 0 \\ 2 & \text{I} & 1 & 1 & 0 & \text{} \\ 2 & \_ & 0 & 0 & 0 & 0 \\ 2 & \text{C} & 0 & 0 & 0 & 1 \\ 3 & \text{S} & 0 & 0 & 1 & \text{} \\ 4 & \text{O} & 0 & 1 & \text{} & \text{} \\ \end{array}$$
Wagner (pp 118-126) takes the following example:
msg="she sells sea shells by the sea shore";
freqs=sortTally[msg]
(* {{1, b}, {1, o}, {1, r}, {1, t}, {1, y}, {2, a}, {4, h}, {4, l}, {7, }, {7, e}, {8, s}} *)
Union@Characters@data//{Length@#,#}&
{11, { , a, b, e, h, l, o, r, s, t, y}}
msgExpressionFull=huffmanExpressionFull[msg]
(* {{37, 37[15[7[3[y, a], h], s], 22[8[l, 4[2[b, o], 2[r, t]]], 14[ , e]]]}} *)
tree=ExpressionTree[msgExpressionFull[[1,2]]];
vertices=TreeFold[List,ExpressionTree[huffmanExpressionFull[msg][[1,2]]]]//Flatten;
vertexTransformationRules=Thread[
#[[All,2]]->#/.{x_Integer/;x>1,y_String}:>y<>"("<>ToString[x]<>")"]&@Select[freqs,#[[1]]>1&
];
ExpressionTree[TreeExpression@tree/.vertexTransformationRules]
encodedMsg=huffmanEncodeAll[dataExpression,msg]
{0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1,
0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0,
1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0,
1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1,
1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0,
1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1}
Length@encodedMsg
(* 114 *)
decodedMsg=huffmanDecodeAll[msgExpressionFull,encodedMsg]
StringLength@decodedMsg
(* she sells sea shells by the sea shore
37 *)
huffmanDecodeAllList[msgExpressionFull,encodedMsg]
(* {{0}, {{0, 1} -> s},
{0}, {0, 0}, {{0, 0, 1} -> h},
{1}, {1, 1}, {{1, 1, 1} -> e},
{1}, {1, 1}, {{1, 1, 0} -> },
{0}, {{0, 1} -> s},
{1}, {1, 1}, {{1, 1, 1} -> e},
{1}, {1, 0}, {{1, 0, 0} -> l},
{1}, {1, 0}, {{1, 0, 0} -> l},
{0}, {{0, 1} -> s},
{1}, {1, 1}, {{1, 1, 0} -> },
{0}, {{0, 1} -> s},
{1}, {1, 1}, {{1, 1, 1} -> e},
{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 1} -> a},
{1}, {1, 1}, {{1, 1, 0} -> },
{0},{{0, 1} -> s},
{0}, {0, 0}, {{0, 0, 1} -> h},
{1}, {1, 1}, {{1, 1, 1} -> e},
{1}, {1, 0}, {{1, 0, 0} -> l},
{1}, {1, 0}, {{1, 0, 0} -> l},
{0}, {{0, 1} -> s},
{1}, {1, 1}, {{1, 1, 0} -> },
{1}, {1, 0}, {1, 0, 1}, {1, 0, 1, 0}, {{1, 0, 1, 0, 0} -> b},
{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 0} -> y},
{1}, {1, 1}, {{1, 1, 0} -> },
{1}, {1, 0}, {1, 0, 1}, {1, 0, 1, 1}, {{1, 0, 1, 1, 1} -> t},
{0}, {0, 0}, {{0, 0, 1} -> h},
{1}, {1, 1}, {{1, 1, 1} -> e},
{1}, {1, 1}, {{1, 1, 0} -> }, {0}, {{0, 1} -> s},
{1}, {1, 1}, {{1, 1, 1} -> e},
{0}, {0, 0}, {0, 0, 0}, {{0, 0, 0, 1} -> a},
{1}, {1, 1}, {{1, 1, 0} -> },
{0}, {{0, 1} -> s},
{0}, {0, 0}, {{0, 0, 1} -> h},
{1}, {1, 0}, {1, 0, 1}, {1, 0, 1, 0}, {{1, 0, 1, 0, 1} -> o},
{1}, {1, 0}, {1, 0, 1}, {1, 0, 1, 1}, {{1, 0, 1, 1, 0} -> r},
{1}, {1, 1}, {{1, 1, 1} -> e}}
TableForm[SortBy[Join[SortBy[freqs,Last],huffmanEncode[dataExpression,
#]&/@(SortBy[freqs,Last][[All,2]]),2],First],
TableHeadings -> {None,{"Freq", "Char"}}]//TeXForm
$$\begin{array}{ccccccc} \text{Freq} & \text{Char} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & \text{y} & 0 & 0 & 0 & 0 & \text{} \\ 1 & \text{b} & 1 & 0 & 1 & 0 & 0 \\ 1 & \text{o} & 1 & 0 & 1 & 0 & 1 \\ 1 & \text{r} & 1 & 0 & 1 & 1 & 0 \\ 1 & \text{t} & 1 & 0 & 1 & 1 & 1 \\ 2 & \text{a} & 0 & 0 & 0 & 1 & \text{} \\ 4 & \text{h} & 0 & 0 & 1 & \text{} & \text{} \\ 4 & \text{l} & 1 & 0 & 0 & \text{} & \text{} \\ 7 & & 1 & 1 & 0 & \text{} & \text{} \\ 7 & \text{e} & 1 & 1 & 1 & \text{} & \text{} \\ 8 & \text{s} & 0 & 1 & \text{} & \text{} & \text{} \\ \end{array}$$
You can try this link: http://www.davidaltherr.net/mathematics/notebooks/huffman_encoding/huffman_encoding.php
Personally I'm working on another version of step by step Huffman tree encoding but for now I can't associate the tree i get with a binary code yet.
Good Luck!
