Huffman coding
editable example
Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.
ghul
use IO.Std.write_line
use Collections.LIST
use Collections.List
use Collections.MAP
use Ghul.Pipes
union Huffman(weight: int) is
LEAF(symbol: char, ..)
NODE(left: Huffman, right: Huffman, ..)
si
use Huffman.LEAF
use Huffman.NODE
take_lightest(pending: LIST[Huffman]) -> Huffman is
let at mut = 0
for i in 1..pending.count do
if pending[i].weight < pending[at].weight then
at = i
fi
od
let lightest = pending[at]
pending.remove_at(at)
return lightest
si
build_tree(leaves: List[Huffman]) -> Huffman is
let pending = LIST[Huffman](leaves)
while pending.count > 1 do
let first = take_lightest(pending)
let second = take_lightest(pending)
pending.add(NODE(first, second, first.weight + second.weight))
od
return pending[0]
si
codes(node: Huffman, prefix: string)
-> Pipe[(symbol: char, weight: int, code: string)]
is
if let leaf: LEAF = ►node then
let code = if prefix.length == 0 then "0" else prefix fi
yield (symbol = leaf.symbol, weight = leaf.weight, code = code)
elif let branch: NODE = ►node then
yield in codes(branch.left, "{prefix}0")
yield in codes(branch.right, "{prefix}1")
fi
si
let text = "this is an example for huffman encoding"
let weights = MAP[char, int]()
for character in text do
let seen mut = 0
weights.try_get_value(character, seen ref)
weights[character] = seen + 1
od
let leaves = LIST[Huffman]()
for symbol in weights.keys |> sort() do
leaves.add(LEAF(symbol, weights[symbol]))
od
let table =
codes(build_tree(leaves), "")
|> sort((left, right) =>
if left.weight != right.weight then
right.weight - left.weight
else
cast int(left.symbol) - cast int(right.symbol)
fi)
|> collect_list()
write_line("symbol weight code")
for entry in table do
let symbol = "'{entry.symbol}'"
write_line("{symbol,-6} {entry.weight,6} {entry.code}")
od