Huffman coding: Difference between revisions
Content added Content deleted
No edit summary |
(→{{header|Lua}}: : add Lua implementation (tested against 5.2 and 5.3)) |
||
Line 3,299: | Line 3,299: | ||
f 3 1101 |
f 3 1101 |
||
6 111</pre> |
6 111</pre> |
||
=={{header|Lua}}== |
|||
{{trans|Lua}} |
|||
This implementation creates an actual tree structure, and then traverses the tree to recover the code. |
|||
<lang lua>local build_freqtable = function (data) |
|||
local freq = { } |
|||
for i = 1, #data do |
|||
local cur = string.sub (data, i, i) |
|||
local count = freq [cur] or 0 |
|||
freq [cur] = count + 1 |
|||
end |
|||
local nodes = { } |
|||
for w, f in next, freq do |
|||
nodes [#nodes + 1] = { word = w, freq = f } |
|||
end |
|||
table.sort (nodes, function (a, b) return a.freq > b.freq end) --- reverse order! |
|||
return nodes |
|||
end |
|||
local build_hufftree = function (nodes) |
|||
while true do |
|||
local n = #nodes |
|||
local left = nodes [n] |
|||
nodes [n] = nil |
|||
local right = nodes [n - 1] |
|||
nodes [n - 1] = nil |
|||
local new = { freq = left.freq + right.freq, left = left, right = right } |
|||
if n == 2 then return new end |
|||
--- insert new node at correct priority |
|||
local prio = 1 |
|||
while prio < #nodes and nodes [prio].freq > new.freq do |
|||
prio = prio + 1 |
|||
end |
|||
table.insert (nodes, prio, new) |
|||
end |
|||
end |
|||
local print_huffcodes do |
|||
local rec_build_huffcodes |
|||
rec_build_huffcodes = function (node, bits, acc) |
|||
if node.word == nil then |
|||
rec_build_huffcodes (node.left, bits .. "0", acc) |
|||
rec_build_huffcodes (node.right, bits .. "1", acc) |
|||
return acc |
|||
else --- leaf |
|||
acc [#acc + 1] = { node.freq, node.word, bits } |
|||
end |
|||
return acc |
|||
end |
|||
print_huffcodes = function (root) |
|||
local codes = rec_build_huffcodes (root, "", { }) |
|||
table.sort (codes, function (a, b) return a [1] < b [1] end) |
|||
print ("frequency\tword\thuffman code") |
|||
for i = 1, #codes do |
|||
print (string.format ("%9d\t‘%s’\t“%s”", table.unpack (codes [i]))) |
|||
end |
|||
end |
|||
end |
|||
local huffcode = function (data) |
|||
local nodes = build_freqtable (data) |
|||
local huff = build_hufftree (nodes) |
|||
print_huffcodes (huff) |
|||
return 0 |
|||
end |
|||
return huffcode "this is an example for huffman encoding" |
|||
</lang> |
|||
<pre> |
|||
frequency word huffman code |
|||
1 ‘g’ “01111” |
|||
1 ‘p’ “01011” |
|||
1 ‘d’ “01100” |
|||
1 ‘c’ “01101” |
|||
1 ‘t’ “01010” |
|||
1 ‘r’ “10000” |
|||
1 ‘u’ “11110” |
|||
1 ‘x’ “10001” |
|||
1 ‘l’ “01110” |
|||
2 ‘o’ “11111” |
|||
2 ‘m’ “0011” |
|||
2 ‘h’ “0010” |
|||
2 ‘s’ “0100” |
|||
3 ‘i’ “1101” |
|||
3 ‘f’ “1110” |
|||
3 ‘a’ “1100” |
|||
3 ‘e’ “1001” |
|||
4 ‘n’ “000” |
|||
6 ‘ ’ “101” |
|||
</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |