99 lines
2.5 KiB
Plaintext
99 lines
2.5 KiB
Plaintext
function store_nodes(object key, object data, integer nodes)
|
|
setd({data,key},0,nodes)
|
|
return 1
|
|
end function
|
|
constant r_store_nodes = routine_id("store_nodes")
|
|
|
|
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(r_store_nodes, nodes, freq)
|
|
destroy_dict(freq)
|
|
return nodes
|
|
end function
|
|
|
|
function build_hufftree(integer nodes)
|
|
sequence lkey, rkey, node
|
|
integer lfreq, rfreq
|
|
while true do
|
|
lkey = getd_partial_key({0,0},nodes)
|
|
lfreq = lkey[1]
|
|
deld(lkey,nodes)
|
|
rkey = getd_partial_key({0,0},nodes)
|
|
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*/)
|
|
printf(1,"'%c' [%d] %s\n",key&data)
|
|
return 1
|
|
end function
|
|
constant r_print_huffcode = routine_id("print_huffcode")
|
|
|
|
procedure print_huffcodes(integer d)
|
|
traverse_dict(r_print_huffcode, 0, d)
|
|
end procedure
|
|
|
|
function invert_huffcode(integer key, sequence data, integer rd)
|
|
setd(data[2],key,rd)
|
|
return 1
|
|
end function
|
|
constant r_invert_huffcode = routine_id("invert_huffcode")
|
|
|
|
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
|
|
?encoded
|
|
|
|
integer rd = new_dict()
|
|
traverse_dict(r_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")
|