搜索
首页php教程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".
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系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字节编码。

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

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

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

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

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),如果是奇数,则编码为零电平,并将计数器清零等等。

码农狂喜!微软提出CodePlan,跨168个代码库编码任务,LLM自动化完成码农狂喜!微软提出CodePlan,跨168个代码库编码任务,LLM自动化完成Oct 04, 2023 pm 08:29 PM

对于大模型来说,擅长的是本地化编码任务。如果任务涉及多个相互依赖的文件,LLM无法解决这个问题微软研究人员为此设计了一个名为CodePlan的任务无关的神经网络框架图片论文地址:https://arxiv.org/pdf/2309.12499.pdf论文中,CodePlan综合了多步骤编辑链(chain-of-edits),是一种将程序分析、规划和LLM结合在一起的新方法。一起来具体看看,CodePlan是如何设计的?CodePlan:大模型+规划软件工程活动中,例如软件包迁移、修复静态分析或测

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)