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[1])+lhs(s[2])=[rhs(s[1]),rhs(s[2])]})
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[1],cat(p,0)), procname(s[2],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[1] else h:=h[2] 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[1])+lhs(s[2])=[rhs(s[1]),rhs(s[2])]})
fi;
HuffmanCoding:=proc(s,p:="")
if s::string then s=p
else procname(s[1],cat(p,0)), procname(s[2],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