PHP는 허프만 인코딩/디코딩을 구현합니다.
- 不言원래의
- 2018-04-20 10:45:081770검색
이 글은 주로 PHP에서의 허프만 인코딩/디코딩 구현을 소개합니다. 이는 특정 참고 가치가 있습니다. 이제 필요한 친구들이 참고할 수 있습니다.
허프만 인코딩은 데이터 압축 알고리즘입니다. 우리가 일반적으로 사용하는 zip 압축의 핵심은 Huffman 인코딩이며, HTTP/2에서는 Huffman 인코딩이 HTTP 헤더 압축에 사용됩니다.
이 기사에서는 PHP를 사용하여 허프만 인코딩 및 디코딩을 연습합니다.
1. 코딩
단어 개수
허프만 코딩의 첫 번째 단계는 문서에서 각 문자의 발생 횟수를 계산하는 것입니다. PHP의 내장 함수 count_chars()를 사용하면 됩니다. 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 树的根节点
根据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()$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;
계산 후 $root는 허프만 트리의 루트 노드를 가리킵니다.
- 허프만 트리를 기반으로 코딩 사전 생성
-
허프만 사용 트리, 인코딩을 위한 사전을 생성할 수 있습니다:
rrreee 파일 쓰기
사전을 사용하여 파일 내용을 인코딩하고 파일에 씁니다. 허프만 인코딩을 파일에 작성할 때 주의할 점이 몇 가지 있습니다.
인코딩 사전을 작성하고 인코딩 내용을 파일에 함께 작성한 후에는 경계를 구분하는 것이 불가능하므로 반드시 파일 시작 바이트 수
PHP에서 제공하는 fwrite() 함수는 한 번에 8비트(1바이트) 또는 8비트의 정수배를 쓸 수 있습니다. 그러나 허프만 인코딩에서는 문자가 1비트로만 표현될 수 있으며, PHP는 파일에 1비트만 쓰는 작업을 지원하지 않습니다. 따라서 우리는 인코딩을 직접 연결해야 하며 매 8비트를 얻은 후에만 파일을 작성해야 합니다.
두 번째 항목과 마찬가지로 최종 파일 크기는 8비트의 정수배가 되어야 합니다. 따라서 전체 인코딩의 크기가 8001비트인 경우 7 0
rrreee
Decoding그래서 디코딩 프로세스 중에 디코딩된 문자 수가 문서 길이에 도달하면 디코딩이 중지됩니다.허프만 인코딩은 비교적 간단합니다. 먼저 인코딩 사전을 읽은 다음 사전에 따라 원래 문자를 디코딩합니다.
디코딩 과정에서 주의해야 할 문제가 있습니다. 인코딩 과정에서 파일 끝에 여러 개의 0비트를 추가했기 때문에 이 0비트가 특정 파일의 인코딩인 경우 문자가 사전에 있으면 디코딩 오류가 발생합니다.
rrreee
Test
허프만 인코딩 위키 페이지의 HTML 코드를 로컬에 저장하고 허프만 인코딩 테스트를 수행했습니다. 테스트 결과:
위 내용은 PHP는 허프만 인코딩/디코딩을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!