Huffman coding: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Combine into a single file for ease of testing) |
|||
Line 4,019: | Line 4,019: | ||
1000000011111011110111110111101100101010111011100010010010011000000111011011110001101101101000110001111011100010100101010111010101100100011110011111101000000 |
1000000011111011110111110111101100101010111011100010010010011000000111011011110001101101101000110001111011100010100101010111010101100100011110011111101000000 |
||
this is an example for huffman encoding</pre> |
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}}== |
=={{header|PHP}}== |