PHPでハフマン符号化をしたい！

はじめに

IPA試験では実際のプログラミング言語ではなく2023年4月から擬似言語となったようですが、私も受けてみようと思っていまして、面白そうな内容があったのでPHPでやってみました。

それがハフマン符号化です。
どう考えても手で図を描いた方が早いのですが、まあロマンということで！

ちなみにPython3でやっている人もいました。こっちの方がハフマンについての詳細説明書いてるっぽいのでまず「ハフマン符号化ってなんだよ」って人は見てみるといいかもです。

注意

ここでは上から下まで順に処理していくという説明でしたいので関数使わずにつくります。(いや、今思うと関数使った方がわかりやすかったかもしれない...?)

コード

説明やらもコード内のコメントを参考にしてもらえると！

$str = "AAAABBCDCDDACCAAAAA";

$freq = []; // 連想配列入れる用

// 1: それぞれの文字の出現回数を $freq に入れる
// array_count_values(str_split($str)); でも可
$len = strlen($str);
for ($i = 0; $i < $len; ++$i) {
    $c = $str[$i];
    if (!isset($freq[$c]))
        $freq[$c] = 0;

    $freq[$c]++;
}

echo "出現回数 (\$freq): ";
var_dump($freq);

// 2: バブルソートを使って $freq を降順に並び変え
// arsort($freq); でも可

$keys = array_keys($freq); // 連想配列のキーだけの配列

// バブルソート
$size = count($keys);
for ($i = 0; $i < $size; $i++) {
    for ($j = $i + 1; $j < $size; ++$j) {
        if ($freq[$keys[$i]] < $freq[$keys[$j]]) {
            $tmp = $keys[$i];
            $keys[$i] = $keys[$j];
            $keys[$j] = $tmp;
        }
    }
}

$sorted = []; // ソート後の $freq を一時的に入れるやつ
for ($i = 0; $i < $size; ++$i) {
    $sorted[$keys[$i]] = $freq[$keys[$i]];
}

$freq = $sorted; // $freq にソート済みのものを入れる
unset($sorted); // $sorted を解放

echo "\nソート後 (\$freq): ";
var_dump($freq);

// 3: ハフマンの木 (これが本題)
$tree = [];

$latestNode = [];

// ハフマンの木をつくる
for ($i = 0; $i < $size - 1; $i++) {
    // 配列の右から最小２つを取り出す
    $keyL = array_key_last($freq);
    $valueL = array_pop($freq);
    $keyR = array_key_last($freq);
    $valueR = array_pop($freq);

    $key = $keyL . $keyR;
    $freq[$key] = $valueL + $valueR;

    // 親ノード (節) をつくる
    $node = [
        'freq' => $freq[$key], // 合算した出現回数
        'value' => [ // 子ノード
            'left' => [
                'freq' => $valueL, // 左側の子の出現回数
                'value' => strlen($keyL) > 1 ? $latestNode['value'] : $keyL
            ],
            'right' => [
                'freq' => $valueR, // 右側の子の出現回数
                'value' => strlen($keyR) > 1 ? $latestNode['value'] : $keyR
            ]
        ]
    ];

    $latestNode = $node;

    arsort($freq); // 出現回数の配列を再整列 (ここではPHP標準関数を使い、中身は省略)

    echo "\n" . $i + 1 . "回目: ";
    echo "\n- \$node: ";
    var_dump($node);
    echo "- \$freq: ";
    var_dump($freq);
}

$tree = $latestNode; // 最も親の節が ハフマンの木 となる

// 4: ここから符号化をする

$bitMapping = []; // ビット表現を入れる

$stack = [[$tree, ""]]; // [ノード, これまでのビット列] のペアをスタックに積む

while (!empty($stack)) {
    list($node, $code) = array_pop($stack);

    // 葉(文字)ならビット列を保存
    if (!is_array($node['value'])) {
        $bitMapping[$node['value']] = $code;
        continue;
    }
    
    $stack[] = [$node['value']['right'], $code . "1"]; // 右側の子をスタックに積む
    $stack[] = [$node['value']['left'], $code . "0"]; // 左側の子をスタックに積む
}

echo "\nビット表現: ";
var_dump($bitMapping);

結果

以下は出力結果です。

出現回数 ($freq): array(4) {
  ["A"]=>
  int(10)
  ["B"]=>
  int(2)
  ["C"]=>
  int(4)
  ["D"]=>
  int(3)
}

ソート後 ($freq): array(4) {
  ["A"]=>
  int(10)
  ["C"]=>
  int(4)
  ["D"]=>
  int(3)
  ["B"]=>
  int(2)
}

1回目: 
- $node: array(2) {
  ["freq"]=>
  int(5)
  ["value"]=>
  array(2) {
    ["left"]=>
    array(2) {
      ["freq"]=>
      int(2)
      ["value"]=>
      string(1) "B"
    }
    ["right"]=>
    array(2) {
      ["freq"]=>
      int(3)
      ["value"]=>
      string(1) "D"
    }
  }
}
- $freq: array(3) {
  ["A"]=>
  int(10)
  ["BD"]=>
  int(5)
  ["C"]=>
  int(4)
}

2回目: 
- $node: array(2) {
  ["freq"]=>
  int(9)
  ["value"]=>
  array(2) {
    ["left"]=>
    array(2) {
      ["freq"]=>
      int(4)
      ["value"]=>
      string(1) "C"
    }
    ["right"]=>
    array(2) {
      ["freq"]=>
      int(5)
      ["value"]=>
      array(2) {
        ["left"]=>
        array(2) {
          ["freq"]=>
          int(2)
          ["value"]=>
          string(1) "B"
        }
        ["right"]=>
        array(2) {
          ["freq"]=>
          int(3)
          ["value"]=>
          string(1) "D"
        }
      }
    }
  }
}
- $freq: array(2) {
  ["A"]=>
  int(10)
  ["CBD"]=>
  int(9)
}

3回目: 
- $node: array(2) {
  ["freq"]=>
  int(19)
  ["value"]=>
  array(2) {
    ["left"]=>
    array(2) {
      ["freq"]=>
      int(9)
      ["value"]=>
      array(2) {
        ["left"]=>
        array(2) {
          ["freq"]=>
          int(4)
          ["value"]=>
          string(1) "C"
        }
        ["right"]=>
        array(2) {
          ["freq"]=>
          int(5)
          ["value"]=>
          array(2) {
            ["left"]=>
            array(2) {
              ["freq"]=>
              int(2)
              ["value"]=>
              string(1) "B"
            }
            ["right"]=>
            array(2) {
              ["freq"]=>
              int(3)
              ["value"]=>
              string(1) "D"
            }
          }
        }
      }
    }
    ["right"]=>
    array(2) {
      ["freq"]=>
      int(10)
      ["value"]=>
      string(1) "A"
    }
  }
}
- $freq: array(1) {
  ["CBDA"]=>
  int(19)
}

ビット表現: array(4) {
  ["C"]=>
  string(2) "00"
  ["B"]=>
  string(3) "010"
  ["D"]=>
  string(3) "011"
  ["A"]=>
  string(1) "1"
}