Huffman coding: Difference between revisions
Content added Content deleted
(Changed indentation. Many other minor changes. Changed the output to a sorted list of pairs.) |
(Added Wren) |
||
Line 6,850: | Line 6,850: | ||
`e: '1101', |
`e: '1101', |
||
` : '111'></pre> |
` : '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}}== |
=={{header|zkl}}== |