PHP는 허프만 인코딩/디코딩을 구현합니다.-PHP 튜토리얼-php.cn

PHP는 허프만 인코딩/디코딩을 구현합니다.

不言

풀어 주다： 2023-03-24 13:14:01

원래의

1798명이 탐색했습니다.

이 글은 주로 PHP에서의 허프만 인코딩/디코딩 구현을 소개합니다. 이는 특정 참고 가치가 있습니다. 이제 필요한 친구들이 참고할 수 있습니다.

허프만 인코딩은 데이터 압축 알고리즘입니다. 우리가 일반적으로 사용하는 zip 압축의 핵심은 Huffman 인코딩이며, HTTP/2에서는 Huffman 인코딩이 HTTP 헤더 압축에 사용됩니다.

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

1. 코딩

단어 개수

허프만 코딩의 첫 번째 단계는 문서에서 각 문자의 발생 횟수를 계산하는 것입니다. PHP의 내장 함수 count_chars()를 사용하면 됩니다. count_chars() 就可以做到：

$input = file_get_contents(&#39;input.txt&#39;);$stat = count_chars($input, 1);

로그인 후 복사

构造Huffman树

接下来根据统计结果构造Huffman树，构造方法在 Wikipedia 有详细的描述。这里用PHP写了一个简易版的：

$huffmanTree = [];foreach ($stat as $char => $count) {    $huffmanTree[] = [        &#39;k&#39; => chr($char),        &#39;v&#39; => $count,        &#39;left&#39; => null,        &#39;right&#39; => 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[&#39;v&#39;] === $b[&#39;v&#39;]) {            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 就会指向 Huffman 树的根节点

根据Huffman树生成编码字典

有了 Huffman 树，就可以生成用于编码的字典：

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

로그인 후 복사

写文件

运用字典将文件内容进行编码，并写入文件。将Huffman编码写入文件的有几个注意的地方：

将编码字典和编码内容一起写入文件后，就没法区分他们的边界了，因此需要在文件开始写入他们各自占用的字节数

PHP提供的 fwrite()

$dictString = serialize($dict);// 写入字典和编码各自占用的字节数$header = pack(&#39;VV&#39;, strlen($dictString), strlen($input));
fwrite($outFile, $header);// 写入字典本身fwrite($outFile, $dictString);// 写入编码的内容$buffer = &#39;&#39;;$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, &#39;0&#39;));
    fwrite($outFile, chr($char));
}
fclose($outFile);

로그인 후 복사

허프만 트리 구축

다음으로, 통계적 결과를 바탕으로 허프만 트리를 구축합니다. 구축 방법은 위키피디아에 자세히 설명되어 있습니다. 다음은 PHP로 작성된 간단한 버전입니다.

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

로그인 후 복사

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

허프만 사용 트리, 인코딩을 위한 사전을 생성할 수 있습니다:
rrreee

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

인코딩 사전을 작성하고 인코딩 내용을 파일에 함께 작성한 후에는 경계를 구분하는 것이 불가능하므로 반드시 파일 시작 바이트 수

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

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

rrreee

Decoding

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

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

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

rrreee

Test

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

인코딩 전: 418,504바이트

인코딩 후: 280,127바이트 🎜🎜🎜공간 절약 33 %.원본 텍스트에 반복되는 내용이 많은 경우 허프만 인코딩으로 절약한 공간은 50% 이상에 달할 수 있습니다. 🎜🎜텍스트 내용 외에도 f. lux 설치 프로그램 테스트 결과는 다음과 같습니다. 🎜🎜🎜인코딩 전: 770,384바이트 🎜🎜인코딩 후: 773,076바이트 🎜🎜🎜인코딩 후에는 사전을 저장할 때 더 많은 공간을 차지합니다. 추가 처리를 하지 않아 공간을 많이 차지합니다. 반면 바이너리 파일에서는 각 문자가 나타날 확률이 상대적으로 균일하여 허프만 코딩의 장점을 활용할 수 없습니다. 🎜🎜관련 권장 사항: 🎜🎜🎜🎜PHP를 사용하여 단일 연결 목록 구현🎜🎜

위 내용은 PHP는 허프만 인코딩/디코딩을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!