PHP implementiert die Huffman-Kodierung/Dekodierung

Dieser Artikel stellt hauptsächlich die Implementierung der Huffman-Kodierung/Dekodierung in PHP vor. Er hat einen gewissen Referenzwert. Jetzt kann ich ihn mit allen teilen, die ihn brauchen.

Die Huffman-Kodierung ist ein Datenkomprimierungsalgorithmus . Der Kern unserer häufig verwendeten Zip-Komprimierung ist die Huffman-Kodierung, und in HTTP/2 wird die Huffman-Kodierung zum Komprimieren von HTTP-Headern verwendet.

In diesem Artikel wird PHP zum Üben der Huffman-Kodierung und -Dekodierung verwendet.

1. Kodierung

Wortzählung

Der erste Schritt der Huffman-Kodierung besteht darin, die Anzahl der Vorkommen jedes Zeichens im Dokument zu zählen count_chars() kann es tun:

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

Konstruieren Sie den Huffman-Baum

Konstruieren Sie als Nächstes den Huffman-Baum basierend auf den statistischen Ergebnissen. Die Konstruktionsmethode ist ausführlich in Wikipedia beschrieben. Hier ist eine einfache, in PHP geschriebene Version:

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

Nach der Berechnung zeigt $root auf den Wurzelknoten des Huffman-Baums

Generieren Sie ein Codierungswörterbuch basierend auf dem Huffman-Baum

Mit dem Huffman-Baum können Sie ein Wörterbuch zum Kodieren generieren:

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

Datei schreiben

Verwenden Sie das Wörterbuch, um den Dateiinhalt zu kodieren und in die Datei zu schreiben. Beim Schreiben der Huffman-Codierung in eine Datei sind mehrere Dinge zu beachten:

1. Nachdem das Codierungswörterbuch und der Codierungsinhalt zusammen in die Datei geschrieben wurden, ist es unmöglich, ihre Grenzen zu unterscheiden Sie müssen die Datei beginnen, die Anzahl der Bytes zu schreiben, die sie jeweils belegen.

2. Die von PHP bereitgestellte Funktion fwrite() kann 8 Bit (ein Byte) oder ein ganzzahliges Vielfaches von 8 Bit schreiben auf einmal. Bei der Huffman-Codierung kann ein Zeichen jedoch nur durch 1 Bit dargestellt werden, und PHP unterstützt nicht den Vorgang, bei dem nur 1 Bit in die Datei geschrieben wird. Daher müssen wir die Codierung selbst zusammenfügen und die Datei erst schreiben, nachdem alle 8 Bit erhalten wurden.

1. Ähnlich wie beim zweiten Punkt muss die endgültige Dateigröße ein ganzzahliges Vielfaches von 8 Bit sein. Wenn also die Größe der gesamten Kodierung 8001 Bit beträgt, müssen am Ende 7 Nullen hinzugefügt werden

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

Dekodierung

Die Dekodierung der Huffman-Kodierung ist relativ Ganz einfach: Lesen Sie zuerst das Codierungswörterbuch und dekodieren Sie dann die Originalzeichen gemäß dem Wörterbuch.

Während des Dekodierungsprozesses gibt es ein Problem, das beachtet werden muss: Da wir während des Kodierungsprozesses mehrere 0-Bits am Ende der Datei hinzugefügt haben, sollten diese 0-Bits zufällig die Kodierung sein ein bestimmtes Zeichen im Wörterbuch. Dies führt zu einer falschen Dekodierung.

Wenn also während des Dekodierungsvorgangs die Anzahl der dekodierten Zeichen die Dokumentlänge erreicht, wird die Dekodierung gestoppt.

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

Wir haben den HTML-Code der Huffman-Kodierungs-Wiki-Seite lokal gespeichert und den Huffman-Kodierungstest durchgeführt. Die Testergebnisse:

Vor der Kodierung : 418.504 Bytes

nach der Kodierung: 280.127 Bytes

33 % Platzersparnis Wenn der Originaltext viele wiederholte Inhalte enthält, kann der durch die Huffman-Kodierung eingesparte Platz mehr als 50 betragen %.

Zusätzlich zum Textinhalt versuchen wir, eine Binärdatei wie das f.lux-Installationsprogramm zu kodieren. Die Testergebnisse sind wie folgt:

Vorher Kodierung: 770.384 Bytes

Nach der Kodierung: 773.076 Bytes

Nach der Kodierung nimmt es mehr Platz ein, weil wir beim Speichern keine zusätzliche Verarbeitung durchführen Wörterbuch, das viel Platz einnimmt. Andererseits ist in Binärdateien die Wahrscheinlichkeit, dass jedes Zeichen auftritt, relativ gleichmäßig und die Vorteile der Huffman-Codierung können nicht genutzt werden.

Verwandte Empfehlungen:

Verwendung von PHP zur Implementierung einer einfach verknüpften Liste

Das obige ist der detaillierte Inhalt vonPHP implementiert die Huffman-Kodierung/Dekodierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!