PHP의 Huffman 인코딩/디코딩 단계에 대한 자세한 설명

이번에는 PHP에서 허프만 인코딩/디코딩을 구현하는 단계에 대해 자세히 설명하겠습니다. PHP에서 허프만 인코딩/디코딩을 구현할 때 주의사항은 무엇인가요?

이 기사에서는 PHP를 사용하여 허프만 인코딩 및 디코딩을 연습합니다.

1. 코딩

단어 개수

Huffman 코딩 첫 번째 단계는 PHP의 내장 함수 count_chars()를 사용하여 다음을 수행할 수 있습니다.

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

허프만 트리 구축

다음으로, 통계 결과를 바탕으로 허프만 트리를 구축합니다. 구성 방법은 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[&#39;v&#39;] < $b[&#39;v&#39;] ? -1 : 1;
  });
  $a = array_shift($huffmanTree);
  $b = array_shift($huffmanTree);
  $huffmanTree[] = [
    &#39;v&#39; => $a[&#39;v&#39;] + $b[&#39;v&#39;],
    &#39;left&#39; => $b,
    &#39;right&#39; => $a,
  ];
}
$root = current($huffmanTree);

계산 후 $root는 허프만 트리의 루트 노드를 가리킵니다.

허프만 트리를 기반으로 코딩 사전을 생성합니다.

허프만 트리를 사용하면 다음을 생성할 수 있습니다. 코딩 사전 사전:

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

파일 쓰기

사전을 사용하여 파일 내용을 인코딩하고 파일에 씁니다. 허프만 인코딩을 파일에 작성할 때 주의할 점이 몇 가지 있습니다.

인코딩 사전을 작성하고 내용을 파일에 함께 작성한 후에는 경계를 구분할 수 없으므로 그들이 차지하는 바이트를 기록해야 합니다. PHP에서 제공하는 fwrite() 함수는 한 번에 8비트(1바이트) 또는 8비트의 정수배를 쓸 수 있습니다. 그러나 허프만 인코딩에서는 문자가 1비트로만 표현될 수 있으며, PHP는 파일에 1비트만 쓰는 작업을 지원하지 않습니다. 따라서 우리는 인코딩을 직접 연결해야 하며 매 8비트를 얻은 후에만 파일을 작성해야 합니다.

8비트를 얻을 때마다 쓰기

두 번째 항목과 마찬가지로 최종 파일 크기는 8비트의 정수배가 되어야 합니다. 따라서 전체 인코딩의 크기가 8001비트인 경우 7 0

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

Decoding

허프만 인코딩은 비교적 간단합니다. 먼저 인코딩 사전을 읽은 다음 사전에 따라 원래 문자를 디코딩합니다.

디코딩 과정에서 주의해야 할 문제가 있습니다. 인코딩 과정에서 파일 끝에 여러 개의 0비트를 추가했기 때문에 이 0비트가 특정 파일의 인코딩인 경우 문자가 사전에 있으면 디코딩 오류가 발생합니다.

그래서 디코딩 프로세스 중에 디코딩된 문자 수가 문서 길이에 도달하면 디코딩이 중지됩니다.

<?php
$content = file_get_contents(&#39;a.out&#39;);
// 读出字典长度和编码内容长度
$header = unpack(&#39;VdictLen/VcontentLen&#39;, $content);
$dict = unserialize(substr($content, 8, $header[&#39;dictLen&#39;]));
$dict = array_flip($dict);
$bin = substr($content, 8 + $header[&#39;dictLen&#39;]);
$output = &#39;&#39;;
$key = &#39;&#39;;
$decodedLen = 0;
$i = 0;
while (isset($bin[$i]) && $decodedLen !== $header[&#39;contentLen&#39;]) {
  $bits = decbin(ord($bin[$i]));
  $bits = str_pad($bits, 8, &#39;0&#39;, STR_PAD_LEFT);
  for ($j = 0; $j !== 8; $j++) {
    // 每拼接上 1-bit，就去与字典比对是否能解码出字符
    $key .= $bits[$j];
    if (isset($dict[$key])) {
      $output .= $dict[$key];
      $key = &#39;&#39;;
      $decodedLen++;
      if ($decodedLen === $header[&#39;contentLen&#39;]) {
        break;
      }
    }
  }
  $i++;
}
echo $output;

Test

허프만 인코딩 위키 페이지의 HTML 코드를 로컬에 저장하고 허프만 인코딩 테스트를 진행했습니다. 테스트 결과:

인코딩 전: 418,504바이트

인코딩 후: 280,127바이트

space. 원본 텍스트에 반복되는 내용이 많은 경우 허프만 인코딩으로 절약한 공간은 50% 이상에 달할 수 있습니다.

텍스트 내용 외에도 다음과 같은 바이너리 파일을 허프만 인코딩해 보겠습니다. f.lux 설치 프로그램, 실험 결과는 다음과 같습니다.

인코딩 전: 770,384바이트

인코딩 후: 773,076바이트

인코딩 후에는 한편으로는 더 많은 공간을 차지하기 때문입니다. 사전을 저장하고 추가 처리를 수행하지 않으며 더 많은 공간을 차지합니다. 반면 바이너리 파일에서는 각 문자가 나타날 확률이 상대적으로 균일하여 허프만 코딩의 장점을 활용할 수 없습니다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!

추천 도서:

PHP 빠른 정렬 알고리즘을 사용하는 단계에 대한 자세한 설명

SPL

을 기반으로 PHP에서 구현한 반복기 단계에 대한 자세한 설명

위 내용은 PHP의 Huffman 인코딩/디코딩 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!