Anonymous user
Huffman coding: Difference between revisions
→{{header|Perl 6}}: Add some explanation.
(→{{header|Perl 6}}: Clean up and modernize the original tree-building solution as well.) |
(→{{header|Perl 6}}: Add some explanation.) |
||
Line 3,735:
===By building a tree===
This version uses nested <code>Array</code>s to builds a tree [https://commons.wikimedia.org/wiki/File:HuffmanCodeAlg.png like shown in this diagram], and then recursively traverses the finished tree to accumulate the prefixes.
{{works with|rakudo|2015-12-17}}
Line 3,751 ⟶ 3,753:
walk $node2, $prefix ~ '1'; }</lang>
===Without building a tree===
This version uses an <code>Array</code> of <code>Pair</code>s to implement a simple priority queue. Each value of the queue is a <code>Hash</code> mapping from letters to prefixes, and when the queue is reduced the hashes are merged on-the-fly, so that the last one remaining is the wanted Huffman table.
{{works with|rakudo|2015-12-17}}
Line 3,798 ⟶ 3,802:
my @codes = %decode-key.keys;
my $encoded = $original.subst: /./, { %encode-key{$
my $decoded = $encoded .subst: /@codes/
.say for $original, $encoded, $decoded;</lang>
| |||