Huffman coding: Difference between revisions
Content deleted Content added
→{{header|Perl 6}}: Clean up and modernize the original tree-building solution as well. |
→{{header|Perl 6}}: Add some explanation. |
||
| Line 3,735: | Line 3,735: | ||
===By building a tree=== |
===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}} |
{{works with|rakudo|2015-12-17}} |
||
| Line 3,751: | Line 3,753: | ||
walk $node2, $prefix ~ '1'; }</lang> |
walk $node2, $prefix ~ '1'; }</lang> |
||
===Without building a tree=== |
===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}} |
{{works with|rakudo|2015-12-17}} |
||
| Line 3,798: | Line 3,802: | ||
my @codes = %decode-key.keys; |
my @codes = %decode-key.keys; |
||
my $encoded = %encode-key{$ |
my $encoded = $original.subst: /./, { %encode-key{$_} }, :g; |
||
my $decoded = $encoded.subst: /@codes/ |
my $decoded = $encoded .subst: /@codes/, { %decode-key{$_} }, :g; |
||
.say for $original, $encoded, $decoded;</lang> |
.say for $original, $encoded, $decoded;</lang> |
||