搜尋
首頁後端開發php教程Huffman編碼是什麼?php中Huffman編碼與解碼的實作方法

Huffman編碼是什麼?Huffman 編碼是一種資料壓縮演算法。我們常用的 zip 壓縮,其核心就是 Huffman 編碼,還有在 HTTP/中,Huffman 編碼被用於 HTTP 頭部的壓縮。這篇文章中我將給大家分享php中Huffman編碼與解碼的實作方法。

1. Huffman編碼

字數統計

Huffman編碼的第一步就是要統計文件中每個字元出現的次數,PHP的內建函數count_chars() 就可以做到:

$input = file_get_contents('input.txt');
$stat = count_chars($input, 1);

建構Huffman樹

接下來根據統計結果建構Huffman樹,建構方法在Wikipedia 有詳細的描述。這裡用PHP寫了一個簡易版的:

$huffmanTree = [];foreach ($stat as $char => $count) {
    $huffmanTree[] = [        
    'k' => chr($char),        
    'v' => $count,        
    'left' => null,        
    'right' => null,
    ];
}// 构造树的层级关系,思想见wiki:https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81$size = count($huffmanTree);for ($i = 0; $i !== $size - 1; $i++) {
    uasort($huffmanTree, function ($a, $b) {        
    if ($a['v'] === $b['v'])
     {            
     return 0;
        }        
        return $a[&#39;v&#39;] < $b[&#39;v&#39;] ? -1 : 1;
    });
    $a = array_shift($huffmanTree);
    $b = array_shift($huffmanTree);
    $huffmanTree[] = [        
    &#39;v&#39; => $a[&#39;v&#39;] + $b[&#39;v&#39;],        
    &#39;left&#39; => $b,        
    &#39;right&#39; => $a,
    ];
}
$root = current($huffmanTree);

經過計算之後,$root 就會指向Huffman 樹的根節點

根據Huffman樹產生編碼字典

#有了Huffman 樹,就可以產生用於編碼的字典:

