#!/usr/bin/perl -w
# 演算法: Huffman Encoding
# 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung
# 授權: public domain (但如果您要將我的程式改寫成有用的大程式,
#	強烈建議將您的版本施以 GPL)

use strict;
use Heap;

sub huffman {
    my ($text) = @_;
    my (%freq, $out, $hp);
    map { ++$freq{$_} } split //, $text;

    foreach (sort keys %freq) {
	$out->[0] .= "  $_";
	$out->[1] .= sprintf " %2d", $freq{$_};
    }
    printf "$out->[0] tot\n$out->[1] %3d\n", length($text);

    $hp = Heap->new([map {"$_:$freq{$_}"} keys %freq],
	-compare=>sub { my ($a, $b);
	    (undef, $a) = split ":", $_[0];
	    (undef, $b) = split ":", $_[1];
	    return $a <=> $b;
	}
    );

    my ($n, $i, $codebook, $root);
    $n = $hp->size();
    print "init:     $hp\n";
    for ($i=1; $i<$n; ++$i) {
	my ($a, $a_freq, $b, $b_freq, $c, $c_freq);
	($a, $a_freq) = split ":", $hp->remove();
	($b, $b_freq) = split ":", $hp->remove();
	$c = "*$i";
	$c_freq = $a_freq + $b_freq;
	$hp->insert("$c:$c_freq");
	$codebook->{$c} = { left=>$a, right=>$b };
	printf "%-9s $hp\n", "[$a $b]";
    }

    ($root, undef) = split ":", $hp->remove();
    print_code_tree($root, 0, "", $codebook);

    $n = join '', map { $codebook->{$_}{code} } split //, $text;
    printf "$n\ntotal %d bits\n", length($n);
}

sub print_code_tree {
    my ($c, $level, $code, $codebook) = @_;
    print "    " x $level, substr($code, -1);
    if (length $c == 1) {
	print " $c\n";
	$codebook->{$c}{code} = $code;
    } else {
	print "\n";
	print_code_tree($codebook->{$c}{left},  $level+1, "${code}0", $codebook);
	print_code_tree($codebook->{$c}{right}, $level+1, "${code}1", $codebook); 
    }
}

my ($text) = defined $ARGV[0] ? $ARGV[0] :
    "a simple string to be encoded using a minimal number of bits";
$text =~ s/ /_/g;
print "$text\n";
huffman($text);