欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  php教程

基于静态huffman编码的压缩

程序员文章站 2022-05-12 15:06:45
...

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

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

实现过程:

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

2.构建huffman树

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

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

5.解压时根据先前的huffman树和字符位长度还原字符串
    
                    for($i=0;$i的结点合并生成出一个树
                     */
                    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;$iencode_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;$idecode_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
             * $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);        
            }


            /**
             * 广度优先遍历树,得到所有原字符对应的二进制表达式
             * $tree:已经构建好的huffman树
             * $tab:编码表,保存所有字符对应的编码
             * $a0:左遍历树的路径
             * $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
                            {
                                    //遍历到叶子节点时的所有路径,既二进制表达式,下同
                                    $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".