Huffman coding: Difference between revisions
→{{header|Phix}}
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Combine into a single file for ease of testing) |
|||
Line 4,019:
1000000011111011110111110111101100101010111011100010010010011000000111011011110001101101101000110001111011100010100101010111010101100100011110011111101000000
this is an example for huffman encoding</pre>
=={{header|Phix}}==
{{trans|Lua}}
<lang Phix>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")</lang>
{{out}}
<pre>
' ' [6] 101
'a' [3] 1001
'c' [1] 01010
'd' [1] 01011
'e' [3] 1100
'f' [3] 1101
'g' [1] 01100
'h' [2] 11111
'i' [3] 1110
'l' [1] 01101
'm' [2] 0010
'n' [4] 000
'o' [2] 0011
'p' [1] 01110
'r' [1] 01111
's' [2] 0100
't' [1] 10000
'u' [1] 10001
'x' [1] 11110
"1000011111111001001011110010010110010001011100111101001001001110011011100101110100110111110111111100011101110100101001000101110000001010001101011111000001100"
"this is an example for huffman encoding"
</pre>
=={{header|PHP}}==
| |||