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

基于静态huffman编码的压缩

Jun 06, 2016 pm 07:31 PM
压缩 基于 编码 静态

名词解释:哈夫曼编码(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

热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冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

如何在 Windows 11 上启用或禁用内存压缩功能 如何在 Windows 11 上启用或禁用内存压缩功能 Sep 19, 2023 pm 11:33 PM

使用Windows11上的内存压缩,即使RAM量有限,您的设备也会窒息运行。在本文中,我们将向您展示如何在Windows11上启用或禁用内存压缩。什么是内存压缩?内存压缩是一种在将数据写入RAM之前压缩数据的功能,从而在其上提供更多存储空间。当然,存储在物理内存中的更多数据转化为更快的系统运行和更好的整体性能。此功能在Windows11中默认启用,但如果它以某种方式未处于活动状态,您可以禁用或重新启用它。如何在Windows11中启用内存压缩?单击搜索栏,键入powershell,然后从结果中单

7-zip最大压缩率设置,7zip如何压缩到最小 7-zip最大压缩率设置,7zip如何压缩到最小 Jun 18, 2024 pm 06:12 PM

发现某下载网站下载的压缩包,解压后再打包会比原来的压缩包大一些,小的几十Kb的差别,大的几十Mb的差别,如果上传到云盘或付费空间,文件少无所谓,文件多的话,大大的增加储存成本。特意研究了下,有需要的可以借鉴。压缩等级:9-极限压缩字典大小:256或384,字典越压缩越慢,256MB之前压缩率差别较大,384MB后压缩率无差别单词大小:最大273参数:f=BCJ2,测试加参数压缩率会高一些

知识图谱:大模型的理想搭档 知识图谱:大模型的理想搭档 Jan 29, 2024 am 09:21 AM

大型语言模型(LLM)具有生成流畅和连贯文本的能力,为人工智能的对话、创造性写作等领域带来了新的前景。然而,LLM也存在一些关键局限。首先,它们的知识仅限于从训练数据中识别出的模式,缺乏对世界的真正理解。其次,推理能力有限,不能进行逻辑推理或从多个数据源融合事实。面对更复杂、更开放的问题时,LLM的回答可能变得荒谬或矛盾,被称为“幻觉”。因此,尽管LLM在某些方面非常有用,但在处理复杂问题和真实世界情境时,仍存在一定的局限性。为了弥补这些差距,近年来出现了检索增强生成(RAG)系统,其核心思想是

减小win10录屏文件大小的建议 减小win10录屏文件大小的建议 Jan 04, 2024 pm 12:05 PM

许多的小伙伴都需要录屏进行办公或者传输文件,但是有时候会出现文件过大的问题制造了很多麻烦,下面就给大家带来了文件过大的解决方法,一起看看吧。win10录屏文件太大怎么办:1、下载软件格式工厂来进行压缩文件。下载地址>>2、进入主页面,点击“视频-MP4”选项。3、在转换格式页面中点击“添加文件”,选择要压缩的MP4文件。4、点击页面“输出配置”,通过输出质量来压缩文件。5、下拉配置列表选择“低质量和大小”点击“确定”。6、点击“确定”完成视频文件的导入。7、点击“开始”进行转化。8、完成后即可

常见的几种编码方式 常见的几种编码方式 Oct 24, 2023 am 10:09 AM

常见的编码方式有ASCII编码、Unicode编码、UTF-8编码、UTF-16编码、GBK编码等。详细介绍:1、ASCII编码是最早的字符编码标准,使用7位二进制数表示128个字符,包括英文字母、数字、标点符号以及控制字符等;2、Unicode编码是一种用于表示世界上所有字符的标准编码方式,它为每个字符分配了一个唯一的数字码点;3、UTF-8编码等等。

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

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

wps怎么压缩文件夹打包发送 wps怎么压缩文件夹打包发送 Mar 20, 2024 pm 12:58 PM

办公人员在工作中使用wps软件进行操作的频率特别地多,有时一天会输入多个文件,然后发送给领导或发送到指定位置,那么wps软件如何压缩文件夹打包发送呢,下面小编就教大家这个操作步骤。首先,将要发送的文件和文件夹整理到同一个文件夹中。如果有很多文件,最好对每个文件进行命名,这样在发送时更易识别。  第二步,这个时候单击这个大的文件夹,然后点击鼠标右键。选择“添加到压缩文件”。  第三步,这个时候软件会自动帮我们打包我们的文件,选项“压缩到XX.zip”,这个zip就是打包的格式,然后点击立即压缩。 

如何正确理解 Linux 中打包和压缩的不同之处 如何正确理解 Linux 中打包和压缩的不同之处 Feb 20, 2024 pm 05:33 PM

Linux中打包和压缩是经常用到的操作,但许多用户往往混淆这两者的概念。本文将详细讨论在Linux系统中打包和压缩的不同之处,并通过具体的代码示例来帮助读者更好地理解。首先,需要明确打包和压缩的区别。打包是将多个文件或目录组合成一个单独的文件,通常用于整理、归档或传输文件。而压缩是将一个或多个文件通过算法进行压缩,以减小文件的大小,节省存储空间或加快传输速

See all articles