Qu'est-ce que l'encodage Huffman ? Comment implémenter l'encodage et le décodage Huffman en php

Qu'est-ce que le codage Huffman ? Le codage Huffman est un algorithme de compression de données. Le cœur de notre compression zip couramment utilisée est le codage Huffman, et dans HTTP/, le codage Huffman est utilisé pour compresser les en-têtes HTTP. Dans cet article, je partagerai avec vous la méthode d'implémentation de l'encodage et du décodage Huffman en php.

1. Encodage Huffman

Nombre de mots

La première étape de l'encodage Huffman consiste à compter le nombre d'occurrences de chaque caractère dans le document, PHP La fonction intégrée count_chars() peut faire ceci :

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

Construire un arbre de Huffman

Ensuite, construisez un arbre de Huffman basé sur les résultats statistiques. La méthode de construction est décrite dans. détail dans Wikipédia. Voici une version simple écrite en 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[&#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);

Après calcul, $root pointera vers le nœud racine de l'arbre de Huffman

Générer un dictionnaire de codage basé sur l'arbre de Huffman

Avec l'arbre de Huffman, vous pouvez générer un dictionnaire pour l'encodage :

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

Écrire un fichier

Utilisez le dictionnaire pour encoder le contenu du fichier et l'écrire dans le fichier. Il y a plusieurs choses à prendre en compte lors de l'écriture de l'encodage Huffman dans un fichier :

Après avoir écrit le dictionnaire d'encodage et encodé le contenu ensemble dans le fichier, il est impossible de distinguer leurs limites, ils doivent donc être écrits à le début du fichier. Nombre d'octets occupés

La fonction fwrite() fournie par PHP peut écrire 8 bits (un octet) ou un multiple entier de 8 bits à la fois. Cependant, dans le codage Huffman, un caractère peut être représenté par seulement 1 bit, et PHP ne prend pas en charge l'opération d'écriture d'un seul bit dans le fichier. Par conséquent, nous devons épisser l'encodage nous-mêmes et écrire le fichier uniquement après l'obtention de chaque 8 bits.

Écrivez toutes les données de 8 bits.

Semblable au deuxième élément, la taille finale du fichier doit être un multiple entier de 8 bits. Ainsi, si la taille de l'encodage entier est de 8001 bits, 7 0 doivent être ajoutés à la fin

$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. Décodage de l'encodage de Huffman

Encodage de Huffman. Le décodage est relativement simple : lisez d'abord le dictionnaire d'encodage, puis décodez les caractères originaux selon le dictionnaire.

Il y a un problème qui doit être noté lors du processus de décodage : comme nous avons ajouté plusieurs bits 0 à la fin du fichier lors du processus d'encodage, si ces bits 0 s'avèrent être l'encodage de un certain caractère dans le dictionnaire, cela entraînera un décodage incorrect.

Ainsi, pendant le processus de décodage, lorsque le nombre de caractères décodés atteint la longueur du document, le décodage s'arrêtera.

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

Nous avons enregistré le code HTML de la page Wiki de codage Huffman localement et effectué le test de codage Huffman :

Avant encodage : 418 504 octets

Après encodage : 280 127 octets

L'espace économisé est de 33 %. Si le texte original a beaucoup de contenu répété, l'espace économisé par l'encodage Huffman peut atteindre plus de 50 %

En plus du contenu texte, nous essayons d'encoder selon Huffman un fichier binaire, tel que le programme d'installation f.lux. Les résultats des tests sont les suivants :

Avant encodage : 770 384 octets

Après encodage : 773 076 octets

Après encodage, cela prend plus de place. D'une part, on ne fait pas de traitement supplémentaire lors du stockage du dictionnaire, ce qui prend beaucoup de place. beaucoup d'espace. En revanche, dans les fichiers binaires, la probabilité d'apparition de chaque caractère est relativement égale et les avantages du codage de Huffman ne peuvent pas être utilisés.

Recommandations associées :

php encode et décode les paramètres d'URL

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!