:

## Huffman Coding

Huffman coding can be implemented in Maple similarly to Python.

First, we need a set of character frequencies. It can be created from a string using the following procedure,

```Freq:=s->map(x->rhs(x)=lhs(x),
{StringTools:-CharacterFrequencies(s)});
```

For example (used in the wikipedia article),

```s:= "this is an example of a huffman tree":

Fr:=Freq(s);

{1 = "l", 1 = "o", 1 = "p", 1 = "r", 1 = "u", 1 = "x", 2 = "h",

2 = "i", 2 = "m", 2 = "n", 2 = "s", 2 = "t", 3 = "f", 4 = "a",

4 = "e", 7 = " "}
```

I've interchanged the equation sides in CharacterFrequencies so that the set entries were sorted (automatically) by their frequencies - similarly to the Python code.

Now, the Huffman tree can be constructed recursively,

```HuffmanTree :=s -> if nops(s)<=1 then rhs(s[])
else procname(s[3..-1] union
{lhs(s)+lhs(s)=[rhs(s),rhs(s)]})
fi;```

In our example, that gives

```HT:=HuffmanTree(Fr);

HT := [[["a", "e"], [["h", "i"], ["m", "n"]]], [

[["s", "t"], [["l", "o"], ["p", "r"]]],

[[["u", "x"], "f"], " "]]]
```

Now, the binary codes associated to letters, can be also constructed recursively,

```HuffmanCoding:=proc(s,p:="")
if s::string then s=p
else procname(s,cat(p,0)), procname(s,cat(p,1))
fi
end;
```

In our example,

```HC:=HuffmanCoding(HT);

"a" = "000", "e" = "001", "h" = "0100", "i" = "0101", "m" = "0110",

"n" = "0111", "s" = "1000", "t" = "1001", "l" = "10100",

"o" = "10101", "p" = "10110", "r" = "10111", "u" = "11000",

"x" = "11001", "f" = "1101", " " = "111"
```

Using that, the original string can be written in binary as

```C:=table([HC]):
b:=cat(map(x->C[x],StringTools:-Explode(s))[]);

"100101000101100011101011000111000011111100111001000011010110101\
0000111110101110111100011101001100011011101011000001111111\
00110111001001"

length(b);
135
```

The decoding can be done using following procedure:

```HuffmanDecode:=proc(b,T)
local h, i, j, ans;
ans:=Array(1..length(b));
h:=T;
j:=0;
for i to length(b) do
if b[i]="0" then h:=h else h:=h fi;
if h::string then j:=j+1; ans[j]:=h; h:=T fi
od;
StringTools:-Implode([seq(i,i=ans[1..j])])
end:

HuffmanDecode(b,HT);

"this is an example of a huffman tree"
```

The encoding operations above can be combined to a single procedure,

```HuffmanEncode:=proc(s)
local C, T, HuffmanTree, HuffmanCoding;
HuffmanTree :=s -> if nops(s)<=1 then rhs(s[])
else procname(s[3..-1] union
{lhs(s)+lhs(s)=[rhs(s),rhs(s)]})
fi;
HuffmanCoding:=proc(s,p:="")
if s::string then s=p
else procname(s,cat(p,0)), procname(s,cat(p,1))
fi
end;
if _nrest=1 then T:=_rest
else T:=HuffmanTree(map(x->rhs(x)=lhs(x),
{StringTools:-CharacterFrequencies(s)}))
fi;
C:=table([HuffmanCoding(T)]);
cat(map(x->C[x],StringTools:-Explode(s))[]),
T
end;
```

It works rather fast for not very long strings,

```s:=StringTools:-Random(10000,ascii):
t:=time():
b:=HuffmanEncode(s):
time()-t;

0.015
```

The decoding procedure is slower,

```t:=time():
s1:=HuffmanDecode(b):
time()-t;

0.124

evalb(s1=s);

true
```

For larger strings, time seems to be increasing linearly,

```s:=StringTools:-Random(100000,ascii):
t:=time():
b:=HuffmanEncode(s):
time()-t;

0.124

t:=time():
s1:=HuffmanDecode(b):
time()-t;

1.591

evalb(s1=s);

true
```

Suggestions (in the code form) are welcomed.

Alec ﻿