Huffman coding: Difference between revisions

Huffman coding (view source)

Revision as of 14:06, 17 December 2015

81 bytes added , 8 years ago

→‎{{header|Perl 6}}: Clean up and modernize the original tree-building solution as well.

Anonymous user

rosettacode>Smls

Revision as of 13:57, 17 December 2015 (view source) rosettacode>Smls (→‎{{header\|Perl 6}}: add solution that doesn't build a tree, and improve testing/demo section) ← Older edit		Revision as of 14:06, 17 December 2015 (view source) rosettacode>Smls (→‎{{header\|Perl 6}}: Clean up and modernize the original tree-building solution as well.) Newer edit →
Line 3,736: ===By building a tree=== {{works with\|rakudo\|2015-0912-1417}} <lang perl6>sub huffman ($s%frequencies) { my ~~$de~~@queue = $s%frequencies.~~chars~~map({ [.value, .key] }).sort; while @qqueue > 1 {▼ ~~my @q = $s.comb.classify({$_}).map({[+.value / $de, .key]}).sort;~~ given @queue.splice(0, 2) -> ([$freq1, $node1], [$freq2, $node2]) { ▲ while @q > 1 { @queue = (\|@queue, [$freq1 + $freq2, [$node1, $node2]]).sort; ~~my ($a,$b) = @q.splice(0,2);~~ } ~~@q = sort flat $[$a[0] + $b[0], [$a[1], $b[1]]], @q;~~ } ~~sort .value,~~hash gather walk @qqueue[0][1], ''; } multi walk (@node, $prefix) {▼ ~~walk @node[0], $prefix ~ 1;~~ ~~walk @node[1], $prefix ~ 0;~~ } multi walk ($node, $prefix) { take $node => $prefix }</lang>▼ ▲multi walk (@$node, $prefix) { take $node => $prefix; } ▲multi walk ([$~~node~~node1, $node2], $prefix) { ~~take~~walk $~~node =>~~node1, $prefix ~~}</lang>~~~ '0'; walk $node2, $prefix ~ '1'; }</lang> ===Without building a tree=== {{works with\|rakudo\|2015-12-17}} <lang perl6>sub huffman (%frequencies~~, $zero='0', $one='1'~~) { my @queue = %frequencies.map: { .value => (hash .key => '') }; while @queue > 1 { Line 3,762 ⟶ 3,759: my $x = @queue.shift; my $y = @queue.shift; @queue.push: ($x.key + $y.key) => hash $x.value.deepmap(~~$zero~~'0' ~ ), $y.value.deepmap(~~$one~~ '1' ~ *); } @queue[0].value;