Huffman coding: Difference between revisions
Added Wren
(Changed indentation. Many other minor changes. Changed the output to a sorted list of pairs.) |
(Added Wren) |
||
Line 6,850:
`e: '1101',
` : '111'></pre>
=={{header|Wren}}==
{{trans|Java}}
{{libheader|Wren-queue}}
Note that the results differ from Java because the PriorityQueue implementation is not the same.
<lang ecmascript>import "/queue" for PriorityQueue
class HuffmanTree {
construct new(freq) {
_freq = freq
}
freq { _freq }
compareTo(tree) { _freq - tree.freq }
}
class HuffmanLeaf is HuffmanTree {
construct new (freq, val) {
super(freq)
_val = val
}
val { _val }
}
class HuffmanNode is HuffmanTree {
construct new(l, r) {
super(l.freq + r.freq)
_left = l
_right = r
}
left { _left }
right { _right }
}
var buildTree = Fn.new { |charFreqs|
var trees = PriorityQueue.new()
var index = 0
for (freq in charFreqs) {
if (freq > 0) trees.push(HuffmanLeaf.new(freq, String.fromByte(index)), -freq)
index = index + 1
}
if (trees.count == 0) Fiber.abort("Something went wrong!")
while (trees.count > 1) {
var a = trees.pop()
var b = trees.pop()
var h = HuffmanNode.new(a[0], b[0])
trees.push(h, -h.freq)
}
return trees.pop()[0]
}
var printCodes // recursive
printCodes = Fn.new { |tree, prefix|
if (tree is HuffmanLeaf) {
System.print("%(tree.val)\t%(tree.freq)\t%(prefix)")
} else if (tree is HuffmanNode) {
// traverse left
prefix = prefix + "0"
printCodes.call(tree.left, prefix)
prefix = prefix[0...-1]
// traverse right
prefix = prefix + "1"
printCodes.call(tree.right, prefix)
prefix = prefix[0...-1]
}
}
var test = "this is an example for huffman encoding"
var freqs = List.filled(256, 0)
for (c in test) {
var ix = c.bytes[0]
freqs[ix] = freqs[ix] + 1
}
var tree = buildTree.call(freqs)
System.print("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes.call(tree, "")</lang>
{{out}}
<pre>
SYMBOL WEIGHT HUFFMAN CODE
n 4 000
m 2 0010
o 2 0011
s 2 0100
c 1 01010
d 1 01011
g 1 01100
l 1 01101
p 1 01110
r 1 01111
t 1 10000
u 1 10001
a 3 1001
6 101
e 3 1100
f 3 1101
i 3 1110
x 1 11110
h 2 11111
</pre>
=={{header|zkl}}==
| |||