PHP实现Huffman编码/解码的示例代码

$input = file_get_contents('input.txt');
$stat = count_chars($input, 1);

$huffmanTree = [];
foreach ($stat as $char => $count) {
  $huffmanTree[] = [
    'k' => chr($char),
    'v' => $count,
    'left' => null,
    'right' => null,
  ];
}

// 构造树的层级关系，思想见wikihttps://zh.wikipedia./wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
$size = count($huffmanTree);
for ($i = 0; $i !== $size - 1; $i++) {
  uasort($huffmanTree, function ($a, $b) {
    if ($a['v'] === $b['v']) {
      return 0;
    }
    return $a['v'] < $b['v'] ? -1 : 1;
  });
  $a = array_shift($huffmanTree);
  $b = array_shift($huffmanTree);
  $huffmanTree[] = [
    'v' => $a['v'] + $b['v'],
    'left' => $b,
    'right' => $a,
  ];
}
$root = current($huffmanTree);

function buildDict($elem, $code = '', &$dict) {
  if (isset($elem['k'])) {
    $dict[$elem['k']] = $code;
  } else {
    buildDict($elem['left'], $code.'0', $dict);
    buildDict($elem['right'], $code.'1', $dict);
  }
}
$dict = [];
buildDict($root, '', $dict);

$dictString = serialize($dict);
// 写入字典和编码各自占用的字节数
$header = pack('VV', strlen($dictString), strlen($input));
fwrite($outFile, $header);
// 写入字典本身
fwrite($outFile, $dictString);

// 写入编码的内容
$buffer = '';
$i = 0;
while (isset($input[$i])) {
  $buffer .= $dict[$input[$i]];
  while (isset($buffer[7])) {
    $char = bindec(substr($buffer, 0, 8));
    fwrite($outFile, chr($char));
    $buffer = substr($buffer, 8);
  }
  $i++;
}
// 末尾的内容如果没有凑齐 8-bit，需要自行补齐
if (!empty($buffer)) {
  $char = bindec(str_pad($buffer, 8, '0'));
  fwrite($outFile, chr($char));
}
fclose($outFile);

<?php
$content = file_get_contents('a.out');

// 读出字典长度和编码内容长度
$header = unpack('VdictLen/VcontentLen', $content);
$dict = unserialize(substr($content, 8, $header['dictLen']));
$dict = array_flip($dict);

$bin = substr($content, 8 + $header['dictLen']);
$output = '';
$key = '';
$decodedLen = 0;
$i = 0;
while (isset($bin[$i]) && $decodedLen !== $header['contentLen']) {
  $bits = decbin(ord($bin[$i]));
  $bits = str_pad($bits, 8, '0', STR_PAD_LEFT);
  for ($j = 0; $j !== 8; $j++) {
    // 每拼接上 1-bit，就去与字典比对是否能解码出字符
    $key .= $bits[$j];
    if (isset($dict[$key])) {
      $output .= $dict[$key];
      $key = '';
      $decodedLen++;
      if ($decodedLen === $header['contentLen']) {
        break;
      }
    }
  }
  $i++;
}
echo $output;