74 lines
1.8 KiB
Lua
74 lines
1.8 KiB
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"
|