PHP實現Huffman編碼/解碼的示例代碼

更新時間：2018年04月20日 14:25:23 作者：切糕糕

本篇文章主要介紹了PHP實現Huffman編碼/解碼的示例代碼，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

Huffman 編碼是一種數據壓縮算法。我們常用的 zip 壓縮，其核心就是 Huffman 編碼，還有在 HTTP/2 中，Huffman 編碼被用于 HTTP 頭部的壓縮。

本文就來用 PHP 來實踐一下 Huffman 編碼和解碼。

1. 編碼

字數統計

Huffman編碼的第一步就是要統計文檔中每個字符出現的次數，PHP的內置函數 count_chars() 就可以做到：

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

構造Huffman樹

接下來根據統計結果構造Huffman樹，構造方法在 Wikipedia 有詳細的描述。這里用PHP寫了一個簡易版的：

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

// 構造樹的層級關系，思想見wiki：https://zh.wikipedia.org/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);

經過計算之后，$root 就會指向 Huffman 樹的根節(jié)點

根據Huffman樹生成編碼字典

有了 Huffman 樹，就可以生成用于編碼的字典：

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);

寫文件

運用字典將文件內容進行編碼，并寫入文件。將Huffman編碼寫入文件的有幾個注意的地方：

將編碼字典和編碼內容一起寫入文件后，就沒法區(qū)分他們的邊界了，因此需要在文件開始寫入他們各自占用的字節(jié)數

PHP提供的 fwrite() 函數一次能寫入 8-bit（一個字節(jié)）或者是 8的整數倍個bit。但Huffman編碼中，一個字符可能只使用 1-bit 表示，PHP不支持只往文件中寫入 1-bit 這種操作。所以需要我們自行對編碼進行拼接，每湊齊 8-bit 才寫入文件。

每湊齊8-bit才寫入

與第二條類似，最終形成的文件大小一定是 8-bit 的整數倍。所以如果整個編碼的大小是 8001-bit的話，還要在末尾補上 7個 0

$dictString = serialize($dict);
// 寫入字典和編碼各自占用的字節(jié)數
$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);

解碼

Huffman編碼的解碼相對簡單：先讀取編碼字典，然后根據字典解碼出原始字符。

解碼過程有個問題需要注意：由于我們在編碼過程中，在文件末尾補齊了幾個0-bit，如果這些 0-bit 在字典中恰巧是某個字符的編碼時，就會造成錯誤的解碼。

所以解碼過程中，當已解碼的字符數達到文檔長度時，就要停止解碼。

<?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;

試驗

我們將Huffman編碼Wiki頁的HTML代碼保存到本地，進行Huffman編碼測試，試驗結果：