Huffman符号の復習をしてみた

※追記：一部、記事の解説に間違いがあった。詳細は以下を参照のこと。

Huffman符号間違ってた

※追記ここまで

思うところがあってHuffman符号について復習した。Huffman符号は、与えたテキスト内の文字の分布によって、それぞれの文字に割り振るbit列を決める。出現頻度が高い文字ほどbit列が短くなる。具体的には頻度の高い文字から順番に0, 10, 110, ... , 1...10, 1...11と符号を割り振っていく。
詳細はWikipediaとかを見ると良い。

ハフマン符号 - Wikipedia

折角なので入力したテキストから各文字にbit列を割り振るperlスクリプトを書いてみた。

#!/usr/local/bin/perl
use strict;
use warnings;

my %freq;
while (<>) {
  chomp;
  my @a = split(//);
  foreach (@a) { $freq{$_}++; }
}

my $size   = scalar(keys %freq);
my @sorted = sort{$freq{$a}<=>$freq{$b}}(keys %freq);
my %code;
foreach (@sorted) {
  $code{$_} = "";
}
for (my $i = 1; $i < $size; $i++) {
  $code{$sorted[$i]} = "0$code{$sorted[$i]}";
  for (my $j = 0; $j < $i; $j++) {
    $code{$sorted[$j]} = "1$code{$sorted[$j]}";
  }
}

foreach (@sorted) {
  print "$_($freq{$_}): $code{$_}\n";
}

例えば

$$ cat test.txt
abracadabra

というテキストの各文字をHuffman符号化してみる。

$$ ./huffman.pl < test.txt
c(1): 1111
d(1): 1110
r(2): 110
b(2): 10
a(5): 0

となった。頻度が高い文字ほど短いbit列が割り振られているのがわかる。めでたし。