Maison php教程 php手册 基于静态huffman编码的压缩

基于静态huffman编码的压缩

Jun 06, 2016 pm 07:31 PM
压缩 basé sur 编码 statique

名词解释:哈夫曼编码(HuffmanCoding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。 实现过程: 1.计算每个字符在字符串中出现的频率作为构建h

名词解释:哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。

实现过程:

1.计算每个字符在字符串中出现的频率作为构建huffman树的权重

2.构建huffman树

3.建立每个字符对应的编码表

4.重建字符串编码,既压缩字符串

5.解压时根据先前的huffman树和字符位长度还原字符串
    <?php   
    /**
    基于静态huffman编码的压缩[PHP语言实现]
    author:        lajabs
    email:        aGl0dHlvQGdtYWlsLmNvbQ==

    本文以PHP作为描述语言较详细讲解huffman树原理及应用
    因保证程序可读性,故不做优化.

    */



    class huffman
    {
            /**
             * 压缩入口
             * $str:待压缩的字符串
             */
            public function encode($str)
            {
                    $len=strlen($str);
                    //计算每个字符权重值(出现的频度)<这边可以做成概率表>
                    for($i=0;$i<$len;$i++)        $array[ord($str{$i})]++;

                    $HuffmanArray=array();
                    asort($array);
                    /**
                     * 构造huffman树,时间复杂度O(nlogn)
                     * 选择两个使用频率较小<字符在字符串中出现的次数>的结点合并生成出一个树
                     */
                    while ($item1 = each($array))
                    {
                            $item2 = each($array);
                            //构建huffman树
                            $this->creat_tree($item1,$item2,$array,$HuffmanArray);
                            //反复排序<优化这步可在构造树时用插入排序算法完成>
                            asort($array);
                    }


                    $HuffmanArray=array_shift($HuffmanArray);
                    //构建编码表<这步可优化为构建树时一同生成>
                    $tab=null;
                    $code_tab=$this->creat_tab($HuffmanArray,$tab);
                    //压缩&转换整个字符串为二进制表达式
                    $binary=null;
                    for($i=0;$i<$len;$i++)        $binary.=$tab[ord($str{$i})];        
                    //转化为压缩后的字符串
                    $code=$this->encode_bin($binary);
                    //静态huffman编码算法压缩后需保留huffman树
                    return array('tree'=>$HuffmanArray,'len'=>strlen($binary),'code'=>$code);
            }

            /**
             * 解压缩入口
             * $huffman:解压所使用的huffman树
             * $str:被压缩的字符
             * $blen:压缩前的位长度
             */
            public function decode($huffman,$str,$blen)
            {
                    $len=strlen($str);
                    $binary=null;
                    //将编码解为二进制表达式
                    for($i=0;$i<$len;$i++)        
                    $binary.=str_pad(base_convert(ord($str{$i}),10,2),8,'0',STR_PAD_LEFT);
                    //去除补码
                    $binary=substr($binary,0,$blen);
                    //从hufman树中配比相应的编码
                    return $this->decode_tree($binary,$huffman,$huffman);
            }

            /**
             * 将压缩后的二进制表达式再转为字符串
             * $binary:二进制表达式字串
             */
            private function encode_bin($binary)
            {
                    $len=strlen($binary);
                    //二进制转字符需要整8位,不足8位补0
                    $blen=$len+8-$len%8;
                    $binary=str_pad($binary,$blen,'0');
                    $encode=null;
                    //每8位转为一个字符
                    for($i=7;$i<$blen;$i+=8)
                    {
                            $frag=substr($binary,$i-7,8);
                            $encode.=chr(base_convert($frag,2,10));
                    }
                    return $encode;
            }

            /**
             * 构造huffman树,使用贪婪算法选择最小的两个元素作为树的子节点
             * $item1:权重最小的元素1
             * $item2:权重次小的元素2
             * $array:所有字符出现次数表<权重表>
             * $HuffmanArray:保存生成的huffman树结构
             */
            private function creat_tree($item1,$item2,&$array,&$HuffmanArray)
            {
                    list($k,$v)=$item1;
                    list($k2,$v2)=$item2;
                    //假设当前树的左右节点为空节点
                    $c1=$k;
                    $c2=$k2;
                    //判断两个元素若为树则直接作为节点并入主树
                    if(isset($HuffmanArray[$k2]))
                    {
                            $c2=$HuffmanArray[$k2];        
                            unset($HuffmanArray[$k2]);
                    }
                    if(isset($HuffmanArray[$k]))
                    {
                            $c1=$HuffmanArray[$k];
                            unset($HuffmanArray[$k]);
                    }
                    //设置树结点权值
                    $array[$k2]=$v+$v2;                                                        
                    //合并节点后删除元素
                    unset($array[$k]);
                    //合并到huffman树中
                    $HuffmanArray[$k2]=array(0=>$c1,1=>$c2);        
            }


            /**
             * 广度优先遍历树,得到所有原字符对应的二进制表达式<01010...>
             * $tree:已经构建好的huffman树
             * $tab:编码表,保存所有字符对应的编码
             * $a0:左遍历树的路径<11010...>
             * $a1:右遍历树的路径
             */
            private function creat_tab($tree,&$tab,$a0=null,$a1=null)
            {
                    if($tree==null) return;
                    //遍历左右子树
                    foreach($tree as $node=>$ctree)
                    {
                            if(is_array($ctree))
                            {
                                    //判断未到达叶子节点时再向下遍历
                                    $this->creat_tab($ctree,$tab,$a0.$node,$a1.$node);
                            }
                            else
                            {
                                    //遍历到叶子节点<原字符ascii码>时的所有路径,既二进制表达式,下同
                                    $tab[$ctree]=${'a'.$node}.$node;
                            }
                    }
            }

            /**
             * 使用进制表达式深度优先遍历树,0为左子树,1为右子树,而到根节点,即为二进制表达式所指向的原字符
             * $binary:二进制表达式字串
             * $huffman:huffman树
             * $tree:当前所遍历的子树
             * $i:指向二进制表达式字串的<指针>
             * $code:解码后的字符串
             */
            private function decode_tree($binary,$huffman,$tree,$i=0,$code=null)
            {
                    $lr=$binary{$i};
                    //遍历完成
                    if($lr==null) return $code;
                    //判断是否到根节点,根节点既为二进制表达式对应的原字符ascii码
                    if(is_array($tree[$lr]))
                    {
                            //继续向下遍历子树
                            return $this->decode_tree($binary,$huffman,$tree[$lr],$i+1,$code);
                    }
                    else
                    {
                            //将二进制表达式解码为原字符
                            $code.=chr($tree[$lr]);
                            return $this->decode_tree($binary,$huffman,$huffman,$i+1,$code);
                    }
            }
    }
    ?>
Copier après la connexion
    $str='
    In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
    ';

    $huffman=new huffman();
    $obj=$huffman->encode($str);
    echo '压缩前的编码长度:',strlen($str),"\n";
    echo '压缩后的编码:',"\n";
    var_dump($obj['code']);
    echo '解压后的字符:',$huffman->decode($obj['tree'],$obj['code'],$obj['len']);
Copier après la connexion
压缩前的编码长度:587压缩后的编码:string(330) "sp閉h颚?6鵞+王d挓吷s霒zk洚磗脎|t?*?;娳9蹴??>楏4O3 5 F凣rRuJ解压后的字符:In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
Copier après la connexion
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Comment activer ou désactiver la compression de la mémoire sur Windows 11 Comment activer ou désactiver la compression de la mémoire sur Windows 11 Sep 19, 2023 pm 11:33 PM

Avec la compression de la mémoire sous Windows 11, votre appareil s'étouffera même avec une quantité limitée de RAM. Dans cet article, nous allons vous montrer comment activer ou désactiver la compression de la mémoire sous Windows 11. Qu’est-ce que la compression de la mémoire ? La compression de la mémoire est une fonctionnalité qui compresse les données avant de les écrire dans la RAM, fournissant ainsi plus d'espace de stockage. Bien entendu, davantage de données stockées dans la mémoire physique se traduisent par un fonctionnement plus rapide du système et de meilleures performances globales. Cette fonctionnalité est activée par défaut dans Windows 11, mais si elle n'est pas active, vous pouvez la désactiver ou la réactiver. Comment activer la compression de la mémoire dans Windows 11 ? Cliquez sur la barre de recherche, tapez PowerShell et cliquez sur

Paramètres du taux de compression maximum de 7-zip, comment compresser 7zip au minimum Paramètres du taux de compression maximum de 7-zip, comment compresser 7zip au minimum Jun 18, 2024 pm 06:12 PM

J'ai découvert que le package compressé téléchargé à partir d'un certain site Web de téléchargement sera plus volumineux que le package compressé d'origine après décompression. La différence est de plusieurs dizaines de Ko et de dizaines de Mo. S'il est téléchargé sur un disque cloud ou un espace payant, cela n'a pas d'importance. si le fichier est petit, s'il y a beaucoup de fichiers, le coût de stockage sera considérablement augmenté. J'ai fait quelques recherches à ce sujet et je peux en tirer des leçons si nécessaire. Niveau de compression : compression 9 extrême Taille du dictionnaire : 256 ou 384, plus le dictionnaire est compressé, plus il est lent. La différence de taux de compression est plus grande avant 256 Mo, et il n'y a aucune différence de taux de compression après 384 Mo. Taille du mot : maximum 273. Paramètres : f=BCJ2, le taux de compression des paramètres de test et d'ajout sera plus élevé

Knowledge graph : le partenaire idéal des grands modèles Knowledge graph : le partenaire idéal des grands modèles Jan 29, 2024 am 09:21 AM

Les grands modèles linguistiques (LLM) ont la capacité de générer un texte fluide et cohérent, ouvrant de nouvelles perspectives dans des domaines tels que la conversation par intelligence artificielle et l'écriture créative. Cependant, le LLM présente également certaines limites clés. Premièrement, leurs connaissances se limitent aux modèles reconnus à partir des données de formation, sans une véritable compréhension du monde. Deuxièmement, les capacités de raisonnement sont limitées et ne peuvent pas faire de déductions logiques ni fusionner des faits provenant de plusieurs sources de données. Face à des questions plus complexes et ouvertes, les réponses de LLM peuvent devenir absurdes ou contradictoires, ce que l'on appelle des « illusions ». Par conséquent, bien que le LLM soit très utile à certains égards, il présente néanmoins certaines limites lorsqu’il s’agit de problèmes complexes et de situations du monde réel. Afin de combler ces lacunes, des systèmes de génération augmentée par récupération (RAG) ont vu le jour ces dernières années.

Conseils pour réduire la taille du fichier d'enregistrement d'écran Win10 Conseils pour réduire la taille du fichier d'enregistrement d'écran Win10 Jan 04, 2024 pm 12:05 PM

De nombreux amis ont besoin d'enregistrer des écrans pour le travail de bureau ou de transférer des fichiers, mais parfois le problème des fichiers trop volumineux pose beaucoup de problèmes. Ce qui suit est une solution au problème des fichiers trop volumineux, jetons-y un coup d'œil. Que faire si le fichier d'enregistrement d'écran Win10 est trop volumineux : 1. Téléchargez le logiciel Format Factory pour compresser le fichier. Adresse de téléchargement >> 2. Entrez dans la page principale et cliquez sur l'option "Vidéo-MP4". 3. Cliquez sur « Ajouter un fichier » sur la page du format de conversion et sélectionnez le fichier MP4 à compresser. 4. Cliquez sur « Configuration de sortie » sur la page pour compresser le fichier en fonction de la qualité de sortie. 5. Sélectionnez « Faible qualité et taille » dans la liste de configuration déroulante et cliquez sur « OK ». 6. Cliquez sur "OK" pour terminer l'importation des fichiers vidéo. 7. Cliquez sur "Démarrer" pour démarrer la conversion. 8. Une fois terminé, vous pouvez

Plusieurs méthodes de codage courantes Plusieurs méthodes de codage courantes Oct 24, 2023 am 10:09 AM

Les méthodes de codage courantes incluent le codage ASCII, le codage Unicode, le codage UTF-8, le codage UTF-16, le codage GBK, etc. Introduction détaillée : 1. Le codage ASCII est la première norme de codage de caractères, utilisant des nombres binaires de 7 bits pour représenter 128 caractères, y compris des lettres anglaises, des chiffres, des signes de ponctuation, des caractères de contrôle, etc. 2. Le codage Unicode est une méthode utilisée pour représenter ; tous les caractères du monde La méthode d'encodage standard des caractères, qui attribue un point de code numérique unique à chaque caractère 3. Encodage UTF-8, etc.

Analyse approfondie du rôle et de l'utilisation du mot-clé static en langage C Analyse approfondie du rôle et de l'utilisation du mot-clé static en langage C Feb 20, 2024 pm 04:30 PM

Analyse approfondie du rôle et de l'utilisation du mot-clé static en langage C. En langage C, static est un mot-clé très important, qui peut être utilisé dans la définition de fonctions, de variables et de types de données. L'utilisation du mot-clé static peut modifier les attributs de lien, la portée et le cycle de vie de l'objet. Analysons en détail le rôle et l'utilisation du mot-clé static en langage C. Variables et fonctions statiques : les variables définies à l'aide du mot-clé static à l'intérieur d'une fonction sont appelées variables statiques et ont un cycle de vie global.

Comment compresser un dossier et l'envoyer en wps Comment compresser un dossier et l'envoyer en wps Mar 20, 2024 pm 12:58 PM

Les employés de bureau utilisent très fréquemment le logiciel wps au travail. Parfois, ils saisissent plusieurs fichiers par jour, puis les envoient au responsable ou à un emplacement désigné. Alors, comment le logiciel wps compresse-t-il un dossier et le conditionne-t-il pour l'envoi ? . Cette étape de l'opération. Tout d’abord, organisez les fichiers et dossiers que vous souhaitez envoyer dans le même dossier. Si vous avez beaucoup de fichiers, c'est une bonne idée de nommer chaque fichier afin qu'il soit plus facile à identifier lors de l'envoi. Deuxième étape, cliquez cette fois sur ce gros dossier, puis faites un clic droit. Sélectionnez "Ajouter aux archives". Étape 3 : À ce stade, le logiciel nous aidera automatiquement à empaqueter nos fichiers. Sélectionnez « Compresser vers XX.zip ». Ce zip est le format d'emballage, puis cliquez sur Compresser maintenant.​

Comment comprendre correctement les différences entre le packaging et la compression sous Linux Comment comprendre correctement les différences entre le packaging et la compression sous Linux Feb 20, 2024 pm 05:33 PM

Le packaging et la compression sont des opérations couramment utilisées sous Linux, mais de nombreux utilisateurs ont tendance à confondre les deux concepts. Cet article abordera en détail les différences entre le packaging et la compression dans les systèmes Linux et utilisera des exemples de code spécifiques pour aider les lecteurs à mieux comprendre. Tout d’abord, nous devons clarifier la différence entre emballage et compression. Le packaging est la combinaison de plusieurs fichiers ou répertoires en un seul fichier, souvent utilisé pour organiser, archiver ou transférer des fichiers. La compression consiste à compresser un ou plusieurs fichiers via un algorithme pour réduire la taille du fichier, économiser de l'espace de stockage ou accélérer la transmission.

See all articles