39 lines
707 B
Plaintext
39 lines
707 B
Plaintext
var forest := {}, encTab := {};
|
|
|
|
plaintext := 'this is an example for huffman encoding';
|
|
|
|
ft := {};
|
|
(for c in plaintext)
|
|
ft(c) +:= 1;
|
|
end;
|
|
|
|
forest := {[f, c]: [c, f] in ft};
|
|
(while 1 < #forest)
|
|
[f1, n1] := getLFN();
|
|
[f2, n2] := getLFN();
|
|
forest with:= [f1+f2, [n1,n2]];
|
|
end;
|
|
addToTable('', arb range forest);
|
|
|
|
(for e = encTab(c))
|
|
print(c, ft(c), e);
|
|
end;
|
|
|
|
print(+/ [encTab(c): c in plaintext]);
|
|
|
|
proc addToTable(prefix, node);
|
|
if is_tuple node then
|
|
addToTable(prefix + '0', node(1));
|
|
addToTable(prefix + '1', node(2));
|
|
else
|
|
encTab(node) := prefix;
|
|
end;
|
|
end proc;
|
|
|
|
proc getLFN();
|
|
f := min/ domain forest;
|
|
n := arb forest{f};
|
|
forest less:= [f, n];
|
|
return [f, n];
|
|
end proc;
|