Was ist Huffman-Kodierung? Wie implementiert man Huffman-Kodierung und -Dekodierung in PHP?

Was ist Huffman-Codierung? Huffman-Codierung ist ein Datenkomprimierungsalgorithmus. Der Kern unserer häufig verwendeten Zip-Komprimierung ist die Huffman-Kodierung, und in HTTP/ wird die Huffman-Kodierung zum Komprimieren von HTTP-Headern verwendet. In diesem Artikel werde ich Ihnen die Implementierungsmethode der Huffman-Kodierung und -Dekodierung in PHP vorstellen.

1. Huffman-Kodierung

Wortzählung

Der erste Schritt der Huffman-Kodierung besteht darin, die Anzahl der Vorkommen jedes Zeichens im Dokument zu zählen. PHP Die integrierte Funktion count_chars() kann Folgendes tun:

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

Konstruieren Sie einen Huffman-Baum

Als nächstes erstellen Sie einen Huffman-Baum basierend auf den statistischen Ergebnissen. Die Konstruktionsmethode wird im Detail beschrieben Wikipedia. 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

Ja. 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:

Nachdem das Codierungswörterbuch und der Codierungsinhalt zusammen in die Datei geschrieben wurden, ist es unmöglich, ihre Grenzen zu unterscheiden, daher müssen sie geschrieben werden der Anfang der Datei. Anzahl der belegten Bytes

Die von PHP bereitgestellte Funktion fwrite() kann jeweils 8 Bit (ein Byte) oder ein ganzzahliges Vielfaches von 8 Bit schreiben. 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.

Alle 8-Bit-Daten schreiben

Ähnlich wie beim zweiten Element 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);

2. Dekodierung der Huffman-Kodierung

Dekodierung der Huffman-Kodierung Relativ 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;

3. Test

Wir haben den HTML-Code der Huffman-Coding-Wiki-Seite lokal gespeichert und den Huffman-Coding-Test durchgeführt:

Codierung Vorher: 418.504 Bytes

Nach der Codierung: 280.127 Bytes

Der Speicherplatz wird um 33 % gespart. Wenn der Originaltext viele wiederholte Inhalte enthält, kann der durch die Huffman-Codierung eingesparte Speicherplatz erreicht werden mehr als 50 %.

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

Kodierung nach: 773.076 Bytes

nimmt nach der Kodierung mehr Platz ein. Einerseits führen wir beim Speichern des Wörterbuchs keine zusätzliche Verarbeitung durch, was viel in Anspruch nimmt des Raumes. 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:

PHP kodiert und dekodiert URL-Parameter

Das obige ist der detaillierte Inhalt vonWas ist Huffman-Kodierung? Wie implementiert man Huffman-Kodierung und -Dekodierung in PHP?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!