function buildDict($elem, $code = &#39;&#39;, &$dict) {    
if (isset($elem[&#39;k&#39;]))
 {
        $dict[$elem[&#39;k&#39;]] = $code;
    } else {
        buildDict($elem[&#39;left&#39;], $code.&#39;0&#39;, $dict);
        buildDict($elem[&#39;right&#39;], $code.&#39;1&#39;, $dict);
    }
}
$dict = [];
buildDict($root, &#39;&#39;, $dict);

寫入檔案

#運用字典將檔案內容編碼,並寫入檔案。將Huffman編碼寫入檔案的有幾個注意的地方:

將編碼字典和編碼內容一起寫入檔案後,就沒法區分他們的邊界了,因此需要在檔案開始寫入他們各自佔用的位元組數

PHP提供的fwrite() 函數一次能寫入8-bit(一個位元組)或是8的整數倍個bit。但Huffman編碼中,一個字元可能只用 1-bit 表示,PHP不支援只往檔案中寫入 1-bit 這種操作。所以需要我們自行對編碼進行拼接,每湊齊 8-bit 才會寫入檔案。

Huffman編碼是什麼?php中Huffman編碼與解碼的實作方法

每湊齊8-bit才寫入

與第二條類似,最終形成的檔案大小一定是 8-bit 的整數倍。所以如果整個編碼的大小是8001-bit的話,還要在末尾補上7個0

$dictString = serialize($dict);// 写入字典和编码各自占用的字节数
$header = pack(&#39;VV&#39;, strlen($dictString), strlen($input));
fwrite($outFile, $header);// 写入字典本身
fwrite($outFile, $dictString);// 写入编码的内容$buffer = &#39;&#39;;
$i = 0;while (isset($input[$i])) {
    $buffer .= $dict[$input[$i]];    
    while (isset($buffer[7])) {
        $char = bindec(substr($buffer, 0, 8));
        fwrite($outFile, chr($char));
        $buffer = substr($buffer, 8);
    }
    $i++;
}// 末尾的内容如果没有凑齐 8-bit,需要自行补齐
if (!empty($buffer))
 {
    $char = bindec(str_pad($buffer, 8, &#39;0&#39;));
    fwrite($outFile, chr($char));
}
fclose($outFile);

2.Huffman編碼的解碼

Huffman編碼的解碼相對簡單:先讀取編碼字典,然後根據字典解碼出原始字元。

解碼過程有個問題要注意:由於我們在編碼過程中,在檔案結尾補齊了幾個0-bit,如果這些0-bit 在字典中剛好是某個字元的編碼時,就會造成錯誤的解碼。

所以解碼過程中,當已解碼的字元數達到文件長度時,就要停止解碼。

<?php
$content = file_get_contents(&#39;a.out&#39;);// 读出字典长度和编码内容长度
$header = unpack(&#39;VdictLen/VcontentLen&#39;, $content);
$dict = unserialize(substr($content, 8, $header[&#39;dictLen&#39;]));
$dict = array_flip($dict);
$bin = substr($content, 8 + $header[&#39;dictLen&#39;]);
$output = &#39;&#39;;
$key = &#39;&#39;;
$decodedLen = 0;
$i = 0;
while (isset($bin[$i]) && $decodedLen !== $header[&#39;contentLen&#39;]) {
    $bits = decbin(ord($bin[$i]));
    $bits = str_pad($bits, 8, &#39;0&#39;, STR_PAD_LEFT);    
    for ($j = 0; $j !== 8; $j++) {        // 每拼接上 1-bit,就去与字典比对是否能解码出字符
        $key .= $bits[$j];        
        if (isset($dict[$key]))
         {
            $output .= $dict[$key];
            $key = &#39;&#39;;
            $decodedLen++;            
            if ($decodedLen === $header[&#39;contentLen&#39;])
             {             
                break;
            }
        }
    }
    $i++;
}echo $output;

3.試驗

我們將Huffman編碼Wiki頁的HTML代碼儲存到本地,進行Huffman編碼測試,試驗結果:

#編碼前: 418,504 位元組

編碼後: 280,127 位元組

空間節省了33%,如果原文的重複內容較多,Huffman編碼節省的空間可以達到50% 以上.

除了文字內容,我們再嘗試將一個二進位檔案進行Huffman編碼,例如f.lux的安裝程序,試驗結果如下:

編碼前: 770,384 位元組

編碼後: 773,076 位元組

編碼後反而佔用了更大的空間,一方面是由於我們儲存字典時,並沒有做額外的處理,佔用了不少空間。另一方面,在二進位檔案中,各個字元出現的機率相對比較平均,無法發揮Huffman編碼的優勢。

相關推薦:

php對URL傳參進行編碼和解碼解析

以上是Huffman編碼是什麼?php中Huffman編碼與解碼的實作方法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
超越炒作:評估當今PHP的角色超越炒作:評估當今PHP的角色Apr 12, 2025 am 12:17 AM

PHP在現代編程中仍然是一個強大且廣泛使用的工具,尤其在web開發領域。 1)PHP易用且與數據庫集成無縫,是許多開發者的首選。 2)它支持動態內容生成和麵向對象編程,適合快速創建和維護網站。 3)PHP的性能可以通過緩存和優化數據庫查詢來提升,其廣泛的社區和豐富生態系統使其在當今技術棧中仍具重要地位。

PHP中的弱參考是什麼?什麼時候有用?PHP中的弱參考是什麼?什麼時候有用?Apr 12, 2025 am 12:13 AM

在PHP中,弱引用是通過WeakReference類實現的,不會阻止垃圾回收器回收對象。弱引用適用於緩存系統和事件監聽器等場景,需注意其不能保證對象存活,且垃圾回收可能延遲。

解釋PHP中的__ Invoke Magic方法。解釋PHP中的__ Invoke Magic方法。Apr 12, 2025 am 12:07 AM

\_\_invoke方法允許對象像函數一樣被調用。 1.定義\_\_invoke方法使對象可被調用。 2.使用$obj(...)語法時,PHP會執行\_\_invoke方法。 3.適用於日誌記錄和計算器等場景,提高代碼靈活性和可讀性。

解釋PHP 8.1中的纖維以進行並發。解釋PHP 8.1中的纖維以進行並發。Apr 12, 2025 am 12:05 AM

Fibers在PHP8.1中引入,提升了並發處理能力。 1)Fibers是一種輕量級的並發模型,類似於協程。 2)它們允許開發者手動控制任務的執行流,適合處理I/O密集型任務。 3)使用Fibers可以編寫更高效、響應性更強的代碼。

PHP社區:資源,支持和發展PHP社區:資源,支持和發展Apr 12, 2025 am 12:04 AM

PHP社區提供了豐富的資源和支持,幫助開發者成長。 1)資源包括官方文檔、教程、博客和開源項目如Laravel和Symfony。 2)支持可以通過StackOverflow、Reddit和Slack頻道獲得。 3)開發動態可以通過關注RFC了解。 4)融入社區可以通過積極參與、貢獻代碼和學習分享來實現。

PHP與Python:了解差異PHP與Python:了解差異Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

php:死亡還是簡單地適應?php:死亡還是簡單地適應?Apr 11, 2025 am 12:13 AM

PHP不是在消亡,而是在不斷適應和進化。 1)PHP從1994年起經歷多次版本迭代,適應新技術趨勢。 2)目前廣泛應用於電子商務、內容管理系統等領域。 3)PHP8引入JIT編譯器等功能,提升性能和現代化。 4)使用OPcache和遵循PSR-12標準可優化性能和代碼質量。

PHP的未來:改編和創新PHP的未來:改編和創新Apr 11, 2025 am 12:01 AM

PHP的未來將通過適應新技術趨勢和引入創新特性來實現:1)適應云計算、容器化和微服務架構,支持Docker和Kubernetes;2)引入JIT編譯器和枚舉類型,提升性能和數據處理效率;3)持續優化性能和推廣最佳實踐。

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.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版