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

名词解释:哈夫曼编码(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);
                    }
            }
    }
    ?>
    $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']);
压缩前的编码长度: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".
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
11个常见的分类特征的编码技术11个常见的分类特征的编码技术Apr 12, 2023 pm 12:16 PM

机器学习算法只接受数值输入,所以如果我们遇到分类特征的时候都会对分类特征进行编码,本文总结了常见的11个分类变量编码方法。1、ONE HOT ENCODING最流行且常用的编码方法是One Hot Enoding。一个具有n个观测值和d个不同值的单一变量被转换成具有n个观测值的d个二元变量,每个二元变量使用一位(0,1)进行标识。例如:编码后最简单的实现是使用pandas的' get_dummiesnew_df=pd.get_dummies(columns=[‘Sex’], data=df)2、

utf8编码汉字占多少字节utf8编码汉字占多少字节Feb 21, 2023 am 11:40 AM

utf8编码汉字占3个字节。在UTF-8编码中,一个中文等于三个字节,一个中文标点占三个字节;而在Unicode编码中,一个中文(含繁体)等于两个字节。UTF-8使用1~4字节为每个字符编码,一个US-ASCIl字符只需1字节编码,带有变音符号的拉丁文、希腊文、西里尔字母、亚美尼亚语、希伯来文、阿拉伯文、叙利亚文等字母则需要2字节编码。

深入解析C语言中static关键字的作用和用法深入解析C语言中static关键字的作用和用法Feb 20, 2024 pm 04:30 PM

深入解析C语言中static关键字的作用和用法在C语言中,static是一种非常重要的关键字,它可以被用于函数、变量和数据类型的定义上。使用static关键字可以改变对象的链接属性、作用域和生命周期,下面就来详细地解析一下static关键字在C语言中的作用和用法。static变量和函数:在函数内部使用static关键字定义的变量称为静态变量,它具有全局生命周

如何解决php数据库查询结果编码的问题如何解决php数据库查询结果编码的问题Mar 21, 2023 am 11:49 AM

PHP是一种流行的Web编程语言,可以用于编写动态网页和应用程序。在实际应用中,PHP经常需要与数据库进行交互,进行数据的查询和处理。然而,在使用PHP从数据库中获取结果时,可能会遇到编码的问题,这通常会导致出现乱码。那么,如何解决php数据库查询结果编码的问题呢?

PHP编码小技巧:如何生成带有防伪验证功能的二维码?PHP编码小技巧:如何生成带有防伪验证功能的二维码?Aug 17, 2023 pm 02:42 PM

PHP编码小技巧:如何生成带有防伪验证功能的二维码?随着电子商务和互联网的发展,二维码越来越被广泛应用于各行各业。而在使用二维码的过程中,为了确保产品的安全性和防止伪造,为二维码添加防伪验证功能是十分重要的一环。本文将介绍如何使用PHP生成带有防伪验证功能的二维码,并附上相应代码示例。在开始之前,我们需要准备以下几个必要的工具和库:PHPQRCode:PHP

PHP中私有静态方法的作用及应用场景PHP中私有静态方法的作用及应用场景Mar 23, 2024 am 10:18 AM

PHP中私有静态方法的作用及应用场景在PHP编程中,私有静态方法是一种特殊的方法类型,它只能在定义它的类内部访问,外部无法直接调用。私有静态方法通常用于类的内部逻辑实现,提供了一种封装和隐藏细节的方式,同时又具有静态方法的特性,可以在不实例化类对象的情况下被调用。下面将探讨私有静态方法的作用及应用场景,并提供具体的代码示例。作用:封装和隐藏实现细节:私有静态

hdb3编码规则是啥hdb3编码规则是啥Aug 29, 2023 pm 01:38 PM

编码规则是:1、如果前一个编码是0,当前数据位为0,则编码为0;2、如果前一个编码是0,当前数据位为1,则编码为双极脉冲(+A或-A),并将计数器加1;3、如果前一个编码是1,当前数据位为1,则编码为0,并将计数器加1;4、如果前一个编码是1,当前数据位为0,则根据计数器的奇偶性来确定编码方式,如果是偶数,则编码为(+B或-B),如果是奇数,则编码为零电平,并将计数器清零等等。

快速掌握静态相对定位的技巧与方法快速掌握静态相对定位的技巧与方法Jan 18, 2024 am 11:18 AM

快速静态相对定位是网页开发中非常重要的一种定位方式。它可以使元素相对于其正常位置进行微调的同时,仍然保持在文档流中的位置。在本文中,我将详细介绍快速静态相对定位的使用方法,以及一些常见的应用场景。首先,我们需要了解快速静态相对定位的基本概念。在CSS中,元素的定位方式有四种:静态定位、相对定位、绝对定位和固定定位。静态定位是默认的定位方式,元素的位置通过文档

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

Hot Tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use