PHP 는 Huff man 인 코딩/디 코딩 의 예제 코드 를 실현 합 니 다.

Huffman 인 코딩 은 데이터 압축 알고리즘 의 일종 이다.우리 가 자주 사용 하 는 zip 압축 의 핵심 은 Huff man 인 코딩 이 고 HTTP/2 에서 Huff man 인 코딩 은 HTTP 머리의 압축 에 사용 된다.
본 고 는 PHP 로 Huffman 인 코딩 과 디 코딩 을 실천 하고 자 합 니 다.
1.인 코딩
글자 수 통계
Huffman 인 코딩 의 첫 번 째 단 계 는 문서 에 있 는 모든 문자 가 나타 나 는 횟수 를 통계 하 는 것 입 니 다.PHP 의 내장 함수 countchars()에서 할 수 있 습 니 다:

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

구조 Huffman 나무
다음은 통계 결과 에 따 르 면 허 프 맨 나 무 를 구성 하고 구조 방법 은 위 키 백과 에서 상세 하 게 설명 되 어 있다.여기에 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 나무의 뿌리 노드 를 가리 킬 것 입 니 다.
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 인 코딩 을 파일 에 기록 하 는 데 몇 가지 주의 할 점 이 있 습 니 다.
인 코딩 사전 과 인 코딩 내용 을 함께 파일 에 쓰 면 경 계 를 구분 할 수 없 기 때문에 각각 사용 하 는 바이트 수 를 파일 에 쓰기 시작 해 야 합 니 다.
PHP 에서 제공 하 는 fwrite()함 수 는 한 번 에 8-bit(한 바이트)또는 8 의 정수 배 bit 를 기록 할 수 있 습 니 다.그러나 Huffman 인 코딩 에서 한 문 자 는 1-bit 만 사용 할 수 있 습 니 다.PHP 는 파일 에 1-bit 만 쓰 는 것 을 지원 하지 않 습 니 다.그래서 우 리 는 스스로 인 코딩 을 맞 추고 8-bit 를 맞 출 때마다 파일 을 써 야 한다.

8 비트 씩 모 아서 쓰 는 거 예요.
제2 조 와 유사 하 게 최종 적 으로 형 성 된 파일 의 크기 는 반드시 8-bit 의 정수 배 이다.그래서 전체 인 코딩 의 크기 가 8001-bit 라면 끝 에 0 7 개 를 채 워 야 합 니 다.

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

디 코딩
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;

테스트
Huff man 인 코딩 위 키 페이지 의 HTML 코드 를 로 컬 에 저장 하여 Huff man 인 코딩 테스트 를 진행 합 니 다.시험 결과:
인 코딩 전:418,504 바이트
인 코딩 후:280,127 바이트
공간 은 33%를 절약 했다.만약 에 원문의 중복 내용 이 비교적 많 으 면 Huffman 인 코딩 이 절약 하 는 공간 은 50%이상 에 이 를 수 있다.
텍스트 내용 을 제외 하고 우 리 는 바 이 너 리 파일 을 Huffman 인 코딩 을 시도 합 니 다.예 를 들 어f.lux 설치 프로그램시험 결 과 는 다음 과 같 습 니 다.
인 코딩 전:770,384 바이트
인 코딩 후:773,076 바이트
인 코딩 후에 오히려 더 큰 공간 을 차지 했다.한편 으로 는 우리 가 사전 을 저장 할 때 별도의 처 리 를 하지 않 아 많은 공간 을 차지 했다.다른 한편,바 이 너 리 파일 에서 각 문자 가 나타 날 확률 이 상대 적 으로 평균 적 이어서 Huffman 인 코딩 의 장점 을 발휘 할 수 없습니다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.