huffman-in-perl.pl

#!/usr/bin/perl

use strict;

my %freq;
while (<>) {
    chomp;
    map { $freq{$_}++ } split //;
}

my @tree = map { [ $freq{$_}, $_ ] } keys %freq;

while (@tree > 1) {
    @tree = sort { $b->[0] <=> $a->[0] } @tree;
    my @last2 = splice(@tree, -2, 2);
    push(@tree, [$last2[0][0] + $last2[1][0], @last2]);
}

showtree("", @tree);

sub showtree {
    my($code, $node) = @_;
    if (@$node == 2) {
	printf("\"%s\" %6d: %s\n", $node->[1], $node->[0], $code);
    } else {
	showtree($code . "0", $node->[1]);
	showtree($code . "1", $node->[2]);
    }
}