ホームページ 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 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Windows 11 でメモリ圧縮を有効または無効にする方法 Windows 11 でメモリ圧縮を有効または無効にする方法 Sep 19, 2023 pm 11:33 PM

Windows 11 ではメモリ圧縮が行われているため、RAM の容量が限られている場合でもデバイスが停止します。この記事では、Windows11でメモリ圧縮を有効または無効にする方法を紹介します。メモリ圧縮とは何ですか?メモリ圧縮は、データを RAM に書き込む前に圧縮して、より多くの記憶領域を提供する機能です。もちろん、物理メモリに保存されるデータが増えると、システム動作が高速になり、全体的なパフォーマンスが向上します。この機能は Windows 11 ではデフォルトで有効になっていますが、何らかの理由でアクティブになっていない場合は、無効にするか再度有効にすることができます。 Windows 11 でメモリ圧縮を有効にするにはどうすればよいですか?検索バーをクリックし、「powershell」と入力して、

7-zipの最大圧縮率設定、7zipを最小まで圧縮する方法 7-zipの最大圧縮率設定、7zipを最小まで圧縮する方法 Jun 18, 2024 pm 06:12 PM

ダウンロード Web サイトからダウンロードした圧縮パッケージは、解凍後に元の圧縮パッケージよりも大きくなり、クラウド ディスクにアップロードすると、小さいものでは数十 MB の差が生じることがわかりました。有料のスペースは、ファイルが小さい場合は問題ありませんが、ファイルが多数ある場合、ストレージのコストが大幅に増加します。私はそれを具体的に勉強したので、必要に応じてそこから学ぶことができます。圧縮レベル: 9-極度の圧縮 辞書サイズ: 256 または 384、辞書が圧縮されるほど遅くなります。256MB より前では圧縮率に大きな違いがあり、384MB 以降では圧縮率に違いはありません。最大 273 パラメータ: f=BCJ2、テストおよび追加パラメータの圧縮率が高くなります

ナレッジ グラフ: 大規模モデルの理想的なパートナー ナレッジ グラフ: 大規模モデルの理想的なパートナー Jan 29, 2024 am 09:21 AM

大規模言語モデル (LLM) は、滑らかで一貫したテキストを生成する機能を備えており、人工知能の会話や創造的な文章などの分野に新たな可能性をもたらします。ただし、LLM にはいくつかの重要な制限もあります。まず、彼らの知識はトレーニング データから認識されたパターンに限定されており、世界に対する真の理解が欠けています。第 2 に、推論スキルには限界があり、論理的な推論を行ったり、複数のデータ ソースからの事実を融合したりすることができません。より複雑で自由回答の質問に直面すると、LLM の答えは「幻想」として知られる不条理または矛盾したものになる場合があります。したがって、LLM はいくつかの面では非常に便利ですが、複雑な問題や現実世界の状況を扱う場合には、依然として一定の制限があります。これらのギャップを埋めるために、検索拡張生成 (RAG) システムが近年登場しました。

win10 画面録画ファイルサイズを減らすためのヒント win10 画面録画ファイルサイズを減らすためのヒント Jan 04, 2024 pm 12:05 PM

多くの友人が事務作業で画面を録画したり、ファイルを転送したりする必要がありますが、ファイルが大きすぎる問題が原因で多くのトラブルが発生することがあります。以下にファイルが大きすぎる問題の解決策を示します。 win10 画面録画ファイルが大きすぎる場合の対処方法: 1. ソフトウェア Format Factory をダウンロードしてファイルを圧縮します。ダウンロードアドレス >> 2. メインページに入り、「Video-MP4」オプションをクリックします。 3. 変換形式ページで「ファイルの追加」をクリックし、圧縮するMP4ファイルを選択します。 4. ページ上の「出力構成」をクリックして、出力品質に従ってファイルを圧縮します。 5. ドロップダウン構成リストから「低品質とサイズ」を選択し、「OK」をクリックします。 6. 「OK」をクリックしてビデオファイルのインポートを完了します。 7. 「開始」をクリックして変換を開始します。 8. 完了したら、次のことができます。

いくつかの一般的なエンコード方法 いくつかの一般的なエンコード方法 Oct 24, 2023 am 10:09 AM

一般的なエンコード方法には、ASCII エンコード、Unicode エンコード、UTF-8 エンコード、UTF-16 エンコード、GBK エンコードなどがあります。詳細な紹介: 1. ASCII エンコードは、英語の文字、数字、句読点、制御文字などを含む 128 文字を表すために 7 ビット 2 進数を使用する、最も初期の文字エンコード標準です; 2. Unicode エンコードは、文字を表すために使用される方法です。世界中のすべての文字 各文字に固有のデジタル コード ポイントを割り当てる文字の標準的なエンコード方式、3. UTF-8 エンコードなど。

フォルダーを圧縮してwpsで送信する方法 フォルダーを圧縮してwpsで送信する方法 Mar 20, 2024 pm 12:58 PM

オフィス ワーカーは仕事で wps ソフトウェアを頻繁に使用します。場合によっては、1 日に複数のファイルを入力し、リーダーまたは指定された場所に送信します。では、wps ソフトウェアはどのようにしてフォルダーを圧縮し、送信用にパッケージ化するのでしょうか? 以下のエディターが説明します。 . この操作ステップ。まず、送信するファイルとフォルダーを同じフォルダーに整理します。ファイルが多数ある場合は、送信時に識別しやすいように、各ファイルに名前を付けることをお勧めします。 2 番目のステップとして、今度はこの大きなフォルダーをクリックして右クリックします。 「アーカイブに追加」を選択します。ステップ 3: この時点で、ソフトウェアはファイルのパッケージ化を自動的に支援します。「XX.zip に圧縮」を選択します。この zip はパッケージ化形式であり、「今すぐ圧縮」をクリックします。​

C 言語における static キーワードの役割と使用法の詳細な分析 C 言語における static キーワードの役割と使用法の詳細な分析 Feb 20, 2024 pm 04:30 PM

C 言語における static キーワードの役割と使用法の詳細な分析 C 言語では、static は関数、変数、データ型の定義に使用できる非常に重要なキーワードです。 static キーワードを使用すると、オブジェクトのリンク属性、スコープ、ライフサイクルが変更される可能性があるため、C 言語における static キーワードの役割と使用法を詳しく分析してみましょう。静的変数と関数: 関数内で static キーワードを使用して定義された変数は静的変数と呼ばれ、グローバルなライフサイクルを持ちます。

Linux におけるパッケージ化と圧縮の違いを正しく理解する方法 Linux におけるパッケージ化と圧縮の違いを正しく理解する方法 Feb 20, 2024 pm 05:33 PM

パッケージ化と圧縮は Linux で一般的に使用される操作ですが、多くのユーザーは 2 つの概念を混同する傾向があります。この記事では、Linux システムにおけるパッケージ化と圧縮の違いについて詳しく説明し、読者の理解を助けるために特定のコード例を使用します。まず、梱包と圧縮の違いを明確にする必要があります。パッケージ化とは、複数のファイルまたはディレクトリを 1 つのファイルに組み合わせることであり、ファイルの整理、アーカイブ、または転送によく使用されます。圧縮とは、アルゴリズムを通じて 1 つ以上のファイルを圧縮して、ファイルのサイズを削減し、記憶領域を節約し、または転送を高速化することです。

See all articles