Anonymous user
Huffman coding: Difference between revisions
→{{header|Lua}}: : add Lua implementation (tested against 5.2 and 5.3)
No edit summary |
(→{{header|Lua}}: : add Lua implementation (tested against 5.2 and 5.3)) |
||
Line 3,299:
f 3 1101
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}}==
| |||