24 lines
1.1 KiB
Plaintext
24 lines
1.1 KiB
Plaintext
fcn buildHuffman(text){ //-->(encode dictionary, decode dictionary)
|
|
ft:=Dictionary();
|
|
foreach c in (text){ ft[c]=ft.find(c,0)+1 } // leafs w/count
|
|
|
|
// build the tree, which is a list of lists of ...
|
|
tree:=ft.pump(List,fcn([(c,cnt)]){ //-->L( (cnt, ((sym,code))), ...)
|
|
L(cnt, L(L(c,"")))
|
|
}).copy(); // make it writable
|
|
|
|
while(tree.len()>1){ // fake up a [lame] priorty queue
|
|
tree=tree.sort(fcn(a,b){ a[0]>b[0] }); //prioritize high to low
|
|
a,b:=tree.pop(-2,2); //remove 2 least frequent symbols
|
|
mc:=fcn(n,c){ n[1] = c + n[1]; }; //(sym,code),"0"|"1"
|
|
a[1].apply2(mc,"0"); b[1].apply2(mc,"1"); // mc(a[1],"0")
|
|
tree.append( L(a[0]+b[0],a[1].extend(b[1])) ); //(a,b)-->new node
|
|
}//-->L(L(39, L( L(" ","000"),L("e","0010"),L("a","0011") ...
|
|
|
|
tree=tree[0][1].pump(List,fcn(i){ // flatten rather than traverse
|
|
if(T.isType(i))return(Void.Recurse,i,self.fcn); i });
|
|
encodeTable:=tree.toDictionary(); // symbol:Huffman code
|
|
decodeTable:=encodeTable.pump(Dictionary(),"reverse"); // code:symbol
|
|
return(encodeTable,decodeTable);
|
|
}
|