(phixonline)-->
with javascript_semantics
function store_nodes(object key, object data, integer nodes)
setd({data,key},0,nodes)
return 1
end function
function build_freqtable(string data)
integer freq = new_dict(),
nodes = new_dict()
for i=1 to length(data) do
integer di = data[i]
setd(di,getd(di,freq)+1,freq)
end for
traverse_dict(store_nodes, nodes, freq)
destroy_dict(freq)
return nodes
end function
function build_hufftree(integer nodes)
sequence node
while true do
sequence lkey = getd_partial_key({0,0},nodes)
integer lfreq = lkey[1]
deld(lkey,nodes)
sequence rkey = getd_partial_key({0,0},nodes)
integer rfreq = rkey[1]
deld(rkey,nodes)
node = {lfreq+rfreq,{lkey,rkey}}
if dict_size(nodes)=0 then exit end if
setd(node,0,nodes)
end while
destroy_dict(nodes)
return node
end function
procedure build_huffcodes(object node, string bits, integer d)
{integer freq, object data} = node
if sequence(data) then
build_huffcodes(data[1],bits&'0',d)
build_huffcodes(data[2],bits&'1',d)
else
setd(data,{freq,bits},d)
end if
end procedure
function print_huffcode(integer key, sequence data, integer /*user_data*/)
{integer i, string s} = data
printf(1,"'%c' [%d] %s\n",{key,i,s})
return 1
end function
procedure print_huffcodes(integer d)
traverse_dict(print_huffcode, 0, d)
end procedure
function invert_huffcode(integer key, sequence data, integer rd)
setd(data[2],key,rd)
return 1
end function
procedure main(string data)
if length(data)<2 then ?9/0 end if
integer nodes = build_freqtable(data)
sequence huff = build_hufftree(nodes)
integer d = new_dict()
build_huffcodes(huff, "", d)
print_huffcodes(d)
string encoded = ""
for i=1 to length(data) do
encoded &= getd(data[i],d)[2]
end for
?shorten(encoded)
integer rd = new_dict()
traverse_dict(invert_huffcode, rd, d)
string decoded = ""
integer done = 0
while done<length(encoded) do
string key = ""
integer node = 0
while node=0 do
done += 1
key &= encoded[done]
node = getd_index(key, rd)
end while
decoded &= getd_by_index(node,rd)
end while
?decoded
end procedure
main("this is an example for huffman encoding")